Parallele All-Pair-Shortest-Paths-Algorithmen sind Algorithmen in der Graphentheorie, um kürzeste Wege zwischen zwei Knoten zu finden. Die kürzesten Wege zwischen allen Knoten in einem Graphen zu finden, bezeichnet man als All-Pairs-Shortest-Path-Problem. Da bei sequentiellen Algorithmen, die dieses Problem lösen, große Graphen zu langen Laufzeiten führen, lohnt es sich diese zu parallelisieren. Hier werden Techniken zur Parallelisierung für die bekanntesten Algorithmen und deren Auswirkungen auf die Laufzeiten vorgestellt.
Sei G=(V,E,w){\displaystyle G=(V,E,w)}
Wir gehen im Folgenden davon aus, dass der Graph zu Beginn der Algorithmen in Form einer Adjazenzmatrix vorliegt. Als Ergebnis der Algorithmen erwarten wir die Distanzmatrix D{\displaystyle D}
Der vorgestellte Floyd Algorithmus funktioniert auch mit negativen Gewichten, der Dijkstra-Algorithmus erlaubt nur positive Kantengewichte.
Der Dijkstra-Algorithmus ist eigentlich ein Algorithmus zur Lösung des Single-Source-Shortest-Path-Problems. Er lässt sich damit jedoch zur Lösung des All-Pair-Shortest-Paths Problems nutzen, indem er für jeden Knoten im Graphen als Startknoten ausgeführt wird.
In Pseudocode könnt somit eine entsprechende Implementierung so aussehen:
1 func DijkstraSSSP(G,v) { 2 ... //Standard SSSP-Implementierung hier 3 return dv; 4 } 5 6 func DijkstraAPSP(G) { 7 D := |V|x|V|-Matrix 8 for i from 1 to |V| { 9 //D[v] bezeichnet die v-te Zeile von D 10 D[v] := DijkstraSSP(G,i) 11 } 12 }In diesem Beispiel wird angenommen, dass DisjktraSSSP als Eingabe den Graphen G{\displaystyle G} und den Startknoten v{\displaystyle v}
Da wir von einer Repräsentation des Graphen als Adjazenzmatrix ausgehen, benötigt DijkstraSSSP eine Laufzeit von O(|V|2){\displaystyle O(|V|^{2})}
Eine einfache Parallelisierung ergibt sich durch das Verteilen der Schleife von DijkstraAPSP in Zeile 8. Dies ist jedoch bei Verwendung des sequentiellen DijkstraSSSP nur möglich, wenn sich daran höchstens so viele Prozessoren beteiligen, wie die Schleife Durchläufe hat. Damit ist |V|{\displaystyle |V|}
Somit ergibt sich z. B. falls die Anzahl Prozessoren p{\displaystyle p}
Insgesamt ergibt sich damit eine Laufzeit von O(|V|2⋅|V|p){\displaystyle O(|V|^{2}\cdot {\frac {|V|}{p}})}
Diese Parallelisierung besitzt einen weiteren Vorteil: Es findet keinerlei Kommunikation zwischen den Prozessoren statt. Eine Ausnahme bildet das eventuelle Verteilen des Graphen vor der Berechnung oder das Einsammeln der Ergebnisse danach. Allerdings wird vorausgesetzt, dass jeder Prozessor genügend Speicher besitzt, um die Adjazenzmatrix des Graphen vollständig zu speichern.
Möchte man mehr als |V|{\displaystyle |V|} Prozessoren zur Parallelisierung verwenden, so müssen sich von diesen mehrere gleichzeitig an der Berechnung von DijkstraSSSP beteiligen. Aus diesem Grund findet diese Parallelisierung über mehrere Ebenen statt.
Zunächst werden die Prozesse in |V|{\displaystyle |V|} Gruppen aufgeteilt. Jede Gruppe ist für die Berechnung einer Zeile in der Distanzmatrix D{\displaystyle D} verantwortlich, d. h. für das Auswerten von DijkstraSSSP mit einem festen Startknoten. Damit hat jede Gruppe die Größe von k=p|V|{\displaystyle k={\frac {p}{|V|}}}
Die Hauptschwierigkeit besteht nun darin, dass k{\displaystyle k}
DijkstraSSSP besteht im Wesentlichen aus dem Wiederholen von zwei Schritten: Zunächst muss der aktuell nächste Knoten x{\displaystyle x}
Bei der Parallelisierung liegt dv{\displaystyle d_{v}} nun verteilt vor, daher müssen die Schritte wie folgt angepasst werden:
- Finde den Knoten x{\displaystyle x} mit aktuell kürzester Distanz in dv{\displaystyle d_{v}}
- Jeder Prozessor besitzt einen Teil der Distanzliste dv{\displaystyle d_{v}}: Finde darin das lokale Minimum x~{\displaystyle {\tilde {x}}}, z. B. via lineare Suche.
- Finde das globale Minimum x{\displaystyle x} in dv{\displaystyle d_{v}} mittels einer Reduktion-Operation über alle x~{\displaystyle {\tilde {x}}} wird x{\displaystyle x}.
- Teile das globale Minimum x{\displaystyle x} wieder allen Prozessoren der Gruppe mit über eine Broadcast-Operation.
- Jeder Prozessor besitzt einen Teil der Distanzliste dv{\displaystyle d_{v}}: Finde darin das lokale Minimum x~{\displaystyle {\tilde {x}}}
- Aktualisiere die Entfernungen in dv{\displaystyle d_{v}} für alle Nachbarn von x{\displaystyle x}
- Jeder Knoten kennt jetzt den nächsten Knoten x{\displaystyle x} sowie dessen Entfernung zum Startknoten. Damit kann er die von ihm verwalteten Nachbarn in dv{\displaystyle d_{v}} aktualisieren.
Der Gesamtaufwand einer solchen Iteration von DijkstraSSSP durch eine Gruppe der Größe k{\displaystyle k} setzt sich entsprechend wie folgt zusammen:
- lineare Suche nach x~{\displaystyle {\tilde {x}}}: O(|V|k){\displaystyle O({\frac {|V|}{k}})}
- Broadcast und Reduktion: Diese lassen sich z. B. effizient über Binomialbäume realisieren, was jeweils einem Kommunikationsaufwand von etwa O(logk){\displaystyle O(\log k)}entspricht.
Für |V|{\displaystyle |V|}-Iterationen ergibt sich damit eine Gesamtlaufzeit in O(|V|(|V|k+logk)){\displaystyle O(|V|({\frac {|V|}{k}}+\log k))}
Ein Vorteil dieser Parallelisierung ist, dass nicht mehr jeder Prozessor den vollständigen Graph speichern muss. Es ist ausreichend, wenn in jeder Gruppe jeder Prozessor nur die Spalten der Adjazenzmatrix speichert, welche zu den Knoten gehören, für die der Prozessor verantwortlich ist. Bei einer Gruppengröße von k{\displaystyle k} muss somit jeder Prozessor nur |V|k{\displaystyle {\frac {|V|}{k}}} Spalten der Adjazenzmatrix speichern. Dieser Vorteil steht jedoch dem Nachteil gegenüber, dass die Prozessoren miteinander kommunizieren müssen um das Gesamtergebnis zu erhalten.
Beispiel[Bearbeiten | Quelltext bearbeiten]
Gegeben sei der im Bild illustrierte Beispielgraph mit vier Knoten.
Nun soll die Distanzmatrix mithilfe von p=8{\displaystyle p=8} Prozessoren berechnet werden. Daher werden vier Gruppen gebildet, die jeweils zwei Prozessoren beinhalten. Betrachten wir nun die Gruppe, welche für die Berechnung der kürzesten Pfade von Knoten A aus zuständig ist. Die beteiligten Prozessoren seien p1 und p2.
Der Verlauf der Berechnung der Distanzliste dA{\displaystyle d_{A}}
Die oberste Zeile entspricht dA{\displaystyle d_{A}} nach der Initialisierung, die unterste dA{\displaystyle d_{A}} nach Beendigung des Algorithmus. Außerdem ist die Verteilung so gestaltet, dass p1 für die Knoten A und B, sowie p2 für die Knoten C und D zuständig ist. Dementsprechend ist dA{\displaystyle d_{A}} auf beide Prozessoren verteilt. Für die zweite Iteration des Algorithmus sind exemplarisch die Teilschritte explizit dargestellt:
- Berechnung des lokal nächsten Knotens in dA{\displaystyle d_{A}}
- Berechnung des global nächsten Knotens in dA{\displaystyle d_{A}} durch eine Reduktions-Operation.
- Bekanntgabe des global nächsten Knotens in dA{\displaystyle d_{A}} durch eine Broadcast-Operation.
- Markieren des global nächsten Knotens in dA{\displaystyle d_{A}} als "fertig" sowie Aktualisierung der Entfernungen seiner Nachbarn in dA{\displaystyle d_{A}}.
Der Floyd Algorithmus löst das All-Pairs Shortest Path Problem für Graphen. Er basiert auf der Berechnung einer |V| x |V|-Matrix, bei der die Einträge der Matrix die Länge der Pfade zwischen zwei Knoten beschreiben. Iterativ werden kürzere Pfade berechnet, sodass die Matrix am Ende die kürzesten Pfade enthält. Der folgende Pseudocode beschreibt eine sequentielle Variante des Floyd Algorithmus:
1 func Floyd_All_Pairs_SP(A) { 2 D ( 0 ) {\displaystyle D^{(0)}}A ist dabei die Adjazenzmatrix des Graphen, n = |V| die Anzahl der Knoten und D die Distanzmatrix. Für mehr Details zum sequentiellen Algorithmus sei an dieser Stelle auf Algorithmus von Floyd und Warshall verwiesen.
Aufteilung einer Matrix auf Prozessoren nach dem 2-D Block Mapping
Die Grundidee zur Parallelisierung des Algorithmus ist es, die Berechnung der Matrix auf die Prozessoren zu verteilen. Jedem Prozessor wird dazu ein gleich großer Teil der Matrix zugeordnet. Eine übliche Methode, um dies zu erreichen, ist das 2-D Block Mapping. Die Matrix wird dabei in Quadrate aufgeteilt und jedem Prozessor ein Quadrat zugewiesen. Bei einer n×n{\displaystyle n\times n}
Da die Berechnungen der einzelnen Teile der Matrix von Ergebnissen aus anderen Bereichen abhängen, müssen die Prozessoren zwischen den Iterationen untereinander kommunizieren und Daten austauschen. Im Folgenden beschreiben wir mit di,j(k){\displaystyle d_{i,j}^{(k)}}
Zusätzlich braucht jeder Prozessor noch einen Teil der k-ten Reihe und der k-ten Spalte aus der Dk−1{\displaystyle D^{k-1}}
Damit ergibt sich für die Variante mit 2-D Block Mapping folgender Algorithmus:
1 func Floyd_All_Pairs_Parallel( D ( 0 ) {\displaystyle D^{(0)}} ) { 2 for k := 1 to n do{ 3 Jeder Prozessor p i , j {\displaystyle p_{i,j}} der einen Teil der k-ten Reihe von D ( k − 1 ) {\displaystyle D^{(k-1)}}Datenabhängigkeiten beim parallelen Floyd Algorithmus
In Zeile 5 des Algorithmus haben wir einen Synchronisationsschritt. Dieser stellt sicher, dass alle benötigten Daten für die nächste Iteration bei jedem Prozessor vorliegen. Um die Laufzeit zu verbessern, kann man diesen Synchronisationsschritt entfernen, ohne dabei die Korrektheit des Algorithmus zu beeinflussen. Um dies zu erreichen, beginnt jeder Prozessor sofort mit der Berechnung sobald die für seinen Teil der Matrix relevanten Teile bei ihm vorhanden sind. Diese Variante der Parallelisierung wird als Pipelined 2-D Block Mapping bezeichnet.
Die Laufzeit des sequentiellen Algorithmus wird durch die drei verschachtelten for-Schleifen dominiert. Die Berechnung in Zeile 6 kann in konstanter Zeit (O(1){\displaystyle O(1)}
2-D Block Mapping[Bearbeiten | Quelltext bearbeiten]
Die Laufzeit des parallelisierten Algorithmus setzt sich aus zwei Teilen zusammen. Die Zeit für die Berechnungen und die Zeit für den Datenaustausch und die Kommunikation zwischen den Prozessoren.