Parallele All-Pair-Shortest-Paths-Algorithmen

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.

Problembeschreibung

Sei $G=(V,E,w)$ ein gerichteter Graph mit der Knotenmenge $V$ und der Kantenmenge $E\subseteq V\times V$. Jeder Kante $e\in E$ ist ein Gewicht $w(e)$ zugeordnet. Ziel ist es, von allen Knoten die kürzesten Pfade zu jedem anderen Knoten zu bestimmen. Damit dieser eindeutig ist, ist es notwendig, dass es in $G$ keine negativen Zyklen gibt.

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$, deren Einträge $d-{i,j}$ das Gewicht des kürzesten Weges von Knoten $i$ zu Knoten $j$ enthalten.

Der vorgestellte Floyd Algorithmus funktioniert auch mit negativen Gewichten, der Dijkstra-Algorithmus erlaubt nur positive Kantengewichte.

Dijkstra-Algorithmus

→ Hauptartikel: Dijkstra-Algorithmus

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$ und den Startknoten $v$ benötigt. Zurückgegeben wird dann ein Array $d_{v}$ der Distanzen. Das $i$-te Element im Array enthält dabei die Distanz von $v$ zu dem Knoten $i$; Damit entspricht diese Liste genau der $v$-ten Zeile in der APSP-Distanzmatrix $D$. Der Algorithmus zur Lösung des APSP-Problems iteriert dementsprechend über alle Knoten des Graphen $G$, führt jeweils DijkstraSSSP aus und speichert das Ergebnis in der entsprechenden Zeile der Distanzmatrix.

Da wir von einer Repräsentation des Graphen als Adjazenzmatrix ausgehen, benötigt DijkstraSSSP eine Laufzeit von $O(|V|^{2})$. Damit ergibt sich für DijkstraAPSP eine sequentielle Laufzeit von $O(|V|^{3})$.

Parallelisierung für maximal |V| Prozessoren

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|$ für diese Parallelisierung eine Obergrenze für die Anzahl an verwendbaren Prozessoren.

Somit ergibt sich z. B. falls die Anzahl Prozessoren $p$ gleich der Anzahl Knoten $|V|$ ist, dass jeder Prozessor genau einmal den DijkstraSSSP ausführt. Stehen hingegen z. B. nur $p={\frac {|V|}{2}}$ Prozessoren zur Verfügung, so muss jeder Prozessor zweimal DijkstraSSSP aufrufen.

Insgesamt ergibt sich damit eine Laufzeit von $O(|V|^{2}\cdot {\frac {|V|}{p}})$, falls $|V|$ ein Vielfaches von $p$ ist. Die Effizienz dieser Parallelisierung ist damit perfekt: Durch Verwendung von $p$ Prozessoren wird die Laufzeit um den Faktor $p$ reduziert.

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.

Parallelisierung für mehr als |V| Prozessoren

Möchte man mehr als $|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|$ Gruppen aufgeteilt. Jede Gruppe ist für die Berechnung einer Zeile in der Distanzmatrix $D$ verantwortlich, d. h. für das Auswerten von DijkstraSSSP mit einem festen Startknoten. Damit hat jede Gruppe die Größe von $k={\frac {p}{|V|}}$ Prozessoren. Die Ergebnisse der Gruppen sind unabhängig voneinander, daher können diese parallel arbeiten. Die im vorherigen Abschnitt vorgestellte Parallelisierung entspricht daher einer Gruppengröße von 1 bei $p=|V|$ Prozessoren.

Die Hauptschwierigkeit besteht nun darin, dass $k$ Prozessoren die Ausführung von DijkstraSSSP parallelisieren müssen. Die Idee zur Lösung dieses Problems ist die Verwaltung der Distanzliste $d_{v}$ in DijkstraSSSP innerhalb der Gruppe zu verteilen. Jeder Prozessor in der Gruppe ist dementsprechend für ${\frac {|V|}{k}}$ Elemente der Liste exklusiv verantwortlich. Sei z. B. $|V|=4$ und $p=8$. Damit ergibt sich eine Gruppengröße von $k=2$. Dann speichert und verwaltet jeweils der erste Prozessor einer Gruppe $d_{v,1}$, $d_{v,2}$ und der zweite $d_{v,3}$ sowie $d_{v,4}$. Die gesamte Distanzliste ist dabei $d_{v}=[d_{v,1},d_{v,2},d_{v,3},d_{v,4}]$.

DijkstraSSSP besteht im Wesentlichen aus dem Wiederholen von zwei Schritten: Zunächst muss der aktuell nächste Knoten $x$ in der Distanzliste $d_{v}$ gefunden werden. Damit ist nun der kürzeste Weg für $x$ bekannt. Anschließend müssen noch die Entfernungen in $d_{v}$ für alle Nachbarn von $x$ aktualisiert werden.

Bei der Parallelisierung liegt $d_{v}$ nun verteilt vor, daher müssen die Schritte wie folgt angepasst werden:

1. Finde den Knoten $x$ mit aktuell kürzester Distanz in $d_{v}$
   • Jeder Prozessor besitzt einen Teil der Distanzliste $d_{v}$: Finde darin das lokale Minimum ${\tilde {x}}$, z. B. via lineare Suche.
   • Finde das globale Minimum $x$ in $d_{v}$ mittels einer Reduktion-Operation über alle ${\tilde {x}}$ wird $x$.
   • Teile das globale Minimum $x$ wieder allen Prozessoren der Gruppe mit über eine Broadcast-Operation.
2. Aktualisiere die Entfernungen in $d_{v}$ für alle Nachbarn von $x$
   • Jeder Knoten kennt jetzt den nächsten Knoten $x$ sowie dessen Entfernung zum Startknoten. Damit kann er die von ihm verwalteten Nachbarn in $d_{v}$ aktualisieren.

Der Gesamtaufwand einer solchen Iteration von DijkstraSSSP durch eine Gruppe der Größe $k$ setzt sich entsprechend wie folgt zusammen:

• lineare Suche nach ${\tilde {x}}$: $O({\frac {|V|}{k}})$
• Broadcast und Reduktion: Diese lassen sich z. B. effizient über Binomialbäume realisieren, was jeweils einem Kommunikationsaufwand von etwa $O(\log k)$ entspricht.

Für $|V|$-Iterationen ergibt sich damit eine Gesamtlaufzeit in $O(|V|({\frac {|V|}{k}} \log k))$. Setzt man nun die Definition von $k$ ein, ergibt sich für DijkstraAPSP eine Laufzeit von $O({\frac {|V|^{3}}{p}} \log p)$.

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$ muss somit jeder Prozessor nur ${\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

Gegeben sei der im Bild illustrierte Beispielgraph mit vier Knoten.

Nun soll die Distanzmatrix mithilfe von $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 $d_{A}$ ist im nachfolgenden Bild dargestellt.

Die oberste Zeile entspricht $d_{A}$ nach der Initialisierung, die unterste $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 $d_{A}$ auf beide Prozessoren verteilt. Für die zweite Iteration des Algorithmus sind exemplarisch die Teilschritte explizit dargestellt:

1. Berechnung des lokal nächsten Knotens in $d_{A}$
2. Berechnung des global nächsten Knotens in $d_{A}$ durch eine Reduktions-Operation.
3. Bekanntgabe des global nächsten Knotens in $d_{A}$ durch eine Broadcast-Operation.
4. Markieren des global nächsten Knotens in $d_{A}$ als „fertig“ sowie Aktualisierung der Entfernungen seiner Nachbarn in $d_{A}$.

Floyd-Algorithmus

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)}$ = A;
 3        for k := 1 to n do
 4            for i := 1 to n do
 5                for j := 1 to n do
 6                    $d_{i,j}^{(k)}:=min(d_{i,j}^{(k-1)},d_{i,k}^{(k-1)} d_{k,j}^{(k-1)})$
 7     }

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.

Parallelisierung

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\times n$- Matrix und p Prozessoren berechnet dabei jeder Prozessor einen $n/{\sqrt {(}}p)\times n/{\sqrt {(}}p)$ großen Abschnitt der Matrix. Abbildung 1 zeigt eine solche Aufteilung. Mit $p=n^{2}$ Prozessoren würde dabei jeder Prozessor genau einen Eintrag berechnen. Der Algorithmus skaliert dadurch nur bis zu einer maximalen Anzahl von $n^{2}$ Prozessoren. Mit $p_{i,j}$ bezeichnen wir im Folgenden den Prozessor der dem Quadrat der i-ten Zeile und j-ten Spalte zugeordnet ist.

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 $d_{i,j}^{(k)}$ den Eintrag der Zeile i und Spalte j der Matrix nach der k-ten Iteration. Um $d_{i,j}^{(k)}$ zu berechnen werden wie in Zeile 6 des Algorithmus angegeben $d_{i,j}^{(k-1)}$, $d_{i,k}^{(k-1)}$ und $d_{k,j}^{(k-1)}$ benötigt. $d_{i,j}^{(k-1)}$ hat jeder Prozessor zur Verfügung, da er es in der vorherigen Iteration selbst berechnet hat.

Zusätzlich braucht jeder Prozessor noch einen Teil der k-ten Reihe und der k-ten Spalte aus der $D^{k-1}$ Matrix. $d_{i,k}^{(k-1)}$ liegt dabei auf einem Prozessor in der gleichen Spalte und $d_{k,j}^{(k-1)}$ auf einem Prozessor in der gleichen Zeile wie der Prozessor der $d_{i,j}^{(k)}$ berechnen muss. Jeder Prozessor, der in $D^{k-1}$ einen Teil der k-ten Reihe berechnet hat, sendet diesen Teil also an alle Prozessoren in seiner Spalte. Jeder Prozessor, der in $D^{k-1}$ einen Teil der k-ten Spalte berechnet hat, sendet diesen an alle Prozessoren aus der gleichen Reihe. All diese Prozessoren führen also eine one-to-all-Broadcast Operation entlang der Zeile bzw. Spalte der Prozessoren aus. Diese Operation ist in Abbildung 2 veranschaulicht.

Damit ergibt sich für die Variante mit 2-D Block Mapping folgender Algorithmus:

 1    func Floyd_All_Pairs_Parallel($D^{(0)}$) {
 2      for k := 1 to n do{
 3          Jeder Prozessor $p_{i,j}$, der einen Teil der k-ten Reihe von $D^{(k-1)}$ hat,
            broadcastet diesen zu den Prozessoren $p_{*,j}$;
 4          Jeder Prozessor $p_{i,j}$, der einen Teil der k-ten Spalte von $D^{(k-1)}$ hat,
            broadcastet diesen zu den Prozessoren $p_{i,*}$;
 5          Jeder Prozessor wartet, bis die benötigten Daten vorhanden sind;
 6          Jeder Prozessor berechnet seinen Teil der $D^{(k)}$ matrix;
 7          }
 8     }

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.

Laufzeit

Die Laufzeit des sequentiellen Algorithmus wird durch die drei verschachtelten for-Schleifen dominiert. Die Berechnung in Zeile 6 kann in konstanter Zeit ($O(1)$) ausgeführt werden. Damit ergibt sich eine Laufzeit von $O(n^{3})$ für den sequentiellen Algorithmus.

2-D Block Mapping

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.

Da bei dem Verfahren keine zusätzlichen Berechnungen entstehen und sich die Berechnungen zu gleichen Teilen auf die p Prozessoren verteilen, haben wir für diesen Teil eine Laufzeit von $O(n^{3}/p)$.

In jeder Iteration des Algorithmus wird eine one-to-all Broadcast Operation mit $n/{\sqrt {p}}$ Elementen entlang der Zeile bzw. Spalte der Prozessoren ausgeführt. Anschließend wird ein Synchronisationsschritt durchgeführt. Wie viel Zeit diese Operationen benötigen, hängt von der Architektur des verwendeten Parallelrechners ab. Für Datenaustausch und Kommunikation wird dadurch $T_{Kommunikation}=n(T_{synch} T_{broadcast})$ zusätzliche Zeit benötigt.

Insgesamt ergibt sich damit eine Laufzeit von:

$T_{Gesamt}=O(n^{3}/p) n(T_{synch} T_{broadcast})$

Pipelined 2-D Block Mapping

Für die Laufzeit des Datenaustauschs zwischen den Prozessoren in der pipelined Version des Algorithmus gehen wir davon aus, dass ein Prozessor k Datenobjekte in O(k) Zeit zu einem benachbarten Prozessor übertragen kann. In jedem Schritt werden $n/{\sqrt {p}}$ Elemente einer Reihe an die benachbarten Prozessoren gesendet. Analog dazu werden $n/{\sqrt {p}}$ Elemente einer Spalte zu den benachbarten Prozessoren gesendet. Für einen solchen Schritt wird O($n/{\sqrt {p}}$) Zeit benötigt. Nach ${\sqrt {p}}$ Schritten sind die relevanten Daten der ersten Reihe und Spalte dann bei Prozessor $p_{{\sqrt {p}},{\sqrt {p}}}$ angekommen. Also nach O(n) Zeit.

Die Daten der weiteren Reihen und Spalten kommen dann sukzessiv nach O($n^{2}/p$) Zeit und können pipelineartig bearbeitet werden. $p_{{\sqrt {p}},{\sqrt {p}}}$ beendet seine letzte Iteration dadurch nach O($n^{3}/p$) O($n$) Zeit. Die zusätzliche Zeit die für den Datenaustausch benötigt wird beträgt damit O($n$).

Damit ergibt sich folgende Gesamtlaufzeit für pipelined 2-d Block Mapping:

$T_{Gesamt}=O(n^{3}/p) O(n)$

Literatur

• A. Grama: Introduction to parallel computing. Pearson Education, 2003.
• V. Kumar: Scalability of Parallel Algorithms for the All-Pairs Shortest-Path Problem. Journal of Parallel and Distributed Programming 13, 1991.
• I. Foster: Designing and Building Parallel Programs (Online).
• Bindell, Fall: Parallel All-Pairs Shortest Paths Applications of Parallel Computers, 2011.