www.wikidata.de-de.nina.az

Hyperwürfel Kommunikationsmuster Der d displaystyle d dimensionale Hyperwürfel ist eine Netztopologie für Rechnerbündel

Hyperwürfel (Kommunikationsmuster)

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

Skizze Bearbeiten

Einige der Kommunikationsprimitiven lassen sich nach derselben Skizze implementieren, die in diesem Abschnitt vorgestellt wird. 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

Präfixsumme 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

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.

All-to-All Bearbeiten

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 .

ESBT-Broadcast Bearbeiten

Der ESBT-Broadcast (Edge-disjoint Spanning Binomial Tree) Algorithmus 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

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

  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.
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Der d displaystyle d dimensionale Hyperwurfel ist eine Netztopologie fur Rechnerbundel mit 2 d displaystyle 2 d Rechnern Sie erlaubt eine effiziente Implementierung der Kommunikations Grundmuster Broadcast Gossip All Reduce und der Partialsummenbildung 1 Dazu werden die teilnehmenden Rechner von 0 displaystyle 0 bis 2 d 1 displaystyle 2 d 1 binar durchnummeriert Jeder Rechner i displaystyle i besitzt dann eine direkte Verbindung zu den d displaystyle d Rechnern deren Nummern sich in genau einem Bit von i displaystyle i unterscheiden Diese Struktur wird von den folgenden Algorithmen effizient ausgenutzt Inhaltsverzeichnis 1 Skizze 2 Kommunikationsprimitiven 2 1 Prafixsumme 2 2 Gossip All Reduce 2 3 All to All 3 ESBT Broadcast 3 1 Aufbau der Binomialbaume 4 EinzelnachweiseSkizze BearbeitenEinige 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 abhangige Platzhalter sind Eingabe Nachricht m displaystyle m nbsp Ausgabe Abhangig von den Platzhaltern Initialisierung Operation und Ausgabe Initialisierung s m displaystyle s m nbsp for 0 k lt d displaystyle 0 leq k lt d nbsp do y i XOR 2 k displaystyle y i text XOR 2 k nbsp Sende s displaystyle s nbsp an y displaystyle y nbsp Empfange m displaystyle m nbsp von y displaystyle y nbsp Operation s m displaystyle s m nbsp endfor Ausgabe Im Pseudocode iteriert jeder Rechner einmal uber seine Nachbarn denn der Ausdruck i XOR 2 k displaystyle i text XOR 2 k nbsp negiert das k displaystyle k nbsp te Bit in der Binardarstellung von i displaystyle i nbsp beschreibt also gerade die Nummer des k displaystyle k nbsp ten Nachbarns von Rechner i displaystyle i nbsp Jeder Rechner tauscht nun eine Nachricht s displaystyle s nbsp mit diesem Nachbarn aus und verarbeitet anschliessend seine aktuelle Nachricht s displaystyle s nbsp mit der empfangenen Nachricht m displaystyle m nbsp wobei sich die anzuwendende Akkumulationsoperation nach Kommunikationsprimitive unterscheidet nbsp Die Algorithmenskizze angewandt auf einen 3 displaystyle 3 nbsp dimensionalen Hyperwurfel 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 BearbeitenPrafixsumme Bearbeiten Bei der Prafixsumme besitzt jeder Prozessor i displaystyle i nbsp zu Beginn eine Nachricht m i displaystyle m i nbsp Das Ziel ist es dass jeder Prozessor i displaystyle i nbsp am Ende 0 j i m j displaystyle bigoplus 0 leq j leq i m j nbsp fur eine assoziative Operation displaystyle oplus nbsp erhalt Der Algorithmus kann wie folgt in die Algorithmenskizze eingebettet werden Eingabe Nachricht m i displaystyle m i nbsp auf Prozessor i displaystyle i nbsp Ausgabe Prafixsumme 0 j i m j displaystyle bigoplus 0 leq j leq i m j nbsp auf Prozessor i displaystyle i nbsp x m i displaystyle x m i nbsp s m i displaystyle sigma m i nbsp for 0 k d 1 displaystyle 0 leq k leq d 1 nbsp do y i XOR 2 k displaystyle y i text XOR 2 k nbsp Sende s displaystyle sigma nbsp an y displaystyle y nbsp Empfange m displaystyle m nbsp von y displaystyle y nbsp s s m displaystyle sigma sigma oplus m nbsp if Bit k displaystyle k nbsp in i displaystyle i nbsp gesetzt then x x m displaystyle x x oplus m nbsp endfor Ein Hyperwurfel der Dimension d displaystyle d nbsp kann in zwei Hyperwurfel der Dimension d 1 displaystyle d 1 nbsp zerlegt werden Dazu wird im Weiteren der Teilwurfel aller Knoten deren Nummer in Binardarstellung mit 0 beginnen als 0 Teilwurfel bezeichnet Die restlichen Knoten bilden analog den 1 Teilwurfel Nachdem in beiden Teilwurfeln die Prafixsumme berechnet wurde muss die Gesamtsumme der Elemente im 0 Teilwurfel noch auf alle Elemente des 1 Teilwurfels aufaddiert werden Das liegt daran dass nach Definition die Rechner im 0 Teilwurfel einen kleineren Rang als die Rechner im 1 Teilwurfel besitzen In der Implementierung speichert jeder Knoten deswegen neben seiner Prafixsumme Variable x displaystyle x nbsp ausserdem die Summe uber alle Elemente im Teilwurfel Variable s displaystyle sigma nbsp So konnen in jedem Schritt alle Knoten im 1 Teilwurfel die Gesamtsumme uber den 0 Teilwurfel beziehen Bei der Laufzeit ergibt sich ein Faktor von log p displaystyle log p nbsp fur T start displaystyle T text start nbsp und ein Faktor von n log p displaystyle n log p nbsp fur T byte displaystyle T text byte nbsp T n p T start n T byte log p displaystyle T n p T text start nT text byte log p nbsp nbsp Beispiel fur eine Prafixsummenberechnung Jeder Knoten startet mit seiner eigenen Knotennummer als Nachricht d h m i i displaystyle m i i nbsp Die obere Zeile eines Knotens zeigt x displaystyle x nbsp die untere Zeile s displaystyle sigma nbsp Die Operation ist Addition Gossip All Reduce Bearbeiten Bei der Gossip Operation startet jeder Rechner mit einer Nachricht m i displaystyle m i nbsp Ziel ist es dass nach der Ausfuhrung jeder Rechner alle Rechner kennt also uber die Nachricht x m 0 m 1 m p displaystyle x m 0 cdot m 1 dots m p nbsp verfugt wobei displaystyle cdot nbsp die Konkatenation bezeichne Diese Operation kann wie folgt mit der Algorithmenskizze implementiert werden Eingabe Nachricht x m i displaystyle x m i nbsp auf Prozessor i displaystyle i nbsp Ausgabe Alle Nachrichten m 1 m 2 m p displaystyle m 1 cdot m 2 dots m p nbsp x m i displaystyle x m i nbsp for 0 k lt d displaystyle 0 leq k lt d nbsp do y i XOR 2 k displaystyle y i text XOR 2 k nbsp Sende x displaystyle x nbsp an y displaystyle y nbsp Empfange x displaystyle x nbsp von y displaystyle y nbsp x x x displaystyle x x cdot x nbsp endfor Der Ablauf folgt der Skizze Man beachte dass sich die Lange der ubermittelelten Nachrichten in jedem Schritt verdoppelt Dadurch ergibt sich folgende Laufzeit T n p j 0 d 1 T start n 2 j T byte log p T start p 1 n T byte displaystyle T n p approx sum j 0 d 1 T text start n cdot 2 j T text byte log p T text start p 1 nT text byte nbsp 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 Verfugung steht Im Hyperwurfel lasst sich der Gossip Algorithmus anpassen Dies reduziert die Anzahl der Kommunikationsschritte gegenuber Reduce und Broadcast All to All Bearbeiten Bei der All to All Kommunikation hat jeder Prozessor eine eigene Nachricht fur alle anderen Prozessoren Eingabe Nachrichten m i j displaystyle m ij nbsp auf Prozessor i displaystyle i nbsp an Prozessor j displaystyle j nbsp for d gt k 0 displaystyle d gt k geq 0 nbsp do Erhalte von Prozessor i XOR 2 k displaystyle i text XOR 2 k nbsp alle Nachrichten fur meinen k displaystyle k nbsp dimensionalen Teilwurfel Sende an Prozessor i XOR 2 k displaystyle i text XOR 2 k nbsp alle Nachrichten fur seinen k displaystyle k nbsp dimensionalen Teilwurfel endfor Eine Nachricht kommt in jedem Iterationsschritt eine Dimension naher an ihr Ziel sollte sie es noch nicht erreicht haben Demnach werden nur maximal d log p displaystyle d log p nbsp viele Schritte benotigt In jedem Schritt werden p 2 displaystyle p 2 nbsp Nachrichten verschickt Fur den ersten Schritt liegen genau die Halfte der Nachrichten nicht im eigenen Teilwurfel In den allen folgenden Schritten ist der Teilwurfel nur noch halb so gross wie davor allerdings wurden im vorhergegangenen Schritt genauso viele Nachrichten von einem anderen Prozessor erhalten die auch fur diesen Teilwurfel bestimmt sind Insgesamt bedeutet dies eine Laufzeit von T n p log p T start p 2 n T byte displaystyle T n p approx log p T text start frac p 2 nT text byte nbsp ESBT Broadcast BearbeitenDer ESBT Broadcast Edge disjoint Spanning Binomial Tree Algorithmus 3 ist ein zeitoptimaler Broadcast fur Rechnerbundel mit Hyperwurfel Netztopologie Dazu wird das Netz ausgehend von der Quelle im Folgenden der 0 displaystyle 0 nbsp Rechner in d displaystyle d nbsp kantendisjunkte Binomialbaume aufgeteilt so dass jeder Nachbar der Quelle die Wurzel eines Binomialbaums mit 2 d 1 displaystyle 2 d 1 nbsp Rechnern ist Die Quelle zerteilt ihre Nachricht nun in k displaystyle k nbsp Teilnachrichten die dann zyklisch an die Wurzeln der Binomialbaume verteilt werden Jeder Binomialbaum fuhrt anschliessend einen Broadcast aus Verteilt die Quelle in jedem Schritt eine Teilnachricht hat sie nach k displaystyle k nbsp Schritten alle Teilnachrichten verteilt Der Broadcast in einem Binomialbaum benotigt d displaystyle d nbsp Schritte Insgesamt werden somit k d displaystyle k d nbsp Schritte benotigt bis der Broadcast fur die letzte Nachricht abgeschlossen ist und die Laufzeit fur eine Nachricht der Lange n displaystyle n nbsp ergibt sich zu T n p k n k T byte T start k d displaystyle T n p k left frac n k T text byte T text start right k d nbsp Das optimale k n d T byte T start displaystyle k sqrt frac nd cdot T text byte T text start nbsp minimiert die Laufzeit zu T n p n T byte log p T start n log p T start T byte displaystyle T n p n cdot T text byte log p cdot T text start sqrt n log p cdot T text start cdot T text byte nbsp Aufbau der Binomialbaume Bearbeiten nbsp Ein 3 displaystyle 3 nbsp dimensionaler Hyperwurfel mit drei kantendisjunkten ESBTs Die d displaystyle d nbsp Binomialbaume konnen systematisch nach der folgender Vorschrift konstruiert werden Dazu wird zunachst ein Binomialbaum mit 2 d displaystyle 2 d nbsp Knoten definiert Anschliessend werden durch Translation und Rotation d displaystyle d nbsp kantendisjunkte Kopien des Binomialbaums in den Hyperwurfel eingebettet Ein einzelner Binomialbaum hat Knoten 0 displaystyle 0 nbsp als Wurzel Die Kinder eines Knotens ergeben sich durch Negation der fuhrenden Nullen in der Binardarstellung der Knotennummer Der so resultierende Graph ist offensichtlich ein Binomialbaum Die Kantenmenge des k displaystyle k nbsp ten Binomialbaums im Hyperwurfel erhalt man nun wie folgt auf jeden Knoten wendet man eine XOR Operation mit 2 k displaystyle 2 k nbsp an und verschiebt die Binardarstellung der Knotennummer anschliessend um k displaystyle k nbsp Stellen zyklisch nach rechts Die so entstehenden d displaystyle d nbsp Kopien des ausgehenden Binomialbaums sind kantendisjunkt und erfullen somit die Voraussetzungen des ESBT Broadcast Algorithmus Einzelnachweise Bearbeiten A Grama Introduction to Parallel Computing 2 Auflage Addison Wesley 2003 ISBN 0 201 64865 2 I Foster Designing and Building Parallel Programs Concepts and Tools for Parallel Software Engineering Addison Wesley 1995 ISBN 0 201 57594 9 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 Abgerufen von https de wikipedia org w index php title Hyperwurfel Kommunikationsmuster amp oldid 206200111