Parallele Breitensuche

aus Wikipedia, der freien Enzyklopädie

Die parallele Breitensuche (englisch parallel breadth-first search (BFS)) ist in der Informatik eine Variante des Breitensuche-Algorithmus für Graphen, bei der dieser Algorithmus nebenläufig auf mehreren Prozessoren verteilt (parallelisiert) ausgeführt wird.

Bei der Breitensuche werden ausgehend von einem Ausgangsknoten alle von diesem erreichbaren Knoten besucht, wobei sichergestellt wird, dass Knoten mit einer geringeren Distanz zum Ausgangsknoten vor anderen Knoten mit einer höheren Distanz besucht werden.

Allgemeines

Die parallele Breitensuche ist Grundlage für viele andere Algorithmen und wird dabei insbesondere bei der Analyse von großen Datenbeständen genutzt. Mit Hilfe der Breitensuche lassen sich z. B. der maximale Fluss, Zusammenhangskomponenten oder das Zentralitätsmaß in Graphen bestimmen. Der Algorithmus kommt außerdem beim Graph500-Benchmark zum Einsatz, um die Leistung von Supercomputern bei der Verarbeitung von großen Datenmengen zu vergleichen. Eine ähnliche Variante dieses Benchmarks ist der Green500, bei dem die Leistung im Verhältnis zum Stromverbrauch verglichen wird.[1]

Speichermodelle

Eine wichtige Rolle bei der Betrachtung von parallelen Algorithmen spielen das zugrundeliegende Speichermodell und die Kommunikation zwischen den einzelnen Prozessen. Grundsätzlich unterscheidet man hierbei zwischen zwei verschiedenen Speichermodellen:

  • Beim gemeinsamen Speicher (Shared Memory) kann jeder Prozessor auf denselben geteilten Hauptspeicher zugreifen
  • Bei verteiltem Speicher (Distributed Memory) besitzt jeder Prozessor einen eigenen, von den restlichen Prozessoren getrennten, lokalen Speicher. Die Prozessoren müssen bei diesem Modell Nachrichten austauschen, um Daten zu teilen.

Level-basierter Algorithmus

Animiertes Beispiel des Level-basierten Algorithmus
  • noch nicht besuchter Knoten
  • besuchter Knoten
  • aktuell besuchte Kante

    • Die Breitensuche wird im sequenziellen Betrieb in der Regel mit einer FIFO-Queue umgesetzt (siehe Breitensuche). Eine mögliche Umsetzung des Algorithmus kann folgendermaßen beschrieben werden:

    1. Markiere alle Knoten als nicht besucht
    2. Wähle einen Startknoten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s} und füge ihn in die aktuelle Warteliste Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle Q_c} und markiere Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s} als besucht
    3. Wiederhole, solang Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle Q_c} nicht leer ist
      1. Entferne den ersten Knoten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k} aus Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle Q_c}
      2. Füge alle mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k} verbundenen Knoten, die noch nicht besucht wurden, in die neue Warteliste Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle Q_n} und markiere sie als besucht
    4. Falls Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle Q_n} nicht leer ist, tausche Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle Q_c} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle Q_n} und gehe zu Schritt 3

    Bei dem Algorithmus gilt die folgende Schleifeninvariante: Bei der Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i} -ten Durchführung von Schritt 3 befinden sich alle Knoten mit der Distanz Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i - 1} vom Startknoten aus in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle Q_c} (aktuelles Level). In Schritt 4 befinden sich alle Knoten mit der Distanz Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i} in der Liste Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle Q_n} (nächstes Level). Da dieser Algorithmus von der Knotenmenge des aktuellen Levels ausgehend nach weiteren Knoten sucht, wird er auch als Top-down-Algorithmus bezeichnet. Ist die Menge der Knoten im aktuellen Level sehr groß, so bietet sich auch eine Bottom-up-Variante an. Bei dieser Methode werden alle bisher noch nicht besuchten Knoten ausgesucht. Diese beiden Varianten können auch als Hybrid-Algorithmus gemeinsam verwendet werden.[2]

    Um den dargestellten Algorithmus parallel auszuführen, kann die Schleife in mehrere Prozesse aufgeteilt werden. Dazu muss sichergestellt werden, dass der Zustand der Warteliste Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle Q_c} und die Datenstruktur, in welcher der Zustand der Knoten (bereits besucht oder nicht) gespeichert ist, zwischen den Prozessoren synchronisiert wird.[1] Ohne weitere Anpassung ist dieser Algorithmus nur im Shared-Memory-Modell möglich.

    BFS mit Partitionierung

    Eine Möglichkeit, den Algorithmus in mehrere Prozesse mit verteiltem Speicher aufzuteilen, besteht darin, jedem Prozess einen eigenen Teil der Knoten des Graphen zuzuordnen. Dieses Verfahren bezeichnet man als Partitionierung.

    1D-Partitionierung

    Im einfachsten Fall werden jedem der Prozesse Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n/p} Knoten mit allen ausgehenden Kanten zugeordnet, wobei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} die Anzahl der Knoten und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p} die Anzahl der Prozesse bezeichnet. In diesem Fall hält jeder Prozessor den Zustand der ihm zugewiesenen Knoten im eigenen Speicher. Durch die Partitionierung muss nach jedem Schritt zwischen den Prozessoren kommuniziert werden, da die ausgehenden Kanten nicht unbedingt auf Knoten zeigen, die demselben Prozessor zugeordnet sind. Da potenziell jeder Prozessor jedem anderen eine Nachricht senden muss, muss hier die All-to-all-Kommunikation verwendet werden.[3]

    2D-Partitionierung

    In vielen Fällen besitzt der Graph nur sehr wenige Kanten im Vergleich zur Anzahl der Knoten. Stellt man den Graphen mit Hilfe einer Adjazenzmatrix dar, erhält man eine sehr dünn besetzte Matrix. Stellt man nun die Knoten, die im aktuellen Level besucht wurden, als Vektor dar, lässt sich der nächste Schritt der Breitensuche durch eine Multiplikation des Vektors mit der Adjazenzmatrix darstellen. Die Multiplikation eines dünnbesetzten Vektors mit einer dünnbesetzten Matrix (Sparse Matrix Vector Multiplication (SpMV)) lässt sich effizient umsetzen.

    Die Adjazenzmatrix lässt sich in mehrere Untermatrizen einteilen. Jede Untermatrix entspricht dabei einem Teil der Kanten im Graphen. Die Breitensuche lässt sich dadurch parallelisieren, dass jeder Prozessor einen eigenen Teil der Adjazenzmatrix bearbeitet.[3]

    Funktionsweise anhand eines Beispiels

    Ungerichteter Graph mit 4 Knoten und 3 Kanten.svg
    Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A = \begin{array}{r|c} & \begin{matrix} 1 & 2 & 3 & 4 \end{matrix} \\ \hline \begin{matrix} 1\\ 2\\ 3\\ 4 \end{matrix} & \begin{pmatrix} 0 & 1 & 0 & 0\\ 1 & 0 & 1 & 1\\ 0 & 1 & 0 & 0\\ 0 & 1 & 0 & 0\\ \end{pmatrix} \end{array} }
    Graph Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G}

    die dazugehörige Adjazenzmatrix Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A}

    • Wir wählen die Anzahl der Spalten, in die wir unsere Matrix aufteilen möchten, mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle C=2} und die Anzahl der Zeilen mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle R=2} . Da unsere Adjazenzmatrix eine Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 4\times4} -Matrix ist, haben unsere Untermatrizen jeweils 2 Zeilen und Spalten. Die bei der Partitionierung erhaltenen Untermatrizen, die jeweils einem Prozessor zugeordnet werden, sehen wie folgt aus:

    Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A = \begin{pmatrix} A_{1, 1} & A_{1, 2} \\ A_{2, 1} & A_{2, 2} \\ \end{pmatrix} \text{ mit } A_{1, 1} = \begin{pmatrix} 0 & 1 \\ 1 & 0 \\ \end{pmatrix}, \ A_{1, 2} = \begin{pmatrix} 0 & 0 \\ 1 & 1 \\ \end{pmatrix}, \ A_{2, 1} = \begin{pmatrix} 0 & 1 \\ 0 & 1 \\ \end{pmatrix}, \ A_{2, 2} = \begin{pmatrix} 0 & 0 \\ 0 & 0 \\ \end{pmatrix} }

    • Im Folgenden wird nun ein einziger Berechnungsschritt der Breitensuche für den Prozessor, der die Matrix Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A_{1, 1}} besitzt, betrachtet:
    1. Der Prozessor Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A_{1, 1}} berechnet den Teil der Breitensuche, der durch die in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A_{1, 1}} enthaltenen Kanten gegeben ist. In Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G} ist dies die Kante zwischen Knoten 1 und 2. Für die Berechnung der Breitensuche benötigt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A_{1, 1}} zunächst als Eingabe den Vektor Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle v} mit zwei Elementen, der angibt, ob Knoten 1 und 2 im letzten Schritt der Breitensuche besucht wurden.
    2. Um einen aktuellen Zustand des Vektors Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle v} zu erhalten, muss Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A_{1, 1}} mit allen Prozessoren in der gleichen Spalten kommunizieren, da jeder dieser Prozessoren einen der beiden Knoten im letzten Schritt besucht haben könnte. In diesem Beispiel muss der Vektor Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle v} also nur mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A_{2, 1}} ausgetauscht werden.
    3. Anschließend wird der Vektor Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle v} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A_{1, 1}} multipliziert, um die Knoten zu erhalten, die im nächsten Schritt erreicht werden. Sei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle v = \begin{pmatrix} 1 \\ 0 \end{pmatrix}} (d. h., Knoten 1 wurde im vorherigen Schritt besucht), gilt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A_{1, 1} \times v = \begin{pmatrix} 0 \\ 1 \end{pmatrix}} , wobei die Eins in der zweiten Komponente darauf hinweist, dass im nächsten Schritt Knoten 2 besucht wird.
    4. Das Ergebnis der Matrix-Vektor-Multiplikation muss nun mit allen Prozessoren in der gleichen Zeile ausgetauscht werden. Durch diesen Kommunikationsschritt wird der besucht-Zustand der Knoten abgeglichen und werden mögliche Konflikte für den Fall gelöst, dass mehrere Prozessoren denselben Knoten besuchen. Anschließend beginnt der Prozess wieder von vorn.

    Der Vorteil gegenüber der 1D-Partitionierung besteht darin, dass jeder Prozessor nur mit den Prozessoren in derselben Reihe und Spalte kommunizieren muss, nicht jedoch mit allen anderen Prozessoren. Im Vergleich zur 1D-Partitionierung sind dafür jedoch zwei anstatt ein einziger Kommunikationsschritt für jede Ebene notwendig.

    Weblinks

    Einzelnachweise

    1. ↑ a b Yasui Y., Fujisawa K. (2017) Fast, Scalable, and Energy-Efficient Parallel Breadth-First Search. In: Anderssen B. et al. (eds) The Role and Importance of Mathematics in Innovation. Mathematics for Industry, vol 25. Springer, Singapore
    2. ↑ Ueno, K., Suzumura, T., Maruyama, N. et al. Data Sci. Eng. (2017) 2: 22. doi:10.1007/s41019-016-0024-y
    3. ↑ a b Aydin Buluç and Kamesh Madduri. 2011. Parallel breadth-first search on distributed memory systems. In Proceedings of 2011 International Conference for High Performance Computing, Networking, Storage and Analysis (SC '11). ACM, New York, NY, USA, Article 65, 12 pages. doi:10.1145/2063384.2063471
    Abgerufen von „https://de.wikiup.org/index.php?title=Parallele_Breitensuche&oldid=224114464“