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.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Daniel Schmitt
URN:urn:nbn:de:hbz:385-8499
Advisor:Stefan Näher
Document Type:Doctoral Thesis
Language:German
Date of completion:2014/03/27
Publishing institution:Universität Trier
Granting institution:Universität Trier, Fachbereich 4
Date of final exam:2013/11/28
Release Date:2014/03/27
Tag:computational geometry; convex hull; divide and conquer; incremental algorithm; multicore
GND Keyword:computational geometry; convex hull; divide and conquer; incremental algorithm; multicore
Institutes:Fachbereich 4 / Informatik
Dewey Decimal Classification:0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik

$Rev: 13581 $