Hyperwürfel (Kommunikationsmuster)

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

Der -dimensionale Hyperwürfel ist eine Netztopologie für Rechnerbündel mit Rechnern. Sie erlaubt eine effiziente Implementierung der Kommunikations-Grundmuster Broadcast, Gossip, All-Reduce und der Partialsummenbildung.[1] Dazu werden die teilnehmenden Rechner von bis binär durchnummeriert. Jeder Rechner besitzt dann eine direkte Verbindung zu den Rechnern, deren Nummern sich in genau einem Bit von unterscheiden. Diese Struktur wird von den folgenden Algorithmen effizient ausgenutzt.

Einige der Kommunikationsprimitiven lassen sich nach derselben Skizze implementieren, die in diesem Abschnitt vorgestellt wird.[2] Zu Beginn jeder Kommunikationsprimitive besitzt jeder teilnehmende Rechner eine Nachricht, die im Laufe der Kommunikation einmal jeden anderen Rechner erreichen muss. Dieser Ablauf wird vom folgenden Pseudocode skizziert, wobei Initialisierung, Operation und Ausgabe von der Kommunikationsprimitive abhängige Platzhalter sind.

Eingabe: Nachricht .
Ausgabe: Abhängig von den Platzhaltern Initialisierung, Operation und Ausgabe.
Initialisierung

for  do
    
    Sende  an 
    Empfange  von 
    Operation
endfor
Ausgabe

Im Pseudocode iteriert jeder Rechner einmal über seine Nachbarn, denn der Ausdruck negiert das -te Bit in der Binärdarstellung von , beschreibt also gerade die Nummer des -ten Nachbarns von Rechner . Jeder Rechner tauscht nun eine Nachricht mit diesem Nachbarn aus und verarbeitet anschließend seine aktuelle Nachricht mit der empfangenen Nachricht , wobei sich die anzuwendende Akkumulationsoperation nach Kommunikationsprimitive unterscheidet.

Die Algorithmenskizze angewandt auf einen -dimensionalen Hyperwürfel. Im ersten Schritt (vor jeder Kommunikation) besitzt jeder Rechner eine Nachricht (blau), die er im jeweiligen Schritt entlang der rot markierten Dimension mit seinem Nachbarn austauscht. Nach einem Austausch werden die Nachricht in diesem Beispiel konkateniert. Nach dem letzten Schritt besitzt jeder Rechner jede Nachricht.

Kommunikationsprimitiven

[Bearbeiten | Quelltext bearbeiten]

Bei der Präfixsumme besitzt jeder Prozessor zu Beginn eine Nachricht . Das Ziel ist es, dass jeder Prozessor am Ende für eine assoziative Operation erhält. Der Algorithmus kann wie folgt in die Algorithmenskizze eingebettet werden:

Eingabe: Nachricht  auf Prozessor .
Ausgabe: Präfixsumme  auf Prozessor .


for  do
    
    Sende  an 
    Empfange  von 
    
    if Bit  in  gesetzt then 
endfor

Ein Hyperwürfel der Dimension kann in zwei Hyperwürfel der Dimension zerlegt werden. Dazu wird im Weiteren der Teilwürfel aller Knoten, deren Nummer in Binärdarstellung mit 0 beginnen, als 0-Teilwürfel bezeichnet. Die restlichen Knoten bilden analog den 1-Teilwürfel. Nachdem in beiden Teilwürfeln die Präfixsumme berechnet wurde, muss die Gesamtsumme der Elemente im 0-Teilwürfel noch auf alle Elemente des 1-Teilwürfels aufaddiert werden. Das liegt daran, dass nach Definition die Rechner im 0-Teilwürfel einen kleineren Rang als die Rechner im 1-Teilwürfel besitzen. In der Implementierung speichert jeder Knoten deswegen neben seiner Präfixsumme (Variable ) außerdem die Summe über alle Elemente im Teilwürfel (Variable ). So können in jedem Schritt alle Knoten im 1-Teilwürfel die Gesamtsumme über den 0-Teilwürfel beziehen.

Bei der Laufzeit ergibt sich ein Faktor von für und ein Faktor von für : .

Beispiel für eine Präfixsummenberechnung. Jeder Knoten startet mit seiner eigenen Knotennummer als Nachricht, d. h. . Die obere Zeile eines Knotens zeigt , die untere Zeile . Die Operation ist Addition.

Gossip / All-Reduce

[Bearbeiten | Quelltext bearbeiten]

Bei der Gossip Operation startet jeder Rechner mit einer Nachricht . Ziel ist es, dass nach der Ausführung jeder Rechner alle Rechner kennt, also über die Nachricht verfügt, wobei die Konkatenation bezeichne. Diese Operation kann wie folgt mit der Algorithmenskizze implementiert werden:


Eingabe: Nachricht  auf Prozessor .
Ausgabe: Alle Nachrichten .

for  do
    
    Sende  an 
    Empfange  von 
    
endfor


Der Ablauf folgt der Skizze. Man beachte, dass sich die Länge der übermittelelten Nachrichten in jedem Schritt verdoppelt. Dadurch ergibt sich folgende Laufzeit: .


Bei All-Reduce werden im Gegensatz zu Gossip die Nachrichten nicht konkateniert, sondern ein Operator auf die zwei Nachrichten angewandt. Es ist also eine Reduce-Operation deren Ergebnis jedem Prozessor zur Verfügung steht. Im Hyperwürfel lässt sich der Gossip-Algorithmus anpassen. Dies reduziert die Anzahl der Kommunikationsschritte gegenüber Reduce und Broadcast.

Bei der All-to-All Kommunikation hat jeder Prozessor eine eigene Nachricht für alle anderen Prozessoren.

Eingabe: Nachrichten  auf Prozessor  an Prozessor .
for  do
   Erhalte von Prozessor :
       alle Nachrichten für meinen -dimensionalen Teilwürfel
   Sende an Prozessor :
       alle Nachrichten für seinen -dimensionalen Teilwürfel
endfor

Eine Nachricht kommt in jedem Iterationsschritt eine Dimension näher an ihr Ziel, sollte sie es noch nicht erreicht haben. Demnach werden nur maximal viele Schritte benötigt. In jedem Schritt werden Nachrichten verschickt. Für den ersten Schritt liegen genau die Hälfte der Nachrichten nicht im eigenen Teilwürfel. In den allen folgenden Schritten ist der Teilwürfel nur noch halb so groß wie davor, allerdings wurden im vorhergegangenen Schritt genauso viele Nachrichten von einem anderen Prozessor erhalten, die auch für diesen Teilwürfel bestimmt sind.

Insgesamt bedeutet dies eine Laufzeit von .

Der ESBT-Broadcast (Edge-disjoint Spanning Binomial Tree) Algorithmus[3] ist ein zeitoptimaler Broadcast für Rechnerbündel mit Hyperwürfel-Netztopologie. Dazu wird das Netz ausgehend von der Quelle (im Folgenden der -Rechner) in kantendisjunkte Binomialbäume aufgeteilt, so dass jeder Nachbar der Quelle die Wurzel eines Binomialbaums mit Rechnern ist. Die Quelle zerteilt ihre Nachricht nun in Teilnachrichten, die dann zyklisch an die Wurzeln der Binomialbäume verteilt werden. Jeder Binomialbaum führt anschließend einen Broadcast aus.

Verteilt die Quelle in jedem Schritt eine Teilnachricht, hat sie nach Schritten alle Teilnachrichten verteilt. Der Broadcast in einem Binomialbaum benötigt Schritte. Insgesamt werden somit Schritte benötigt, bis der Broadcast für die letzte Nachricht abgeschlossen ist und die Laufzeit für eine Nachricht der Länge ergibt sich zu . Das optimale minimiert die Laufzeit zu .

Aufbau der Binomialbäume

[Bearbeiten | Quelltext bearbeiten]
Ein -dimensionaler Hyperwürfel mit drei kantendisjunkten ESBTs.

Die Binomialbäume können systematisch nach der folgender Vorschrift konstruiert werden. Dazu wird zunächst ein Binomialbaum mit Knoten definiert. Anschließend werden durch Translation und Rotation kantendisjunkte Kopien des Binomialbaums in den Hyperwürfel eingebettet.

Ein einzelner Binomialbaum hat Knoten als Wurzel. Die Kinder eines Knotens ergeben sich durch Negation der führenden Nullen in der Binärdarstellung der Knotennummer. Der so resultierende Graph ist offensichtlich ein Binomialbaum. Die Kantenmenge des -ten Binomialbaums im Hyperwürfel erhält man nun wie folgt: auf jeden Knoten wendet man eine XOR-Operation mit an und verschiebt die Binärdarstellung der Knotennummer anschließend um Stellen zyklisch nach rechts. Die so entstehenden Kopien des ausgehenden Binomialbaums sind kantendisjunkt und erfüllen somit die Voraussetzungen des ESBT-Broadcast Algorithmus.

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]
  1. A. Grama: Introduction to Parallel Computing. 2. Auflage. Addison-Wesley, 2003, ISBN 0-201-64865-2.
  2. I. Foster: Designing and Building Parallel Programs. Concepts and Tools for Parallel Software Engineering. Addison-Wesley, 1995, ISBN 0-201-57594-9.
  3. S. L. Johnsson, C.-T. Ho: Optimum broadcasting and personalized communication in hypercubes. In: IEEE Transactions on Computers. Band 38, Nr. 9, 1989, ISSN 0018-9340, S. 1249–1268, doi:10.1109/12.29465.