Abstract
Finding the fastest algorithm to solve a problem is one of the main issues in Computational Geometry. Focusing only on worst case analysis or asymptotic computations leads to the development of complex data structures or hard to implement algorithms. Randomized algorithms appear in this scenario as a very useful tool in order to obtain easier implementations within a good expected time bound. However, parallel implementations of these algorithms are hard to develop and require an in-depth understanding of the language, the compiler and the underlying parallel computer architecture. In this paper we show how we can use speculative parallelization techniques to execute in parallel iterative algorithms such as randomized incremental constructions. In this paper we focus on the convex hull problem, and show that, using our speculative parallelization engine, the sequential algorithm can be automatically executed in parallel, obtaining speedups with as little as four processors, and reaching 5.15x speedup with 28 processors.
The first author has been partially supported by EPSRC under grant GR/R65169/01. The first and second authors have been partially supported by the European Commission under grant HPRI-CT-1999-00026. The third author has been partially supported by MCYT TIC2003-08933-C02-01.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Brönnimann, H., Iacono, J., Katajainen, J., Morin, P., Morrison, J., Toussaint, G.T.: In-place planar convex hull algorithms. In: Rajsbaum, S. (ed.) LATIN 2002. LNCS, vol. 2286, pp. 494–507. Springer, Heidelberg (2002)
CGAL, Computational Geometry Algorithms Library, http://www.cgal.org/
Chan, T.M.: Optimal output-sensitive convex hull algorithms in two and three dimensions. Discrete Comput. Geom. 16, 361–368 (1996)
Cintra, M., Llanos, D.R.: Toward efficient and robust software speculative parallelization on multiprocessors. In: Proc. of the SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), June 2003, pp. 13–24 (2003)
Cintra, M., Martínez, J.F., Torrellas, J.: Architectural support for scalable speculative parallelization in shared-memory multiprocessors. In: Proc. of the 27th Intl. Symp. on Computer Architecture (ISCA), June 2000, pp. 256–264 (2000)
Clarkson, K.L.: Randomized geometric algorithms. In: Du, D.-Z., Hwang, F. (eds.) Computing in Euclidean Geometry, 2nd edn. Lect. Notes Series on Computing, vol. 4, pp. 149–194. World Scientific, Singapore (1995)
Clarkson, K.L., Mehlhorn, K., Seidel, R.: Four results on randomized incremental constructions. Comput. Geom. Theory Appl. 3(4), 185–212 (1993)
Ghouse, M., Goodrich, M.: Fast randomized parallel methods for planar convex hull construction. Comput. Geom. Theory Appl. 7, 219–236 (1997)
Graham, R.L.: An efficient algorithm for determining the convex hull of a finite planar set. Inform. Process. Lett. 1, 132–133 (1972)
Hammond, L., Willey, M., Olukotun, K.: Data speculation support for a chip multiprocessor. In: Proc. of the 8th Intl. Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), October 1998, pp. 58–69 (1998)
Kirkpatrick, D.G., Seidel, R.: The ultimate planar convex hull algorithm? SIAM J. Comput. 15, 287–299 (1986)
Gupta, M., Nim, R.: Techniques for run-time parallelization of loops. Supercomputing (November 1998)
Mehlhorn, K., Näher, S.: LEDA: A Platform for Combinatorial and Geometric Computing. Cambridge University Press, Cambridge (2000)
Mulmuley, K.: Computational Geometry: An Introduction Through Randomized Algorithms. Prentice Hall, Englewood Cliffs (1994)
Rauchwerger, L., Padua, D.A.: The LRPD test: Speculative run-time parallelization of loops with privatization and reduction parallelization. IEEE Transactions on Parallel and Distributed Systems 10(2), 160–180 (1999)
Sohi, G., Breach, S., Vijaykumar, T.: Multiscalar processors. In: Proc. of the 22nd Intl. Symp. on Computer Architecture (ISCA), June 1995, pp. 414–425 (1995)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cintra, M., Llanos, D.R., Palop, B. (2004). Speculative Parallelization of a Randomized Incremental Convex Hull Algorithm. In: Laganá, A., Gavrilova, M.L., Kumar, V., Mun, Y., Tan, C.J.K., Gervasi, O. (eds) Computational Science and Its Applications – ICCSA 2004. ICCSA 2004. Lecture Notes in Computer Science, vol 3045. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-24767-8_20
Download citation
DOI: https://doi.org/10.1007/978-3-540-24767-8_20
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-22057-2
Online ISBN: 978-3-540-24767-8
eBook Packages: Springer Book Archive