Contention in Structured Concurrency: Provably Efficient Dynamic Non-Zero Indicators for Nested Parallelism

Abstract : 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 O(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.
Type de document :
Communication dans un congrès
22nd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, Feb 2017, Austin, United States. <10.1145/3018743.3018762>
Liste complète des métadonnées


https://hal.inria.fr/hal-01416531
Contributeur : Arthur Charguéraud <>
Soumis le : mercredi 14 décembre 2016 - 15:48:50
Dernière modification le : jeudi 15 juin 2017 - 09:08:44
Document(s) archivé(s) le : mercredi 15 mars 2017 - 13:28:42

Fichier

dynsnzi.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Umut Acar, Naama Ben-David, Mike Rainey. Contention in Structured Concurrency: Provably Efficient Dynamic Non-Zero Indicators for Nested Parallelism. 22nd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, Feb 2017, Austin, United States. <10.1145/3018743.3018762>. <hal-01416531>

Partager

Métriques

Consultations de
la notice

117

Téléchargements du document

67