Beschreibung

Das Minimum Spanning Tree (MST) Problem sucht für einen (kanten-)gewichteten
Eingabegraphen G = (V, E) nach einem Baum T = (V, E' ⊆ E), welcher alle
Knoten aus V verbindet und minimales Gewicht besitzt. Das MST Problem zählt
zu den fundamentalsten Graphenproblemen überhaupt und bietet Raum für viele
algorithmische Ansätze.
Neben seiner Bedeutung in der Algorithmentheorie ist das Problem auch in der
Praxis relevant und findet bspw. in den Bereichen Bildsegmentierung, Netzwerk-
planung und Clustering breite Anwendung.
In unserer aktuellen Forschung [2] beschäftigen wir uns mit der Frage, wie MSTs auf
Supercomputer mit mehreren zehntausend Prozessoren effizient berechnet werden
können. Solche Supercomputer sind verteilte Systeme, in welchen die Prozessoren
nicht über den geteilten Speicher (shared-memory), sondern mittels dedizierten
Nachrichten über Hochleistungsnetzwerke, wie z.B. InfiniBand kommunizieren.
Dadurch ergeben sich deutlich andere Anforderungen an effiziente Algorithmen
als in herkömmlichen shared-memory Systemen.

Thema der Arbeit

Ziel der Arbeit ist die Entwicklung und praktische Evaluation von massiv parallelen
MST Algorithmen auf dichten Graphen mit |V | ≤ |E|/p (p ist hier die Prozessorenzahl).
Da durch diese Bedingung die Anzahl an Kanten um den Faktor p größer ist als die
Knotenmenge, kann die Knotenmenge auf allen Prozessoren repliziert werden,
was zu deutlichen
Kommunikationseinsparungen und Vereinfachungen im Algorithmus führen kann.

In einer Literaturrecherche ausgehend von [2, 1] sollen zunächst die besten beste-
henden Ansätze gesammelt und weiterentwickelt werden. Die Implementierung
erfolgt in C++ unter Verwendung von MPI. Die Evaluation erfolgt auf Supercompu-
tern mit bis zu 300 000 Prozessoren.

Voraussetzungen

• Interesse an parallelen Algorithmen
• Gute Programmierkenntnisse in (modernem) C++

Literatur

[1] Frank K. H. A. Dehne and Silvia Götz. “Practical Parallel Algorithms for Minimum Spanning Trees”. In:
17th Symposium on Reliable Distributed Systems, SRDS. IEEE Computer Society, 1998, pp. 366–371. url:
https://doi.org/10.1109/RELDIS.1998.740525.

[2] Peter Sanders and Matthias Schimek. “Engineering Massively Parallel MST Algorithms”. In: CoRR (2023).
arXiv: 2302.12199. url: https://doi.org/10.48550/arXiv.2302.12199.