---
res:
bibo_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.@eng
bibo_authorlist:
- foaf_Person:
foaf_givenName: Dan-Adrian
foaf_name: Alistarh, Dan-Adrian
foaf_surname: Alistarh
foaf_workInfoHomepage: http://www.librecat.org/personId=4A899BFC-F248-11E8-B48F-1D18A9856A87
- foaf_Person:
foaf_givenName: Giorgi
foaf_name: Nadiradze, Giorgi
foaf_surname: Nadiradze
foaf_workInfoHomepage: http://www.librecat.org/personId=3279A00C-F248-11E8-B48F-1D18A9856A87
- foaf_Person:
foaf_givenName: Nikita
foaf_name: Koval, Nikita
foaf_surname: Koval
foaf_workInfoHomepage: http://www.librecat.org/personId=2F4DB10C-F248-11E8-B48F-1D18A9856A87
bibo_doi: 10.1145/3323165.3323201
dct_date: 2019^xs_gYear
dct_isPartOf:
- http://id.crossref.org/issn/9781450361842
dct_language: eng
dct_publisher: ACM Press@
dct_title: Efficiency guarantees for parallel incremental algorithms under relaxed
schedulers@
...