Name
Title | ||
|---|---|---|
Sequential random permutation, list contraction and tree contraction are highly parallel |
Abstract | ||
|---|---|---|
We show that simple sequential randomized iterative algorithms for random permutation, list contraction, and tree contraction are highly parallel. In particular, if iterations of the algorithms are run as soon as all of their dependencies have been resolved, the resulting computations have logarithmic depth (parallel time) with high probability. Our proofs make an interesting connection between the dependence structure of two of the problems and random binary trees. Building upon this analysis, we describe linear-work, polylogarithmic-depth algorithms for the three problems. Although asymptotically no better than the many prior parallel algorithms for the given problems, their advantages include very simple and fast implementations, and returning the same result as the sequential algorithm. Experiments on a 40-core machine show reasonably good performance relative to the sequential algorithms. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.5555/2722129.2722159 | SODA |
Field | DocType | ISBN |
Analysis of parallel algorithms,Discrete mathematics,Combinatorics,Parallel algorithm,Computer science,Binary tree,Algorithm,Random permutation,Mathematical proof,Logarithm,Sequential algorithm,Computation | Conference | 978-1-61197-433-1 |
Citations | PageRank | References |
8 | 0.50 | 34 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Julian Shun | 1 | 593 | 32.57 |
| Yan Gu | 2 | 43 | 5.10 |
| Guy E. Blelloch | 3 | 2927 | 207.30 |
| Jeremy T. Fineman | 4 | 587 | 36.10 |
| Phillip B. Gibbons | 5 | 6863 | 624.14 |