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

Bearbeiten

Sei   ein gerichteter Graph mit der Knotenmenge   und der Kantenmenge  . Jeder Kante   ist ein Gewicht   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   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  , deren Einträge   das Gewicht des kürzesten Weges von Knoten   zu Knoten   enthalten.

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

Dijkstra-Algorithmus

Bearbeiten

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   und den Startknoten   benötigt. Zurückgegeben wird dann ein Array   der Distanzen. Das  -te Element im Array enthält dabei die Distanz von   zu dem Knoten  ; Damit entspricht diese Liste genau der  -ten Zeile in der APSP-Distanzmatrix  . Der Algorithmus zur Lösung des APSP-Problems iteriert dementsprechend über alle Knoten des Graphen  , 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  . Damit ergibt sich für DijkstraAPSP eine sequentielle Laufzeit von  .

Parallelisierung für maximal |V| Prozessoren

Bearbeiten

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

Somit ergibt sich z. B. falls die Anzahl Prozessoren   gleich der Anzahl Knoten   ist, dass jeder Prozessor genau einmal den DijkstraSSSP ausführt. Stehen hingegen z. B. nur   Prozessoren zur Verfügung, so muss jeder Prozessor zweimal DijkstraSSSP aufrufen.

Insgesamt ergibt sich damit eine Laufzeit von  , falls   ein Vielfaches von   ist. Die Effizienz dieser Parallelisierung ist damit perfekt: Durch Verwendung von   Prozessoren wird die Laufzeit um den Faktor   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

Bearbeiten
 
 

Möchte man mehr als   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   Gruppen aufgeteilt. Jede Gruppe ist für die Berechnung einer Zeile in der Distanzmatrix   verantwortlich, d. h. für das Auswerten von DijkstraSSSP mit einem festen Startknoten. Damit hat jede Gruppe die Größe von   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   Prozessoren.

Die Hauptschwierigkeit besteht nun darin, dass   Prozessoren die Ausführung von DijkstraSSSP parallelisieren müssen. Die Idee zur Lösung dieses Problems ist die Verwaltung der Distanzliste   in DijkstraSSSP innerhalb der Gruppe zu verteilen. Jeder Prozessor in der Gruppe ist dementsprechend für   Elemente der Liste exklusiv verantwortlich. Sei z. B.   und  . Damit ergibt sich eine Gruppengröße von  . Dann speichert und verwaltet jeweils der erste Prozessor einer Gruppe  ,   und der zweite   sowie  . Die gesamte Distanzliste ist dabei  .

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

Bei der Parallelisierung liegt   nun verteilt vor, daher müssen die Schritte wie folgt angepasst werden:

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

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

  • lineare Suche nach  :  
  • Broadcast und Reduktion: Diese lassen sich z. B. effizient über Binomialbäume realisieren, was jeweils einem Kommunikationsaufwand von etwa   entspricht.

Für  -Iterationen ergibt sich damit eine Gesamtlaufzeit in  . Setzt man nun die Definition von   ein, ergibt sich für DijkstraAPSP eine Laufzeit von  .

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

Gegeben sei der im Bild illustrierte Beispielgraph mit vier Knoten.

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

Die oberste Zeile entspricht   nach der Initialisierung, die unterste   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   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  
  2. Berechnung des global nächsten Knotens in   durch eine Reduktions-Operation.
  3. Bekanntgabe des global nächsten Knotens in   durch eine Broadcast-Operation.
  4. Markieren des global nächsten Knotens in   als „fertig“ sowie Aktualisierung der Entfernungen seiner Nachbarn in  .

Floyd-Algorithmus

Bearbeiten

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          = A;
 3        for k := 1 to n do
 4            for i := 1 to n do
 5                for j := 1 to n do
 6                     
 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

Bearbeiten
 
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  - Matrix und p Prozessoren berechnet dabei jeder Prozessor einen   großen Abschnitt der Matrix. Abbildung 1 zeigt eine solche Aufteilung. Mit   Prozessoren würde dabei jeder Prozessor genau einen Eintrag berechnen. Der Algorithmus skaliert dadurch nur bis zu einer maximalen Anzahl von   Prozessoren. Mit   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   den Eintrag der Zeile i und Spalte j der Matrix nach der k-ten Iteration. Um   zu berechnen werden wie in Zeile 6 des Algorithmus angegeben  ,   und   benötigt.   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   Matrix.   liegt dabei auf einem Prozessor in der gleichen Spalte und   auf einem Prozessor in der gleichen Zeile wie der Prozessor der   berechnen muss. Jeder Prozessor, der in   einen Teil der k-ten Reihe berechnet hat, sendet diesen Teil also an alle Prozessoren in seiner Spalte. Jeder Prozessor, der in   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( ) {
 2      for k := 1 to n do{
 3          Jeder Prozessor  , der einen Teil der k-ten Reihe von   hat,
            broadcastet diesen zu den Prozessoren  ;
 4          Jeder Prozessor  , der einen Teil der k-ten Spalte von   hat,
            broadcastet diesen zu den Prozessoren  ;
 5          Jeder Prozessor wartet, bis die benötigten Daten vorhanden sind;
 6          Jeder Prozessor berechnet seinen Teil der   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

Bearbeiten

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

2-D Block Mapping

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.

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  .

In jeder Iteration des Algorithmus wird eine one-to-all Broadcast Operation mit   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   zusätzliche Zeit benötigt.

Insgesamt ergibt sich damit eine Laufzeit von:

 

Pipelined 2-D Block Mapping

Bearbeiten

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   Elemente einer Reihe an die benachbarten Prozessoren gesendet. Analog dazu werden   Elemente einer Spalte zu den benachbarten Prozessoren gesendet. Für einen solchen Schritt wird O( ) Zeit benötigt. Nach   Schritten sind die relevanten Daten der ersten Reihe und Spalte dann bei Prozessor   angekommen. Also nach O(n) Zeit.

Die Daten der weiteren Reihen und Spalten kommen dann sukzessiv nach O( ) Zeit und können pipelineartig bearbeitet werden.   beendet seine letzte Iteration dadurch nach O( ) + O( ) Zeit. Die zusätzliche Zeit die für den Datenaustausch benötigt wird beträgt damit O( ).

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

 

Literatur

Bearbeiten
  • 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.