Parallele Breitensuche

Grundidee und Bedeutung

Die parallele Breitensuche, englisch parallel breadth-first search (BFS), ist eine Variante des Breitensuche-Algorithmus für Graphen. Ein Graph besteht aus Knoten und Kanten; die Breitensuche besucht von einem Ausgangsknoten aus alle erreichbaren Knoten. Dabei werden Knoten mit geringerer Distanz zum Ausgangsknoten vor Knoten mit größerer Distanz besucht. Bei der parallelen Breitensuche wird diese Arbeit nebenläufig auf mehrere Prozessoren verteilt.

Sie ist wichtig, weil sie als Grundlage für viele weitere Graphalgorithmen dient, besonders bei der Analyse großer Datenbestände. Mit Breitensuche lassen sich zum Beispiel maximaler Fluss, Zusammenhangskomponenten oder Zentralitätsmaße in Graphen bestimmen. Außerdem wird sie im Graph500-Benchmark verwendet, um die Leistung von Supercomputern bei der Verarbeitung großer Datenmengen zu vergleichen. Eine ähnliche Variante ist Green500, bei der die Leistung im Verhältnis zum Stromverbrauch bewertet wird.

Speicher und Kommunikation

Für parallele Algorithmen ist entscheidend, wie Speicher organisiert ist und wie Prozesse miteinander kommunizieren.

Beim gemeinsamen Speicher, auch Shared Memory, können alle Prozessoren auf denselben geteilten Hauptspeicher zugreifen. Dadurch können gemeinsame Datenstrukturen wie Wartelisten oder Markierungen für besuchte Knoten direkt gemeinsam genutzt werden, müssen aber synchronisiert werden.

Beim verteilten Speicher, auch Distributed Memory, besitzt jeder Prozessor einen eigenen lokalen Speicher, der von den Speichern der anderen Prozessoren getrennt ist. Daten müssen dann durch Nachrichten zwischen Prozessoren ausgetauscht werden. Dieses Modell macht Kommunikation ausdrücklich notwendig, wenn ein Prozessor Informationen über Knoten oder Kanten benötigt, die einem anderen Prozessor zugeordnet sind.

Level-basierte Breitensuche

Die sequenzielle Breitensuche wird meistens mit einer FIFO-Queue umgesetzt. FIFO bedeutet „first in, first out“: Das zuerst eingefügte Element wird zuerst wieder entnommen. Eine level-basierte Variante arbeitet mit zwei Wartelisten: der aktuellen Warteliste Q_c und der neuen Warteliste Q_n.

Der Ablauf ist: Zuerst werden alle Knoten als nicht besucht markiert. Dann wird ein Startknoten s gewählt, in Q_c eingefügt und als besucht markiert. Solange Q_c nicht leer ist, wird ein Knoten k aus Q_c entfernt. Alle mit k verbundenen, noch nicht besuchten Knoten werden in Q_n eingefügt und als besucht markiert. Wenn Q_n nicht leer ist, werden Q_c und Q_n getauscht, und der Ablauf wird fortgesetzt.

Die zentrale Schleifeninvariante lautet: Bei der i-ten Durchführung von Schritt 3 befinden sich alle Knoten mit der Distanz i-1 vom Startknoten in Q_c, also im aktuellen Level. In Schritt 4 befinden sich alle Knoten mit der Distanz i in Q_n, also im nächsten Level. Weil der Algorithmus vom aktuellen Level aus nach weiteren Knoten sucht, heißt diese Variante Top-down-Algorithmus. Wenn das aktuelle Level sehr viele Knoten enthält, kann eine Bottom-up-Variante sinnvoll sein; dabei werden alle bisher noch nicht besuchten Knoten betrachtet. Top-down und Bottom-up können auch zu einem Hybrid-Algorithmus kombiniert werden.

Für eine parallele Ausführung kann die Schleife auf mehrere Prozesse aufgeteilt werden. Dabei müssen die aktuelle Warteliste Q_c und die Datenstruktur für den Besuchszustand der Knoten synchronisiert werden. Ohne weitere Anpassung ist dieser Algorithmus nur im Shared-Memory-Modell möglich.

Partitionierung im verteilten Speicher

Um Breitensuche mit verteiltem Speicher parallel auszuführen, kann der Graph partitioniert werden. Partitionierung bedeutet, dass jedem Prozess ein eigener Teil der Knoten oder Kanten zugeordnet wird. Dadurch kann jeder Prozess lokal an seinem Teil arbeiten, muss aber mit anderen Prozessen kommunizieren, sobald Kanten oder Zustände über Partitionsgrenzen hinweg relevant werden.

Bei der 1D-Partitionierung werden im einfachsten Fall jedem der p Prozesse n/p Knoten mit allen ausgehenden Kanten zugeordnet. Dabei steht n für die Anzahl der Knoten und p für die Anzahl der Prozesse. Jeder Prozessor speichert den Zustand der ihm zugewiesenen Knoten in seinem eigenen Speicher. Nach jedem Schritt muss zwischen Prozessoren kommuniziert werden, weil ausgehende Kanten nicht zwingend zu Knoten führen, die demselben Prozessor gehören. Da potenziell jeder Prozessor jedem anderen eine Nachricht senden muss, wird All-to-all-Kommunikation verwendet.

2D-Partitionierung mit Matrizen

Viele Graphen besitzen im Vergleich zur Anzahl der Knoten nur wenige Kanten. Stellt man einen solchen Graphen als Adjazenzmatrix dar, entsteht eine dünn besetzte Matrix. Eine Adjazenzmatrix beschreibt, welche Knoten durch Kanten verbunden sind. Werden die Knoten des aktuellen Levels als Vektor dargestellt, kann ein Schritt der Breitensuche als Multiplikation dieses Vektors mit der Adjazenzmatrix aufgefasst werden.

Die Multiplikation eines dünnbesetzten Vektors mit einer dünnbesetzten Matrix heißt Sparse Matrix Vector Multiplication, kurz SpMV. Sie lässt sich effizient umsetzen. Für die 2D-Partitionierung wird die Adjazenzmatrix in mehrere Untermatrizen aufgeteilt. Jede Untermatrix steht für einen Teil der Kanten im Graphen, und jeder Prozessor bearbeitet einen eigenen Teil der Adjazenzmatrix.

Der Vorteil gegenüber der 1D-Partitionierung liegt in der Kommunikation: Ein Prozessor muss nur mit Prozessoren in derselben Reihe und derselben Spalte der Matrixaufteilung kommunizieren, nicht mit allen anderen Prozessoren. Dafür sind pro Ebene zwei Kommunikationsschritte notwendig statt nur eines.

Beispiel zur 2D-Partitionierung

Im Beispiel wird eine 4×4-Adjazenzmatrix A betrachtet. Sie wird mit C=2 Spalten und R=2 Zeilen in vier Untermatrizen zerlegt. Da die ursprüngliche Matrix 4×4 groß ist, hat jede Untermatrix 2 Zeilen und 2 Spalten. Die vier Teilmatrizen heißen A_1,1, A_1,2, A_2,1 und A_2,2 und werden jeweils einem Prozessor zugeordnet.

Für einen Berechnungsschritt wird der Prozessor betrachtet, der A_1,1 besitzt. Dieser Teil enthält im Graphen die Kante zwischen Knoten 1 und 2. Der Prozessor benötigt zuerst einen Vektor v mit zwei Elementen, der angibt, ob Knoten 1 und 2 im vorherigen Schritt der Breitensuche besucht wurden. Um den aktuellen Zustand von v zu erhalten, kommuniziert A_1,1 mit den Prozessoren derselben Spalte; im Beispiel mit A_2,1.

Danach wird v mit A_1,1 multipliziert. Ist v = (1, 0)^T, bedeutet das, dass Knoten 1 im vorherigen Schritt besucht wurde. Dann gilt A_1,1 × v = (0, 1)^T. Die Eins in der zweiten Komponente zeigt, dass im nächsten Schritt Knoten 2 besucht wird.

Das Ergebnis der Matrix-Vektor-Multiplikation wird anschließend mit allen Prozessoren in derselben Zeile ausgetauscht. So wird der Besuchszustand der Knoten abgeglichen, und Konflikte werden gelöst, falls mehrere Prozessoren denselben Knoten besuchen. Danach beginnt der Vorgang erneut.