[Back]

M. Kainer:
"More Parallelism in Single-Source Shortest Path Algorithms: Simulation and Implementation";
Supervisor: J. Träff; Institute of Computer Engineering, Research Division of Parallel Computing, 2018; final examination: 2019-01-24.

The single-source shortest path problem is one of the most studied problems in computer science. Nevertheless, it is infamous for being notoriously hard to parallelize due to the so-called transitive closure bottleneck. In 1998 an algorithm called -stepping was proposed to parallelize the single-source shortest path problem. This algorithm formed the basis for further research in even more optimized algorithms, and eventually became to be the de-facto standard in parallelizing the single-source shortest path problem. A second idea by Crauser et al. to parallelize the single-source shortest path problem was published in 1998. This idea did not get a lot of attention, and seems to have been forgotten. The goal of this thesis is to evaluate the viability and performance of Crauser et al.'s approach in comparison to -stepping. Furthermore, several ideas to improve or change this approach are evaluated. In order to do this, these algorithms are first introduced, then proven correct, and finally implemented. There are two implementations of each algorithm. One implementation is to analyze the number of phases each algorithm needs to solve the single-source shortest path problem, a key metric in assessing the quality of such algorithms. The second implementation is optimized to measure the performance on the systems provided by the research group. The phase analysis shows that the improvements to Crauser et al.'s original formulation of their algorithm reduce the number of phases by a large margin, therefore leading to a theoretical gain. Unfortunately, no efficient implementation was found for these improvements, and therefore they cannot enhance real-world performance. Nevertheless, Crauser et al.'s original algorithm performs very well and is competitive to -stepping.

Das Single-Source Shortest Path Problem (kürzester Pfad von einem Startpunkt aus) ist eines der am häufigsten untersuchten Probleme in der Informatik. Allerdings ist das Problem dafür bekannt enorm schwierig parallelisierbar zu sein. Dies liegt vor allem an dem sogenannten Transitive Closure Bottleneck. 1998 wurde ein Algorithmus namens -Stepping vorgeschlagen um das Single-Source Shortest Path Problem zu parallelisieren. Dieser Algorithmus hat als Basis für eine Reihe von zusätzlicher Forschung im Bereich solcher Algorithmen gedient und zählt heute als der Standardalgorithmus zum Parallelisieren des Single-Source Shortest Path Problems. Eine weitere Idee das Single-Source Shortest Path Problem zu parallelisieren wurde von Crauser et al., ebenfalls 1998, publiziert. Diese Idee hat allerdings nie viel Aufmerksamkeit erlangt und ist aus heutiger Sicht nicht mehr sehr bekannt. Das Ziel dieser Arbeit ist es zu evaluieren ob diese Idee eine mögliche Alternative für -Stepping darstellt. Des Weiteren werden verschiedene Möglichkeiten betrachtet diesen Lösungsansatz zu erweitern. Um diese Ziele zu erreichen werden zuerst die Algorithmen eingeführt, danach werden sie als korrekt bewiesen und letztendlich implementiert. Jeder Algorithmus wird zweimal implementiert: Eine Implementierung dient zum Analysieren der Anzahl an Phasen die benötigt werden um das Single-Source Shortest Path Problem zu lösen. Diese Anzahl an Phasen stellt eine wichtige Kennzahl dar um die Qualität solcher Algorithmen zu beurteilen. Die zweite Implementierung dient zur Performancemessung auf den Systemen der Forschungsgruppe. Die Analyse der Phasenanzahl hat ergeben, dass die vorgeschlagenen Erweiterungen der original Formulierung des Algorithmus die Anzahl an Phasen um einiges reduziert und daher zu einer theoretischen Verbesserung des Algorithmus führt. Leider konnte keine effiziente Implementierung dieser Verbesserungen gefunden werden und daher konnte diese theoretische Verbesserung nicht in die Praxis umgesetzt werden. Nichtsdestotrotz hat sich herausgestellt, dass der original Algorithmus von Crauser et al. eine ausgezeichnete Performance im Vergleich zu -Stepping aufweist und daher als Alternative dazu gesehen werden kann.

Parallel algorithms / Single-source shortest path problem / Dijkstra's algorithm / Delta-stepping / Simulation / Benchmarking