LIPIcs.SEA.2018.20.pdf
- Filesize: 0.51 MB
- 13 pages
Document
Restructuring Expression Dags for Efficient Parallelization
Author
-
Part of:
Volume:
17th International Symposium on Experimental Algorithms (SEA 2018)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Experimental Algorithms (SEA) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2018-06-19
Cite AsGet BibTex
Martin Wilhelm. Restructuring Expression Dags for Efficient Parallelization. In 17th International Symposium on Experimental Algorithms (SEA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 103, pp. 20:1-20:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.SEA.2018.20
https://doi.org/10.4230/LIPIcs.SEA.2018.20
Abstract
In the field of robust geometric computation it is often necessary to make exact decisions based on inexact floating-point arithmetic. One common approach is to store the computation history in an arithmetic expression dag and to re-evaluate the expression with increasing precision until an exact decision can be made. We show that exact-decisions number types based on expression dags can be evaluated faster in practice through parallelization on multiple cores. We compare the impact of several restructuring methods for the expression dag on its running time in a parallel environment.
Subject Classification
ACM Subject Classification
- Theory of computation → Data structures design and analysis
- Theory of computation → Computational geometry
- Computing methodologies → Parallel algorithms
Keywords
- exact computation
- expression dag
- parallel evaluation
- restructuring
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Mohand Ourabah Benouamer, P. Jaillon, Dominique Michelucci, and Jean-Michel Moreau. A lazy exact arithmetic. In 11th Symposium on Computer Arithmetic, 29 June - 2 July 1993, Windsor, Canada, Proceedings., pages 242-249, 1993. URL: http://dx.doi.org/10.1109/ARITH.1993.378086.
-
Richard P. Brent. The parallel evaluation of general arithmetic expressions. J. ACM, 21(2):201-206, 1974.
- Christoph Burnikel, Stefan Funke, Kurt Mehlhorn, Stefan Schirra, and Susanne Schmitt. A separation bound for real algebraic expressions. Algorithmica, 55(1):14-28, 2009. URL: http://dx.doi.org/10.1007/s00453-007-9132-4.
-
Christoph Burnikel, Kurt Mehlhorn, and Stefan Schirra. The leda class real number. Report MPI-I-1996-1-001, Max-Planck-Institut für Informatik, Saarbrücken, Germany, 1996.
- Vijay Karamcheti, C. Li, Igor Pechtchanski, and Chee-Keng Yap. A core library for robust numeric and geometric computation. In Proceedings of the Fifteenth Annual Symposium on Computational Geometry, Miami Beach, Florida, USA, June 13-16, 1999, pages 351-359, 1999. URL: http://dx.doi.org/10.1145/304893.304989.
-
Gary L. Miller and John H. Reif. Parallel tree contraction and its application. In 26th Annual Symposium on Foundations of Computer Science, Portland, Oregon, USA, 21-23 October 1985, pages 478-489, 1985.
- Marc Mörig, Ivo Rössling, and Stefan Schirra. On design and implementation of a generic number type for real algebraic number computations based on expression dags. Mathematics in Computer Science, 4(4):539-556, 2010. URL: http://dx.doi.org/10.1007/s11786-011-0086-1.
- Marc Mörig and Stefan Schirra. Precision-driven computation in the evaluation of expression-dags with common subexpressions: Problems and solutions. In 6th International Conference on Mathematical Aspects of Computer and Information Sciences, MACIS, pages 451-465, 2015. URL: http://dx.doi.org/10.1007/978-3-319-32859-1_39.
-
Stefan Schirra. Robustness and precision issues in geometric computation. In Handbook of Computational Geometry, pages 597-632. Elsevier, 2000.
-
Susanne Schmitt. Improved separation bounds for the diamond operator. Report ECG-TR-363108-01, Effective Computational Geometry for Curves and Surfaces, Sophia Antipolis, France, 2004.
- Martin Wilhelm. Balancing expression dags for more efficient lazy adaptive evaluation. In Mathematical Aspects of Computer and Information Sciences - 7th International Conference, MACIS 2017, Vienna, Austria, November 15-17, 2017, Proceedings, pages 19-33, 2017. URL: http://dx.doi.org/10.1007/978-3-319-72453-9_2.
-
Martin Wilhelm. Multithreading for the expression-dag-based number type Real_algebraic. Technical Report FIN-001-2018, Otto-von-Guericke-Universität Magdeburg, 2018.
- Chee-Keng Yap. Towards exact geometric computation. Comput. Geom., 7:3-23, 1997. URL: http://dx.doi.org/10.1016/0925-7721(95)00040-2.
- Jihun Yu, Chee-Keng Yap, Zilin Du, Sylvain Pion, and Hervé Brönnimann. The design of core 2: A library for exact numeric computation in geometry and algebra. In Proceedings of the Third International Congress on Mathematical Software, ICMS, pages 121-141, 2010. URL: http://dx.doi.org/10.1007/978-3-642-15582-6_24.