Umut A. Acar
Andrew Cotter
ABSTRACT
Parallel algorithms and dynamic algorithms possess an interesting duality property: compared to sequential algorithms, parallel algorithms improve run-time while preserving work, while dynamic algorithms improve work but typically offer no parallelism. Although they are often considered separately, parallel and dynamic algorithms employ similar design techniques. They both identify parts of the computation that are independent of each other. This suggests that dynamic algorithms could be parallelized to improve work efficiency while preserving fast parallel run-time.
In this paper, we parallelize a dynamic algorithm for well-spaced point sets, an important problem related to mesh refinement in computational geometry. Our parallel dynamic algorithm computes a well-spaced superset of a dynamically changing set of points, allowing arbitrary dynamic modifications to the input set. On an EREW PRAM, our algorithm processes batches of k modifications such as insertions and deletions in O(k log Δ) total work and in O(log Δ) parallel time using k processors, where Δ is the geometric spread of the data, while ensuring that the output is always within a constant factor of the optimal size. EREW PRAM model is quite different from actual hardware such as modern multiprocessors. We therefore describe techniques for implementing our algorithm on modern multi-core computers and provide a prototype implementation. Our empirical evaluation shows that our algorithm can be practical, yielding a large degree of parallelism and good speedups.
- U. A. Acar. Self-Adjusting Computation. PhD thesis, Department of Computer Science, Carnegie Mellon University, May 2005. Google Scholar
Digital Library
- U. A. Acar, G. E. Blelloch, M. Blume, and K. Tangwongsan. An experimental analysis of self-adjusting computation. In Programming Language Design and Implementation, 2006. Google ScholarDigital Library
- U. A. Acar, G. E. Blelloch, K. Tangwongsan, and D. Turkoglu. Robust kinetic convex hulls in 3D. In European Symposium on Algorithms, September 2008. Google ScholarDigital Library
- U. A. Acar, A. Cotter, B. Hudson, and D. Turkoglu. Dynamic well-spaced point sets. In SCG '10: the 26th Annual Symposium on Computational Geometry, 2010. Google ScholarDigital Library
- U. A. Acar, B. Hudson, and D. Turkoglu. Kinetic mesh refinement in 2d. In SCG '11: the 27th Annual Symposium on Computational Geometry, 2011. Google ScholarDigital Library
- M. Bern, D. Eppstein, and J. R. Gilbert. Provably Good Mesh Generation. J. Computer and System Sciences, 48(3):384--409, 1994. Google ScholarDigital Library
- M. W. Bern, D. Eppstein, and S.-H. Teng. Parallel construction of quadtrees and quality triangulations. International Journal of Computational Geometry and Applications, 9(6):517--532, 1999.Google ScholarCross Ref
- J.-D. Boissonnat, O. Devillers, R. Schott, M. Teillaud, and M. Yvinec. Applications of random sampling to on-line algorithms in computational geometry. Discrete Computional Geometry, 8:51--71, 1992. Google ScholarDigital Library
- S.-W. Cheng, T. K. Dey, H. Edelsbrunner, M. A. Facello, and S.-H. Teng. Silver exudation. J. ACM, 47(5):883--904, 2000. Google ScholarDigital Library
- L. P. Chew. Guaranteed-quality triangular meshes. Technical Report TR-89-983, Department of Computer Science, Cornell University, 1989.Google ScholarCross Ref
- Y.-J. Chiang and R. Tamassia. Dynamic algorithms in computational geometry. Proceedings of the IEEE, 80(9):1412--1434, 1992.Google ScholarCross Ref
- K. L. Clarkson, K. Mehlhorn, and R. Seidel. Four results on randomized incremental constructions. Computational Geometry Theory and Application, 3:185--212, 1993. Google ScholarDigital Library
- C. Demetrescu, I. Finocchi, and G. Italiano. Handbook on Data Structures and Applications, chapter 36: Dynamic Graphs. 2005.Google Scholar
- L. Guibas. Modeling motion. In J. Goodman and J. O'Rourke, editors, Handbook of Discrete and Computational Geometry, pages 1117--1134. Chapman and Hall/CRC, 2nd edition, 2004.Google Scholar
- M. A. Hammer, U. A. Acar, and Y. Chen. CEAL: A C-based language for self-adjusting computation. In Programming Language Design and Implementation, June 2009. Google ScholarDigital Library
- B. Hudson, G. Miller, and T. Phillips. Sparse voronoi refinement. In Proceedings of the 2006 International Meshing Roundtable, 2006.Google ScholarCross Ref
- B. Hudson, G. Miller, and T. Phillips. Sparse Parallel Delaunay Mesh Refinement. In SPAA, 2007. Google ScholarDigital Library
- B. Hudson and D. Turkoglu. An efficient query structure for mesh refinement. In Canadian Conference on Computational Geometry, 2008.Google Scholar
- H. Jung and K. Mehlhorn. Parallel algorithms for computing maximal independent sets in trees and for updating minimum spanning trees. Inf. Process. Lett., 27:227--236, April 1988. Google ScholarDigital Library
- R. Ley-Wild, U. A. Acar, and M. Fluet. A cost semantics for self-adjusting computation. In Principles of Programming Languages, 2009. Google ScholarDigital Library
- G. L. Miller, D. Talmor, S.-H. Teng, N. Walkington, and H. Wang. Control Volume Meshes Using Sphere Packing: Generation, Refinement and Coarsening. In Fifth Intl. Meshing Roundtable, pages 47--61, 1996.Google Scholar
- D. Moore. The cost of balancing generalized quadtrees. In SMA '95: symposium on Solid modeling and app., pages 305--312, New York, NY, USA, 1995. ACM. Google ScholarDigital Library
- G. M. Morton. A computer oriented geodetic data base; and a new technique in file sequencing. Technical report, IBM, Ottowa, CA, 1966.Google Scholar
- K. Mulmuley. Computational Geometry: An Introduction Through Randomized Algorithms. Prentice Hall, 1994.Google Scholar
- S. Pawagi and O. Kaser. Optimal parallel algorithms for multiple updates of minimum spanning trees. Algorithmica, 9:357--381, 1993.Google ScholarCross Ref
- O. Schwarzkopf. Dynamic maintenance of geometric structures made easy. In 32nd Annual Symposium on Foundations of Computer Science, pages 197--206, October 1991. Google ScholarDigital Library
- D. Talmor. Well-Spaced Points for Numerical Methods. PhD thesis, Carnegie Mellon University, August 1997. CMU-CS-97-164.Google Scholar
Index Terms
- Parallelism in dynamic well-spaced point sets
Recommendations
Dynamic well-spaced point sets
SoCG '10: Proceedings of the twenty-sixth annual symposium on Computational geometryIn a well-spaced point set, when there is a bounding hypercube, the Voronoi cells all have bounded aspect ratio, i.e., the distance from the Voronoi site to the farthest point in the Voronoi cell divided by the distance to the nearest neighbor in the ...
Dynamic well-spaced point sets
In a well-spaced point set the Voronoi cells all have bounded aspect ratio. Well-spaced point sets satisfy some important geometric properties and yield quality Voronoi or simplicial meshes that are important in scientific computations. In this paper, ...
Kinetic mesh refinement in 2D
SoCG '11: Proceedings of the twenty-seventh annual symposium on Computational geometryWe provide a kinetic data structure (KDS) to the planar kinetic mesh refinement problem, which concerns computation of meshes of continuously moving points. Our KDS computes the Delaunay triangulation of a size-optimal well-spaced superset of a set of ...
Comments