Contention in Structured Concurrency: Provably Efficient Dynamic Non-Zero Indicators for Nested Parallelism
Contention in Structured Concurrency: Provably Efficient Dynamic Non-Zero Indicators for Nested Parallelism
复制标题
结构化并发中的争用：可证明有效的嵌套并行动态非零指标
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Mike Rainey
中科院分区：
文献类型：
--
作者：
Umut A. Acar;N. Ben;Mike Rainey
在过去的二十年中，已经设计和实施了许多并发数据结构。几乎所有此类工作分析并发数据结构从经验上进行了，忽略了其效率的渐近范围，部分原因是所需的分析的复杂性，部分原因是由于难以获得相关的渐近界限：当分析考虑到重要的实际因素时，例如作为争论，很难证明所需的界限。在本文中，我们表明，考虑结构化的并发或放松并发模型可以使建立强大的界限，也可以供争夺。为此，我们首先提出一个动态放松的计数器数据结构，该结构表明计数器的非零状态。我们的数据结构扩展了最近提出的称为SNZI的数据结构，从而使我们的结构能够动态增长，以响应系统的增加程度。然后，使用动态SNZI数据结构，我们为串联的定向无环图（SP-DAGS）提供了一个并发数据结构，这是一种广泛用于实现现代并行编程语言的关键数据结构。 SP-DAGS的关键组成部分是一个室内数据结构，是我们动态SNZI的实例。我们分析了嵌套并行计算范式下的并发SP-DAG和室内数据结构的效率。该范式提供了一个结构化的并发模型。在此模型下，我们证明我们的数据结构需要摊销（1）共享内存步骤，包括争论。我们提出了实施和实验评估，表明SP-DAGS数据结构是实用的，并且在实践中可以表现良好。
Over the past two decades, many concurrent data structures have been designed and implemented. Nearly all such work analyzes concurrent data structures empirically, omitting asymptotic bounds on their efficiency, partly because of the complexity of the analysis needed, and partly because of the difficulty of obtaining relevant asymptotic bounds: when the analysis takes into account important practical factors, such as contention, it is difficult or even impossible to prove desirable bounds. In this paper, we show that considering structured concurrency or relaxed concurrency models can enable establishing strong bounds, also for contention. To this end, we first present a dynamic relaxed counter data structure that indicates the non-zero status of the counter. Our data structure extends a recently proposed data structure, called SNZI, allowing our structure to grow dynamically in response to the increasing degree of concurrency in the system. Using the dynamic SNZI data structure, we then present a concurrent data structure for series-parallel directed acyclic graphs (sp-dags), a key data structure widely used in the implementation of modern parallel programming languages. The key component of sp-dags is an in-counter data structure that is an instance of our dynamic SNZI. We analyze the efficiency of our concurrent sp-dags and in-counter data structures under nested-parallel computing paradigm. This paradigm offers a structured model for concurrency. Under this model, we prove that our data structures require amortized (1) shared memory steps, including contention. We present an implementation and an experimental evaluation that suggests that the sp-dags data structure is practical and can perform well in practice.