@inproceedings{6673,
abstract = {Several classic problems in graph processing and computational geometry are solved via incremental algorithms, which split computation into a series of small tasks acting on shared state, which gets updated progressively. While the sequential variant of such algorithms usually specifies a fixed (but sometimes random) order in which the tasks should be performed, a standard approach to parallelizing such algorithms is to relax this constraint to allow for out-of-order parallel execution. This is the case for parallel implementations of Dijkstra's single-source shortest-paths (SSSP) algorithm, and for parallel Delaunay mesh triangulation. While many software frameworks parallelize incremental computation in this way, it is still not well understood whether this relaxed ordering approach can still provide any complexity guarantees. In this paper, we address this problem, and analyze the efficiency guarantees provided by a range of incremental algorithms when parallelized via relaxed schedulers. We show that, for algorithms such as Delaunay mesh triangulation and sorting by insertion, schedulers with a maximum relaxation factor of k in terms of the maximum priority inversion allowed will introduce a maximum amount of wasted work of O(łog n poly(k)), where n is the number of tasks to be executed. For SSSP, we show that the additional work is O(poly(k), dmax / wmin), where dmax is the maximum distance between two nodes, and wmin is the minimum such distance. In practical settings where n >> k, this suggests that the overheads of relaxation will be outweighed by the improved scalability of the relaxed scheduler. On the negative side, we provide lower bounds showing that certain algorithms will inherently incur a non-trivial amount of wasted work due to scheduler relaxation, even for relatively benign relaxed schedulers.},
author = {Alistarh, Dan-Adrian and Nadiradze, Giorgi and Koval, Nikita},
booktitle = {31st ACM Symposium on Parallelism in Algorithms and Architectures},
isbn = {9781450361842},
location = {Phoenix, AZ, United States},
pages = {145--154},
publisher = {ACM Press},
title = {{Efficiency guarantees for parallel incremental algorithms under relaxed schedulers}},
doi = {10.1145/3323165.3323201},
year = {2019},
}
@misc{6485,
abstract = {Traditional concurrent programming involves manipulating shared mutable state. Alternatives to this programming style are communicating sequential processes (CSP) [1] and actor [2] models, which share data via explicit communication. Rendezvous channelis the common abstraction for communication between several processes, where senders and receivers perform a rendezvous handshake as a part of their protocol (senders wait for receivers and vice versa). Additionally to this, channels support the select expression. In this work, we present the first efficient lock-free channel algorithm, and compare it against Go [3] and Kotlin [4] baseline implementations.},
author = {Koval, Nikita and Alistarh, Dan-Adrian and Elizarov, Roman},
booktitle = {Proceedings of the 24th Symposium on Principles and Practice of Parallel Programming},
isbn = {9781450362252},
location = {Washington, NY, United States},
pages = {417--418},
publisher = {ACM Press},
title = {{Lock-free channels for programming via communicating sequential processes}},
doi = {10.1145/3293883.3297000},
year = {2019},
}