DROPS

Document

DOI: 10.4230/LIPIcs.SEA.2018.20

Restructuring Expression Dags for Efficient Parallelization

Authors: Martin Wilhelm

Published in: LIPIcs, Volume 103, 17th International Symposium on Experimental Algorithms (SEA 2018)

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.

Cite as

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)

Copy BibTex To Clipboard

@InProceedings{wilhelm:LIPIcs.SEA.2018.20,
  author =	{Wilhelm, Martin},
  title =	{{Restructuring Expression Dags for Efficient Parallelization}},
  booktitle =	{17th International Symposium on Experimental Algorithms (SEA 2018)},
  pages =	{20:1--20:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-070-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{103},
  editor =	{D'Angelo, Gianlorenzo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2018.20},
  URN =		{urn:nbn:de:0030-drops-89551},
  doi =		{10.4230/LIPIcs.SEA.2018.20},
  annote =	{Keywords: exact computation, expression dag, parallel evaluation, restructuring}
}

Search Results

Documents authored by Wilhelm, Martin

Restructuring Expression Dags for Efficient Parallelization

Abstract

Cite as

Thanks for your feedback!

Could not send message