Multithread Plattformen für Divide und Conquer und inkrementelle Algorithmen und Anwendungen in der Computational Geometry
Multithread platforms for Divide and Conquer and incremental algorithms and applications to Computational Geometry
- In dieser Arbeit präsentieren wir einen systematischen Ansatz zur Multithread Implementierung von Divide und Conquer sowie inkrementellen Algorithmen. Wir stellen für beide Kategorien von Algorithmen ein Framework vor. Beide Frameworks sollen die Behandlung von Threads erleichtern, die Implementierung von parallelen Algorithmen beschleunigen und die Rechenzeit verringern. Mit Hilfe der Frameworks parallelisieren wir beispielhaft zahlreiche Algorithmen insbesondere aus dem Bereich Computational Geometry, unter anderem: Sortieralgorithmen, konvexe Hülle Algorithmen und Triangulierungen. Der Programmcode zu diese Arbeit ist in C++ unter Verwendung templatisierter Klassen implementiert und basiert auf der LEDA Bibliothek.
- We present a systematical approach for multithread implementations of divide and conquer and incremental algorithms. We introduce a framework for both classes of algorithms. Both frameworks are supposed to improve the usability of threads, to speed up the implementation of parallel algorithms and to reduce computation time. rnWe are using the frameworks to parallelise several algorithms especially from the field of Computational Geometry. These are amongst others: sorting algorithms, convex hull algorithms, and triangulations. The Code is written in C++ by the use of templates. The implementation is based on the LEDA library.
