research-article

Public Access

Parallelism in Randomized Incremental Algorithms

Authors:

Guy E. Blelloch,

Yihan SunAuthors Info & Claims

SPAA '16: Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures

Pages 467 - 478

https://doi.org/10.1145/2935764.2935766

Published: 11 July 2016 Publication History

Abstract

In this paper we show that most sequential randomized incremental algorithms are in fact parallel. We consider several random incremental algorithms including algorithms for comparison sorting and Delaunay triangulation; linear programming, closest pair, and smallest enclosing disk in constant dimensions; as well as least-element lists and strongly connected components on graphs.

We analyze the dependence between iterations in an algorithm, and show that the dependence structure is shallow for all of the algorithms, implying high parallelism. We identify three types of dependences found in the algorithms studied and present a framework for analyzing each type of algorithm. Using the framework gives work-efficient polylogarithmic-depth parallel algorithms for most of the problems that we study. Some of these algorithms are straightforward (e.g., sorting and linear programming), while others are more novel and require more effort to obtain the desired bounds (e.g., Delaunay triangulation and strongly connected components). The most surprising of these results is for planar Delaunay triangulation for which the incremental approach is by far the most commonly used in practice, but for which it was not previously known whether it is theoretically efficient in parallel.

References

[1]

M. Ajtai and N. Megiddo. A deterministic poly$(łog łog n)-time n-processor algorithm for linear programming in fixed dimension. In ACM Symposium on Theory of Computing (STOC), pages 327--338, 1992.

Digital Library

[2]

N. Alon and N. Megiddo. Parallel linear programming in fixed dimension almost surely in constant time. J. ACM (JACM), 41(2):422--434, Mar. 1994.

Digital Library

[3]

M. Atallah and M. Goodrich. Deterministic parallel computational geometry. In Synthesis of Parallel Algorithms, pages 497--536. Morgan Kaufmann, 1993.

[4]

J. Barnat, P. Bauch, L. Brim, and M. Ceska. Computing strongly connected components in parallel on CUDA. In International Parallel & Distributed Processing Symposium (IPDPS), pages 544--555, 2011.

Digital Library

[5]

D. K. Blandford, G. E. Blelloch, and C. Kadow. Engineering a compact parallel Delaunay algorithm in 3D. In ACM Symposium on Computational Geometry (SoCG), pages 292--300, 2006.

Digital Library

[6]

G. E. Blelloch, J. T. Fineman, P. B. Gibbons, and J. Shun. Internally deterministic algorithms can be fast. In Principles and Practice of Parallel Programming (PPoPP), pages 181--192, 2012.

Digital Library

[7]

G. E. Blelloch, J. T. Fineman, and J. Shun. Greedy sequential maximal independent set and matching are parallel on average. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 308--317, 2012.

Digital Library

[8]

G. E. Blelloch, Y. Gu, and Y. Sun. Efficient construction of probabilistic tree embeddings. arXiv preprint: 1605.04651, 2016.

[9]

G. E. Blelloch, Y. Gu, Y. Sun, and K. Tangwongsan. Parallel shortest-paths using radius stepping. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2016.

Digital Library

[10]

G. E. Blelloch, A. Gupta, and K. Tangwongsan. Parallel probabilistic tree embeddings, k-median, and buy-at-bulk network design. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 205--213, 2012.

Digital Library

[11]

G. E. Blelloch, J. C. Hardwick, G. L. Miller, and D. Talmor. Design and implementation of a practical parallel Delaunay algorithm. Algorithmica, 24(3--4):243--269, 1999.

[12]

R. L. Bocchino, V. S. Adve, S. V. Adve, and M. Snir. Parallel programming must be deterministic by default. In Usenix HotPar, 2009.

Digital Library

[13]

J.-D. Boissonnat and M. Teillaud. On the randomized construction of the delaunay tree. Theoretical Computer Science, 112(2):339--354, 1993.

Digital Library

[14]

R. P. Brent. The parallel evaluation of general arithmetic expressions. J. ACM (JACM), 21(2):201--206, 1974.

Digital Library

[15]

C. Cao Minh, J. Chung, C. Kozyrakis, and K. Olukotun. STAMP: Stanford transactional applications for multi-processing. In IEEE International Symposium on Workload Characterization (IISWC), 2008.

[16]

D. Z. Chen and J. Xu. Two-variable linear programming in parallel. Computational Geometry, 21(3):155 -- 165, 2002.

Digital Library

[17]

P. Cignoni, C. Montani, R. Perego, and R. Scopigno. Parallel 3D delaunay triangulation. Computer Graphics Forum, 12(3):129--142, 1993.

[18]

M. Cintra, D. R. Llanos, and B. Palop. International conference on computational science and its applications. In Speculative Parallelization of a Randomized Incremental Convex Hull Algorithm, pages 188--197, 2004.

[19]

K. L. Clarkson and P. W. Shor. Applications of random sampling in computational geometry, II. Discrete & Computational Geometry, 4(5):387--421, 1989.

Digital Library

[20]

E. Cohen. Size-estimation framework with applications to transitive closure and reachability. Journal of Computer and System Sciences, 55(3):441--453, 1997.

Digital Library

[21]

E. Cohen and H. Kaplan. Efficient estimation algorithms for neighborhood variance and other moments. In ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 157--166, 2004.

Digital Library

[22]

R. Cole. Parallel merge sort. SIAM J. Comput., 17(4):770--785, 1988.

Digital Library

[23]

D. Coppersmith, L. Fleischer, B. Hendrickson, and A. Pinar. A divide-and-conquer algorithm for identifying strongly connected components. Technical Report RC23744, IBM, 2003.

[24]

M. de Berg, O. Cheong, M. van Kreveld, and M. Overmars. Computational Geometry: Algorithms and Applications. Springer-Verlag, 2008.

Digital Library

[25]

X. Deng. An optimal parallel algorithm for linear programming in the plane. Information Processing Letters, 35(4):213 -- 217, 1990.

Digital Library

[26]

P. Diaz, D. R. Llanos, and B. Palop. Parallelizing 2D-convex hulls on clusters: Sorting matters. Jornadas De Paralelismo, 2004.

[27]

N. Du, L. Song, M. Gomez-Rodriguez, and H. Zha. Scalable influence estimation in continuous-time diffusion networks. In Advances in Neural Information Processing Systems (NIPS), pages 3147--3155, 2013.

[28]

M. Dyer. A parallel algorithm for linear programming in fixed dimension. In Symposium on Computational Geometry (SoCG), pages 345--349, 1995.

Digital Library

[29]

H. Edelsbrunner. Geometry and Topology for Mesh Generation. Cambridge University Press, 2006.

Digital Library

[30]

J. Fakcharoenphol, S. Rao, and K. Talwar. A tight bound on approximating arbitrary metrics by tree metrics. Journal of Computer and System Sciences (JCSS), 69(3):485--497, 2004.

Digital Library

[31]

J. Gil, Y. Matias, and U. Vishkin. Towards a theory of nearly constant time parallel algorithms. In Foundations of Computer Science (FOCS), pages 698--710, 1991.

Digital Library

[32]

M. Golin, R. Raman, C. Schwarz, and M. Smid. Simple randomized algorithms for closest pair problems. Nordic J. of Computing, 2(1):3--27, Mar. 1995.

Digital Library

[33]

A. Gonzalez-Escribano, D. R. Llanos, D. Orden, and B. Palop. Parallelization alternatives and their performance for the convex hull problem. Applied Mathematical Modelling, 30(7):563 -- 577, 2006.

[34]

M. T. Goodrich. Fixed-dimensional parallel linear programming via relative ε-approximations. In ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 132--141, 1996.

Digital Library

[35]

M. T. Goodrich and E. A. Ramos. Bounded-independence derandomization of geometric partitioning with applications to parallel fixed-dimensional linear programming. Discrete & Computational Geometry, 18(4):397--420, 1997.

[36]

P. J. Green and R. Sibson. Computing Dirichlet tessellations in the plane. The Computer Journal, 21(2):168--173, 1978.

[37]

Y. Gu, J. Shun, Y. Sun, and G. E. Blelloch. A top-down parallel semisort. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 24--34, 2015.

Digital Library

[38]

L. J. Guibas, D. E. Knuth, and M. Sharir. Randomized incremental construction of Delaunay and Voronoi diagrams. Algorithmica, 7(4):381--413, 1992.

Digital Library

[39]

S. Har-peled. Geometric Approximation Algorithms. American Mathematical Society, 2011.

Digital Library

[40]

W. Hasenplaugh, T. Kaler, T. B. Schardl, and C. E. Leiserson. Ordering heuristics for parallel graph coloring. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 166--177, 2014.

Digital Library

[41]

S. Hong, N. C. Rodia, and K. Olukotun. On fast parallel detection of strongly connected components (SCC) in small-world graphs. In International Conference for High Performance Computing, Networking, Storage and Analysis (SC), pages 1--11, 2013.

Digital Library

[42]

J. Jaja. Introduction to Parallel Algorithms. Addison-Wesley Professional, 1992.

Digital Library

[43]

M. Khan, F. Kuhn, D. Malkhi, G. Pandurangan, and K. Talwar. Efficient distributed approximation algorithms via probabilistic tree embeddings. Distributed Computing, 25(3):189--205, 2012.

[44]

S. Khuller and Y. Matias. A simple randomized sieve algorithm for the closest-pair problem. Information and Computation, 118(1):34--37, 1995.

Digital Library

[45]

P. N. Klein and S. Subramanian. A randomized parallel algorithm for single-source shortest paths. Journal of Algorithms, 25(2):205--220, 1997.

Digital Library

[46]

D. R. Llanos, D. Orden, and B. Palop. Meseta: A new scheduling strategy for speculative parallelization of randomized incremental algorithms. International Conference on Parallel Processing Workshops, pages 121--128, 2005.

Digital Library

[47]

N. Megiddo. Linear-time algorithms for linear programming in $R^3$ and related problems. SIAM Journal on Computing, 1983.

[48]

K. Mulmuley. Computational geometry - an introduction through randomized algorithms. Prentice Hall, 1994.

[49]

X. Pan, D. Papailiopoulos, S. Oymak, B. Recht, K. Ramchandran, and M. I. Jordan. Parallel correlation clustering on big graphs. In Advances in Neural Information Processing Systems (NIPS), 2015.

Digital Library

[50]

K. Pingali, D. Nguyen, M. Kulkarni, M. Burtscher, M. A. Hassaan, R. Kaleem, T.-H. Lee, A. Lenharth, R. Manevich, M. Méndez-Lojo, D. Prountzos, and X. Sui. The tao of parallelism in algorithms. In ACM SIGPLAN conference on Programming Language Design and Implementation (PLDI), 2011.

Digital Library

[51]

M. O. Rabin. Probabilistic algorithms. Algorithms and Complexity: New Directions and Recent Results, pages 21--39, 1976.

[52]

S. Rajasekaran and J. H. Reif. Optimal and sublogarithmic time randomized parallel sorting algorithms. SIAM J. Comput., 18(3):594--607, 1989.

Digital Library

[53]

J. H. Reif. Depth-first search is inherently sequential. Information Processing Letters, 20(5):229--234, 1985.

[54]

J. H. Reif and S. Sen. Optimal randomized parallel algorithms for computational geometry. Algorithmica, 7(1--6):91--117, 1992.

[55]

W. Schudy. Finding strongly connected components in parallel using O(log2 n) reachability queries. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 146--151, 2008.

Digital Library

[56]

R. Seidel. Small-dimensional linear programming and convex hulls made easy. Discrete & Computational Geometry, 6(3):423--434, 1991.

Digital Library

[57]

R. Seidel. Backwards analysis of randomized geometric algorithms. In New Trends in Discrete and Computational Geometry, pages 37--67. 1993.

[58]

S. Sen. A deterministic poly(łogłog n) time optimal CRCW PRAM algorithm for linear programming in fixed dimensions. Technical report, Department of Computer Science, University of Newcastle, 1995.

[59]

J. Shun, G. E. Blelloch, J. T. Fineman, P. B. Gibbons, A. Kyrola, H. V. Simhadri, and K. Tangwongsan. Brief announcement: the Problem Based Benchmark Suite. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 68--70, 2012.

Digital Library

[60]

J. Shun, Y. Gu, G. Blelloch, J. Fineman, and P. Gibbons. Sequential random permutation, list contraction and tree contraction are highly parallel. In ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 431--448, 2015.

Digital Library

[61]

G. M. Slota, S. Rajamanickam, and K. Madduri. BFS and Coloring-based parallel algorithms for strongly connected components and related problems. In International Parallel and Distributed Processing Symposium (IPDPS), 2014.

Digital Library

[62]

T. H. Spencer. Time-work tradeoffs for parallel algorithms. Journal of the ACM (JACM), 44(5):742--778, 1997.

Digital Library

[63]

R. Tarjan. Depth-first search and linear graph algorithms. SIAM Journal on Computing, 1(2):146--160, 1972.

Digital Library

[64]

D. Tomkins, T. Smith, N. M. Amato, and L. Rauchwerger. Efficient, reachability-based, parallel algorithms for finding strongly connected components. Technical report, Texas A&M University, 2015.

[65]

J. D. Ullman and M. Yannakakis. High-probability parallel transitive-closure algorithms. SIAM Journal on Computing, 20(1):100--125, 1991.

Digital Library

[66]

U. Vishkin. Thinking in Parallel: Some Basic Data-Parallel Algorithms and Techniques. 2010.

[67]

E. Welzl. Smallest enclosing disks (balls and ellipsoids). In New Results and New Trends in Computer Science, 1991.

Cited By

Manohar MShen ZBlelloch GDhulipala LGu YSimhadri HSun YLee IChabbi MSteuwer M(2024)ParlayANN: Scalable and Deterministic Parallel Graph-Based Approximate Nearest Neighbor Search AlgorithmsProceedings of the 29th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming10.1145/3627535.3638475(270-285)Online publication date: 2-Mar-2024
https://dl.acm.org/doi/10.1145/3627535.3638475
Lee TZhang YMareels I(2024)Multi-agreements in social networks based on LaSalle invariance principle and positive definitenessAutomatica10.1016/j.automatica.2024.111666165(111666)Online publication date: Jul-2024
https://doi.org/10.1016/j.automatica.2024.111666
Fedorov AHashemi DNadiradze GAlistarh DAgrawal KShun J(2023)Provably-Efficient and Internally-Deterministic Parallel Union-FindProceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3558481.3591082(261-271)Online publication date: 17-Jun-2023
https://dl.acm.org/doi/10.1145/3558481.3591082
Show More Cited By

Index Terms

Parallelism in Randomized Incremental Algorithms
1. Theory of computation
  1. Design and analysis of algorithms
  2. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

Parallelism in Randomized Incremental Algorithms

In this article, we show that many sequential randomized incremental algorithms are in fact parallel. We consider algorithms for several problems, including Delaunay triangulation, linear programming, closest pair, smallest enclosing disk, least-element ...
Delaunay refinement algorithms for triangular mesh generation

Delaunay refinement is a technique for generating unstructured meshes of triangles for use in interpolation, the finite element method, and the finite volume method. In theory and practice, meshes produced by Delaunay refinement satisfy guaranteed ...
Quality Meshing with Weighted Delaunay Refinement

Delaunay meshes with bounded circumradius to shortest edge length ratio have been proposed in the past for quality meshing. The only poor quality tetrahedra, called slivers, that can occur in such a mesh can be eliminated by the sliver exudation ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SPAA '16: Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures

July 2016

492 pages

ISBN:9781450342100

DOI:10.1145/2935764

General Chair:
Christian Scheideler
University of Paderborn
,
Program Chair:
Seth Gilbert
National University of Singapore

Copyright © 2016 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 July 2016

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

SPAA '16

Sponsor:

SPAA '16: 28th ACM Symposium on Parallelism in Algorithms and Architectures

July 11 - 13, 2016

California, Pacific Grove, USA

Acceptance Rates

Overall Acceptance Rate 447 of 1,461 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

19
Total Citations
View Citations
680
Total Downloads

Downloads (Last 12 months)83
Downloads (Last 6 weeks)19

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Manohar MShen ZBlelloch GDhulipala LGu YSimhadri HSun YLee IChabbi MSteuwer M(2024)ParlayANN: Scalable and Deterministic Parallel Graph-Based Approximate Nearest Neighbor Search AlgorithmsProceedings of the 29th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming10.1145/3627535.3638475(270-285)Online publication date: 2-Mar-2024
https://dl.acm.org/doi/10.1145/3627535.3638475
Lee TZhang YMareels I(2024)Multi-agreements in social networks based on LaSalle invariance principle and positive definitenessAutomatica10.1016/j.automatica.2024.111666165(111666)Online publication date: Jul-2024
https://doi.org/10.1016/j.automatica.2024.111666
Fedorov AHashemi DNadiradze GAlistarh DAgrawal KShun J(2023)Provably-Efficient and Internally-Deterministic Parallel Union-FindProceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3558481.3591082(261-271)Online publication date: 17-Jun-2023
https://dl.acm.org/doi/10.1145/3558481.3591082
Wang YYu SDhulipala LGu YShun JLee JAgrawal KSpear M(2022)ParGeoProceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming10.1145/3503221.3508429(450-452)Online publication date: 2-Apr-2022
https://dl.acm.org/doi/10.1145/3503221.3508429
Cao NFineman JRussell KAgrawal KLee I(2022)Parallel Shortest Paths with Negative Edge WeightsProceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3490148.3538583(177-190)Online publication date: 11-Jul-2022
https://dl.acm.org/doi/10.1145/3490148.3538583
Suijlen Wde Framond FLallouet APetitet A(2022)A Parallel Algorithm for GAC Filtering of the Alldifferent ConstraintIntegration of Constraint Programming, Artificial Intelligence, and Operations Research10.1007/978-3-031-08011-1_26(390-407)Online publication date: 20-Jun-2022
https://dl.acm.org/doi/10.1007/978-3-031-08011-1_26
Dhulipala LBlelloch GShun J(2021)Theoretically Efficient Parallel Graph Algorithms Can Be Fast and ScalableACM Transactions on Parallel Computing10.1145/34343938:1(1-70)Online publication date: 22-Apr-2021
https://dl.acm.org/doi/10.1145/3434393
Blelloch GGu YShun JSun Y(2020)Parallelism in Randomized Incremental AlgorithmsJournal of the ACM10.1145/340281967:5(1-27)Online publication date: 19-Sep-2020
https://dl.acm.org/doi/10.1145/3402819
Blelloch GGu YShun JSun YScheideler CSpear M(2020)Randomized Incremental Convex Hull is Highly ParallelProceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3350755.3400255(103-115)Online publication date: 6-Jul-2020
https://dl.acm.org/doi/10.1145/3350755.3400255
Alistarh DNadiradze GKoval NScheideler CBerenbrink P(2019)Efficiency Guarantees for Parallel Incremental Algorithms under Relaxed SchedulersThe 31st ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3323165.3323201(145-154)Online publication date: 17-Jun-2019
https://dl.acm.org/doi/10.1145/3323165.3323201
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents