Algorithmus zwei verschiedene wege mit gleichem start und ende

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.

Inhaltsverzeichnis Show

Hat ein Algorithmus ein Ende?
Wie funktioniert der Algorithmus von Dijkstra?
Wo wird der Dijkstra Algorithmus angewendet?
Welches Problem löst der Dijkstra Algorithmus?

Sei G=(V,E,w){\displaystyle G=(V,E,w)}

ein gerichteter Graph mit der Knotenmenge V{\displaystyle V}

und der Kantenmenge E⊆V×V{\displaystyle E\subseteq V\times V}

. Jeder Kante e∈E{\displaystyle e\in E}

ist ein Gewicht w(e){\displaystyle 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{\displaystyle 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{\displaystyle D}

, deren Einträge d−i,j{\displaystyle d-{i,j}}

das Gewicht des kürzesten Weges von Knoten i{\displaystyle i}

zu Knoten j{\displaystyle j}

enthalten.

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}

benötigt. Zurückgegeben wird dann ein Array dv{\displaystyle d_{v}}

der Distanzen. Das i{\displaystyle i}-te Element im Array enthält dabei die Distanz von v{\displaystyle v} zu dem Knoten i{\displaystyle i}; Damit entspricht diese Liste genau der v{\displaystyle v}-ten Zeile in der APSP-Distanzmatrix D{\displaystyle D}. Der Algorithmus zur Lösung des APSP-Problems iteriert dementsprechend über alle Knoten des Graphen G{\displaystyle 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){\displaystyle O(|V|^{2})}

. Damit ergibt sich für DijkstraAPSP eine sequentielle Laufzeit von O(|V|3){\displaystyle O(|V|^{3})}

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|}

für diese Parallelisierung eine Obergrenze für die Anzahl an verwendbaren Prozessoren.

Somit ergibt sich z. B. falls die Anzahl Prozessoren p{\displaystyle p}

gleich der Anzahl Knoten |V|{\displaystyle |V|} ist, dass jeder Prozessor genau einmal den DijkstraSSSP ausführt. Stehen hingegen z. B. nur p=|V|2{\displaystyle 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⋅|V|p){\displaystyle O(|V|^{2}\cdot {\frac {|V|}{p}})}

, falls |V|{\displaystyle |V|} ein Vielfaches von p{\displaystyle p} ist. Die Effizienz dieser Parallelisierung ist damit perfekt: Durch Verwendung von p{\displaystyle p} Prozessoren wird die Laufzeit um den Faktor p{\displaystyle 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.

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|}}}

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|{\displaystyle p=|V|}

Prozessoren.

Die Hauptschwierigkeit besteht nun darin, dass k{\displaystyle k}

Prozessoren die Ausführung von DijkstraSSSP parallelisieren müssen. Die Idee zur Lösung dieses Problems ist die Verwaltung der Distanzliste dv{\displaystyle d_{v}} in DijkstraSSSP innerhalb der Gruppe zu verteilen. Jeder Prozessor in der Gruppe ist dementsprechend für |V|k{\displaystyle {\frac {|V|}{k}}}

Elemente der Liste exklusiv verantwortlich. Sei z. B. |V|=4{\displaystyle |V|=4}

und p=8{\displaystyle p=8}

. Damit ergibt sich eine Gruppengröße von k=2{\displaystyle k=2}

. Dann speichert und verwaltet jeweils der erste Prozessor einer Gruppe dv,1{\displaystyle d_{v,1}}

, dv,2{\displaystyle d_{v,2}}

und der zweite dv,3{\displaystyle d_{v,3}}

sowie dv,4{\displaystyle d_{v,4}}

. Die gesamte Distanzliste ist dabei dv=[dv,1,dv,2,dv,3,dv,4]{\displaystyle 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{\displaystyle x}

in der Distanzliste dv{\displaystyle d_{v}} gefunden werden. Damit ist nun der kürzeste Weg für x{\displaystyle x} bekannt. Anschließend müssen noch die Entfernungen in dv{\displaystyle d_{v}} für alle Nachbarn von x{\displaystyle x} aktualisiert werden.

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.
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(log⁡k){\displaystyle O(\log k)}
entspricht.

Für |V|{\displaystyle |V|}-Iterationen ergibt sich damit eine Gesamtlaufzeit in O(|V|(|V|k+log⁡k)){\displaystyle O(|V|({\frac {|V|}{k}}+\log k))}

. Setzt man nun die Definition von k{\displaystyle k} ein, ergibt sich für DijkstraAPSP eine Laufzeit von O(|V|3p+log⁡p){\displaystyle 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{\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}}

ist im nachfolgenden Bild dargestellt.

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;
 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
            )
          
        
        :=
        m
        i
        n
        (
        
          d
          
            i
            ,
            j
          
          
            (
            k
            −
            1
            )
          
        
        ,
        
          d
          
            i
            ,
            k
          
          
            (
            k
            −
            1
            )
          
        
        +
        
          d
          
            k
            ,
            j
          
          
            (
            k
            −
            1
            )
          
        
        )
      
    
    {\displaystyle 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.

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}

- Matrix und p Prozessoren berechnet dabei jeder Prozessor einen n/(p)×n/(p){\displaystyle n/{\sqrt {(}}p)\times n/{\sqrt {(}}p)}

großen Abschnitt der Matrix. Abbildung 1 zeigt eine solche Aufteilung. Mit p=n2{\displaystyle p=n^{2}}

Prozessoren würde dabei jeder Prozessor genau einen Eintrag berechnen. Der Algorithmus skaliert dadurch nur bis zu einer maximalen Anzahl von n2{\displaystyle n^{2}}

Prozessoren. Mit pi,j{\displaystyle 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 di,j(k){\displaystyle d_{i,j}^{(k)}}

den Eintrag der Zeile i und Spalte j der Matrix nach der k-ten Iteration. Um di,j(k){\displaystyle d_{i,j}^{(k)}} zu berechnen werden wie in Zeile 6 des Algorithmus angegeben di,j(k−1){\displaystyle d_{i,j}^{(k-1)}}

, di,k(k−1){\displaystyle d_{i,k}^{(k-1)}}

und dk,j(k−1){\displaystyle d_{k,j}^{(k-1)}}

benötigt. di,j(k−1){\displaystyle 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 Dk−1{\displaystyle D^{k-1}}

Matrix. di,k(k−1){\displaystyle d_{i,k}^{(k-1)}} liegt dabei auf einem Prozessor in der gleichen Spalte und dk,j(k−1){\displaystyle d_{k,j}^{(k-1)}} auf einem Prozessor in der gleichen Zeile wie der Prozessor der di,j(k){\displaystyle d_{i,j}^{(k)}} berechnen muss. Jeder Prozessor, der in Dk−1{\displaystyle 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 Dk−1{\displaystyle 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
            )
          
        
      
    
    {\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)}}
  
 hat,
            broadcastet diesen zu den Prozessoren 
  
    
      
        
          p
          
            ∗
            ,
            j
          
        
      
    
    {\displaystyle p_{*,j}}
  
;
 4          Jeder Prozessor 
  
    
      
        
          p
          
            i
            ,
            j
          
        
      
    
    {\displaystyle p_{i,j}}
  
 der einen Teil der k-ten Spalte von 
  
    
      
        
          D
          
            (
            k
            −
            1
            )
          
        
      
    
    {\displaystyle D^{(k-1)}}
  
 hat,
            broadcastet diesen zu den Prozessoren 
  
    
      
        
          p
          
            i
            ,
            ∗
          
        
      
    
    {\displaystyle p_{i,*}}
  
;
 5          Jeder Prozessor wartet bis die benötigten Daten vorhanden sind;
 6          Jeder Prozessor berechnet seinen Teil der 
  
    
      
        
          D
          
            (
            k
            )
          
        
      
    
    {\displaystyle 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.

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)}

) ausgeführt werden. Damit ergibt sich eine Laufzeit von O(n3){\displaystyle O(n^{3})}

für den sequentiellen Algorithmus.

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.

Hat ein Algorithmus ein Ende?

Aus dieser Definition sind folgende Eigenschaften eines Algorithmus ableitbar: Das Verfahren muss in einem endlichen Text eindeutig beschreibbar sein (Finitheit). Jeder Schritt des Verfahrens muss tatsächlich ausführbar sein (Ausführbarkeit).

Wie funktioniert der Algorithmus von Dijkstra?

Der Dijkstra-Algorithmus berechnet die Kosten der günstigsten Wege von einem Startknoten aus zu allen anderen Knoten im Graph. Der Algorithmus beginnt bei einem Startknoten und wählt schrittweise über die als nächstes erreichbaren Knoten die momentan günstigsten Wege aus. Dabei kann er auch Verbesserungen vornehmen.

Wo wird der Dijkstra Algorithmus angewendet?

Es ist wichtig für mobile Ad-hoc-Netze. Eine mögliche Anwendung davon sind die freien Funknetze. Auch bei der Lösung des Münzproblems, eines zahlentheoretischen Problems, das auf den ersten Blick nichts mit Graphen zu tun hat, kann der Dijkstra-Algorithmus eingesetzt werden.

Welches Problem löst der Dijkstra Algorithmus?

Der Algorithmus von Dijkstra löst das Problem der kürzesten Wege für einen gegebenen Startknoten. Der Algorithmus berechnet einen kürzesten Weg zwischen dem gegebenen Startknoten und den anderen Knoten in einem kantengewichteten, gerichteten Graphen.