Verbindungsnetzwerke, Einbettungen, Routing- und Switchingstrategien Seminar „Parallele Programmierung“ Gunnar Thies

Verbindungsnetzwerke, Einbettungen, Routing- und

Switchingstrategien

Seminar „Parallele Programmierung“Gunnar Thies

2

1. Einleitung

2. Grundbegriffe

3. Arten von Verbindungsnetzwerken

4. Routingtechnik

5. Fazit

Gliederung

3

1. Einleitung

1. Einleitung

Verwendung paralleler Rechnersysteme beispielsweise bei

komplexen Rechenaufgaben wie:

• Wettervorhersagen

• Windkanalsimulationen für Fahrzeuge

• Filmindustrie

4

1. Einleitung

Vorteil von Einsatz paralleler Rechnersysteme gegenüberEinzelrechnern:

• Aufteilung der Rechenlast auf mehrere Verarbeitungseinheiten (Prozessoren)

• Steigerung der Rechen(Speicher-)Kapazität• Ausfallsicherheit wird gesteigert• Steigerung der Simulationsgenauigkeit

Nachteile von parallelen Rechnersystemen:

• Deadlockgefahr• Wartungsaufwand höher (im Vergleich zu Einzelrechnern)

5

2. Grundbegriffe

2.1 Verbindungsnetzwerk

2.2 Einbettung

2.3 Routingtechnik

6

2. Grundbegriffe - Verbindungsnetzwerk

2.1 Verbindungsnetzwerk

• Verbindet einzelne Verarbeitungseinheiten (Knoten) des Netzwerks miteinander

• Dient der Koordination von Rechenaufgaben

• Haupt-Aufgabe: Übertragung von Nachrichten zwischen einzelnen Verarbeitungseinheiten

Wichtigster Aspekt:

Fehlerfreie und möglichst schnelle Übertragung der

Nachrichten / Daten durch das Verbindungsnetzwerk

7

2. Grundbegriffe - Verbindungsnetzwerk

Grundaspekte zur Einordnung von Verbindungsnetzwerken:

• Topologie : Form der Verschachtelung / Verbindung der Verarbeitungseinheiten (Knoten) im Netzwerk

• Routingtechnik: Berechnung von Pfaden durchs Netzwerk und Realisierung der Nachrichtenübertragung vom Quell- zum Zielknoten

8

2. Grundbegriffe - Einbettung

2.2 Einbettung

• Die Einbettung ist ein Maß für die Flexibilität des Verbindungsnetzwerks

Vorgehen:

• Überprüfen der Möglichkeit ein Netzwerk N‘ auf ein gegebenes Netzwerk N so abzubilden, dass jeder Knoten des Netzwerks N‘ auf unterschiedlichen Knoten des Netzwerks N zu liegen kommt.

9


Beispiel:

Einbettung eines Ring-Netzwerks mit 8 Knoten in ein Gitter-Netzwerk

mit 12 Knoten:

1

2

3 4 5

6

4

781

2

3 4 5

67

8

• Dadurch lassen sich (Routing-) Algorithmen des Netzwerks N‘ auch im Netzwerk N verwenden – N ist mindestens so flexibel wie N‘.

N‘ N

10


Ein Merkmal der Einbettung ist der Streckungsgrad:

• bezeichnet die maximale Erhöhung der Distanz zweier Knoten des Netzwerks N‘ durch die Einbettung in Netzwerk N

• Grad von 1 bedeutet, dass die Distanz der Knoten in N dieselbe ist wie in N‘

• Höherer Grad bedeutet Erhöhung der Distanz durch die Einbettung und dadurch erhöhte Kommunikationslast und -dauer.

Anm.: Hier werden nur Einbettungen vom Grad 1 betrachtet.

11


Einbettung eines Netzwerks N‘ in N mit Streckungsgrad 1:

1

2

3 4 5

6

4

78 1

2

3 4 5

67

8


N‘ N

1

3

2 4

5N‘

1

2

4 5

3N

12

2. Grundbegriffe - Routingtechnik

2.3 Routingtechnik

• Beschreibt wie und entlang welchen Pfades eine Nachricht im Netzwerk verschickt wird

• Setzt sich aus zwei Teilen zusammen: - Routingalgorithmen: bestimmen den Pfad einer

Nachricht durch das Netzwerk - Switching-Strategien: legen fest, ob und wie eine

Nachricht in Teile zerlegt wird und regeln die Allokation von Verbindungen

Die Kombination aus Routingalgorithmen, Switching-Strategien und der Topologie des Netzwerks beeinflussen imwesentlichen dessen Geschwindigkeit.

13

3. Arten von Verbindungsnetzwerken

3.1 Statische Verbindungsnetzwerke

3.2 Einbettung statischer Verbindungsnetzwerke

3.3 Dynamische Verbindungsnetzwerke

14

3. Arten von Verbindungsnetzwerken – Statische Verbindungsnetzwerke

3.1 Statische Verbindungsnetzwerke

3.1.1 Einordnung statischer Verbindungsnetzwerke

3.1.2 Anforderungen an ein Verbindungsnetzwerk

3.1.3 Topologien statischer Verbindungsnetzwerke

15

3. Arten von Verbindungsnetzwerken–Einordnung statischer V.-Netzwerke

3.1.1 Einordnung statischer Verbindungsnetzwerke

• Netzwerke mit fest verdrahteten Knoten (Speichereinheiten, Prozessoren) werden als statische oder direkte Verbindungsnetzwerke bezeichnet

• Anordnung der Komponenten im ungerichteten Kommunikationsgraphen G = (V,E)

(mit V = Menge der Knoten und E = Menge der Kanten)

• 4 Bewertungskriterien für die Topologie eines Verbindungsnetzwerkes: Durchmesser, Grad, Bisektionsbandbreite, Knotenkonnektivität

16


Durchmesser

• Beschreibt die maximale Distanz zwischen zwei beliebigen Knoten des Netzwerks

• Maß der maximalen Dauer für den Transport einer Nachricht vom Startknoten u zum Zielknoten v

• Formel:

}}|{min{max)( , vnachuvonPfadesdesLängeistkkG Vvu

17


1

4

7 4 9

6

8

32

5

Hier ist die Distanz von Knoten Nr.1 zu Knoten Nr. 9 maximal 4.

Durchmesser = 4

Beispiel für den Durchmesser eines Netzwerks:

18


Grad (eines Netzwerks)

• entspricht dem größten Grad eines Knotens des Netzwerks

• Grad eines Knotens ist zu bestimmen aus den adjazenten (ein-/ausgehenden) Kanten des Knotens

• Je höher der Grad eines Netzwerks ist, desto komplexer werden die Berechnungen für die Versendung einer Nachricht über das Netzwerk.

• Formel: } von vGrad)(|)(max{)( VvgvgGg

19


Beispiel für den Grad eines Netzwerks:

1

4

7 4 9

6

8

32

5

Knoten Nr. 5 hat mit vier Verbindungen den größten Grad dieses Netzwerks.

Grad des Netzwerks = 4

20


Bisektionsbandbreite (oder Bisektionsbreite)

• Nennt die minimale Anzahl an Kanten, die entfernt werden müssen, um das Netzwerk in zwei gleichgroße Teilnetzwerke zu zerteilen.*

• Drückt das Maß an Belastbarkeit des Netzwerks bei gleichzeitiger Übertragung von Nachrichten aus

• Formel:

* Diese müssen die bis auf 1 identische Anzahl an Knoten aufweisen !

},|),{()( 211

min21

UvUuEvuGBUU

VvonPartitionUUmit 21 ,

21


Beispiel für die Bisektionsbandbreite eines Netzwerks:

Durch entfernen von 4 Kanten kann hier das Netzwerk in

zwei Netzwerke geteilt werden.

Bisektionsbandbreite = 4

1

4

7 4 9

6

8

32

5

1

4

7

2

4 9

6

8

3

5

22


Knotenkonnektivität

• Beschreibt die Anzahl der Knoten, die entfernt werden müssen, um das Netzwerk in zwei Teile zu teilen (nicht zwei gleiche Teile – nur Verbindung unterbrechen!)

• Maß für den Zusammenhang im Netzwerk

• Je höher die Knotenkonnektivität desto höher die Ausfallsicherheit des Netzwerks

• Formel:

bezeichnet den Restgraphen, der nach Löschen der Knoten von und den dazugehörigen

Kanten entsteht.

},\,|{)( \min gibtvnachuvonPfadkeinenGinesdasssoMVvuexistierenesMGnc MVVM

MVG \ VM

23


Beispiel für Knotenkonnektivität:

1

4

7 4 9

6

8

32

5

Entfernen von 2 Knoten...

Die Knotenkonnektivität beträgt hier 2, da 2 Knoten aus dem Netzwerk entfernt werden müssen, um die Verbindungenvollständig zu trennen. (Hier ist z.B. keine Verbindung zwischen 1 und dem Rest des Netzwerks mehr möglich.)

1

7 4 9

6

8

3

5

24

3. Arten von Verbindungsnetzwerken – Anforderungen an ein V.-Netzwerk

3.1.2 Anforderungen an ein Verbindungsnetzwerk

Ein optimales Verbindungsnetzwerk sollte folgende

Anforderungen erfüllen:

• geringer Durchmesser geringe Distanzen für Nachrichtenversand

• kleiner Grad der Knoten weniger Rechenaufwand

• hohe Bisektionsbandbreite + hohe Konnektivität

großer Datendurchsatz bei hoher Zuverlässigkeit

• Skalierbarkeit leichte Erweiterung um weitere Knoten

25

3. Arten von Verbindungsnetzwerken–Topologien statischer V.-Netzwerke

3.1.3 Topologien statischer Verbindungsnetzwerke

Folgende statische Verbindungsnetzwerke werden vorgestellt:

• vollständiger Graph

• Ring

• d-dimensionales Gitter

• k-dimensionaler Würfel

• vollständiger binärer Baum

26


Vollständiger Graph

• Alle Knoten sind direkt miteinander verbunden

• Jedes Netzwerk lässt sich hierin einbetten

• Durch hohen Knoten und Kantengrad nur für wenige Prozessoren zu realisieren

27


Durchmesser:

Grad:

Konnektivität:

Bisektionsbreite: (für gerade n)

1)( G1)( nGg

1)( nGnc

4)(

2nGB

28


Ring

• Sequentielle Anordnung der Knoten mit je genau einem Nachfolger und einem Vorgänger

• der letzte Knoten ist mit dem ersten Knoten verbunden, somit ist der Ring geschlossen

• bei kleiner Prozessorzahl auch heute noch in Verwendung

29


Durchmesser:

Grad:

Konnektivität:

Bisektionsbreite:

2

)(n

G2)( Gg

2)( Gnc2)( GB

30


d-dimensionales Gitter / Feld

• Besteht aus Knoten, die ein d-dimensionales Feld aufspannen

• bezeichnet die Ausdehnung des Feldes in der Dimension d

dnnnn ...21

dn

31


Durchmesser:

Grad:

Konnektivität:

)1()( d ndGdGg 2)(

dGnc )(

Abbildung: 2-dimensionales Gitter

32


k-dimensionaler Hyperwürfel

• besteht aus Knoten

• rekursiver Aufbau aus Würfeln tieferer Dimensionen

• jedem Knoten wird ein Bitwort der Länge k zugeordnet, um Distanzen zwischen Knoten einfach zu bestimmen

• die Benennung der Knoten folgt dabei dem gespiegelten Gray-Code-Verfahren

kn 2

33


Gespiegeltes Gray Code Verfahren:

• Bei einem Dimensionssprung im Würfel verdoppeln sich die Knoten im Netzwerk

• Bit-Wörter von vorhandenen Knoten bekommen eine ‚0‘ vorangestellt

• Die neu hinzugekommenen Knoten erhalten die Bitwörter der schon vorhandenen Knoten, aber mit einer zusätzlichen ‚1‘ vorangestellt

• Direkt miteinander verbundene Knoten unterscheiden sich nur in einem Bit ihres Namens

• Einfache Berechnung der Distanzen zwischen Knoten (Unterschiede in Bitstellen zweier gleichlanger Bitworte = „Hamming-Distanz“)

34


Beispiel für gespiegeltes Gray-Code-Verfahren bei der

Benennung der Knoten eines Hyperwürfels:

0 1

00 01

10 11

000 001

011010

111110

100 101

1-dimensionaler Hyperwürfel



Durch Dimensionssprung hinzugekommene Knoten: Durch Dimensionssprung vorangestelltes Bit: 0 oder 1

35


000 001

011010

111110

100 101

Durchmesser:

Grad:

Konnektivität:

kG )(kGg )(

kGnc )(

36


vollständiger binärer Baum

• Besteht aus Knoten

• Darstellung einer kompletten binären Baumstruktur

• Jeder Knoten (bis auf die Endknoten auf unterster Stufe) ist mit zwei Kindknoten verbunden

12 kn

37


Durchmesser:

Grad:

Konnektivität:

3)( Gg1)( Gnc

2

1log2)(

nG

38

3. Arten von Verbindungsnetzwerken - Einbettung statischer V.-Netzwerke

3.2 Einbettung statischer Verbindungsnetzwerke

• Eingebettet werden meist Ring- und Gitternetzwerk in 2-dimensionale Gitter oder k-dimensionale Hyperwürfel

• Eine höhere Belastung des Zielnetzwerkes wird durch den Streckungsgrad von 1 vermieden

• Da Einbettung eines Rings oder Gitters in ein gleichdimensionales Netzwerk einfach ist (Beispiel), wird hier die Einbettung in einen Hyperwürfel vorgestellt

39


Einbettung eines Rings in einen k-dimensionalen Würfel

• Um einen Ring mit Knoten in einen k-dimensionalen Hyperwürfel einzubetten, müssen alle Knoten des Rings auf die Knotenmenge abgebildet werden

• Die Kanten des Rings sollen dabei auf den Kanten E des Würfels liegen

• Die Benennung der Knoten im Hyperwürfel folgt dem Gray-Code-Verfahren, im Ring einer Zahlenfolge von 1 bis n, daher kann die Einbettung durch folgende Abbildung ausgedrückt werden:

},...,1{' nV

kn 2

kV }1,0{'),( Eji

)(:)(}1,0{},...,1{: iRGCimitn kk

( meint das i-te Element der Gray-Code-Folge ). )(iRGCk )(iRGCk

40


Beispiel: Einbettung eines Rings in einen k-dimensionalen Würfel

010001

100

110

011

101 111

000

Ring mit 8 Knoten

000

010

001

100

110

011

101

111

3-d. Hyperwürfel

41


Einbettung eines 2-dimensionalen Gitters in einen k-dimensionalen Würfel

• Um ein Gitter mit Knoten in einen k-dimensionalen Hyperwürfel mit Knoten einzubetten, wird die Knotenmenge des Gitters in zwei Teilmengen aufgeteilt: und

• dabei gilt k als Dimension des Würfels mit:

• Für jede dieser Mengen wird eine Gray-Code-Folge erstellt: und

21 nnn kn 2

121kn 222

kn 21 kkk

),...,(11 1 nk aaRGC ),...,(

22 1 nk bbRGC

42


• Aus den beiden Gray-Code-Folgen wird eine Matrix M nach folgendem Schema erstellt:

• Alle Elemente der Matrix sind Bitwörter der Länge k und unterscheiden sich jeweils in nur einem Bit voneinander

• Alle Knotennamen eines k-dimensionalen Hyperwürfels sind in dieser Matrix vorhanden

21 nn

2111

2

21

12

12111

nnnn

n

bababa

ba

bababa

M

43


• folgende Formel beschreibt die Einbettung mathematisch:

• Als Beispiel: 2x4 Gitter in 3-dimensionalen Würfel

),()),((}1,0{},...,1{},...,1{: 21 jiMjimitnn k

000010 001

100110

011

101111

000

010

001

100

110

011

101

111

44

3. Arten von Verbindungsnetzwerken – Dynamische V.-Netzwerke

3.3 Dynamische Verbindungsnetzwerke

3.3.1 Einordnung dynamischer Verbindungsnetzwerke

3.3.3 Topologien dynamischer Verbindungsnetzwerke

45

3. Arten von Verbindungsnetzwerken–Einordnung dynamische V.-Netzw.

3.3.1 Einordnung dynamischer Verbindungsnetzwerke

• Im Gegensatz zu statischen Netzwerken keine feste Punkt-zu-Punkt-Verbindung

• Aufgebaut aus physikalischen Leitern und dazwischenliegenden Schaltern

• Verbindung einzelner Knoten bei Bedarf• Deshalb auch Bezeichnung: indirekte

Verbindungsnetzwerke• Verwendung meist in Systemen mit gemeinsam genutzten

Speicher• Zur Einordnung: heranziehen topologischer Merkmale• Je komplexer ein Netzwerk ist, desto höher sind die

Hardwarekosten aber auch die Leistung des Netzwerks

46

3. Arten von Verbindungsnetzwerken–Topologien dynamische V.-Netzw.

3.3.2 Topologien dynamischer Verbindungsnetzwerke

Folgende dynamische Verbindungsnetzwerke werden

vorgestellt:

• „Crossbar“-Netzwerk

• „Omega“-Netwerk

• „Butterfly“(„Banyan“)-Netzwerk

• „Benes“-Netzwerk

47


„Crossbar“-Netzwerk

• Höchste Verbindungskapazität zwischen Knoten• Ein „Crossbar“-Netzwerk besitzt n Eingänge (P), m

Ausgänge (M) und Schalter• Die Schalter können eine Nachricht entweder geradeaus

oder nach unten weiterleiten• Höchstens ein Schalter pro Spalte darf auf Umleiten

gesetzt werden, da sonst nicht der kürzeste Weg durchs Netzwerk gewählt wird

• Mögliche Schalterstellungen:

mnmn

Nicht umleiten Umleiten

48


P1

P2

Pn

M1 M2 Mm

n x m „Crossbar“-Netzwerk

Schalter wird auf umleitengesetzt !

Nachricht von P2 nach M2:

49


2x2 „Crossbar“-Schalter

• Die weiteren dynamischen Netzwerke, die häufig in der Praxis verwendet werden, sind aus Knoten und dazwischenliegenden 2x2 „Crossbar“-Schaltern aufgebaut

• Folgende vier Schalterstellungen sind damit möglich:

straight

crossover

lower broadcast

upper broadcast

50


„ Omega“-Netzwerk

• Ein „Omega“-Netzwerk besteht aus 2x2-“Crossbar“-Schaltern, die in Stufen angeordnet sind

• Je Stufe Schalter mit einem Bitwort und der Stufenzahl bezeichnet

• Beispiel: ein 2-dimensionales „Omega“-Netzwerk hat dann je 4 Schalter pro Stufe: bei 3 Stufen insgesamt 12 Schalter

• Dimension k des Netzwerks: Stufenanzahl - 1

nnnlog

2

n)1(log n

51


• Die festen Verbindungen im Netzwerk zwischen den einzelnen Stufen folgen einer Regel:

Es gibt eine Kante von Schalter ( ,i) in Stufe i zu den

beiden Schaltern ( ,i+1) in Stufe i+1, die dadurch

definiert sind, dass

- entweder durch einen zyklischen Linksshift aus

hervorgeht oder

- dadurch entsteht, dass nach einem zyklischen

Linksshift von das letzte Bit invertiert wird.

52


Ein 2-dimensionales „Omega“-Netzwerk:

Stufe 0 Stufe 1 Stufe 2

00

01

10

11

...

- entweder durch einen zyklischen

Linksshift aus hervorgeht oder

- dadurch entsteht, dass nach einem

zyklischen Linksshift von das letzte

Bit invertiert wird.

53


„ Butterfly“(„Banyan“)-Netzwerk

• Die Anzahl an Kanten, Schaltern und Knoten unterscheidet sich nicht von einem „Omega“-Netzwerk

• Nur die Bildungsregel für die festen Verbindungen unterscheidet sich:

Es gibt eine Kante von Schalter ( ,i) in Stufe i zu den

beiden Schaltern ( ,i+1) in Stufe i+1, die dadurch

definiert sind, dass

- und identisch sind (straight edge - direkte

Kante)

- und sich nur im (i+1)-ten Bit von links

unterscheiden (cross edge – Kreuzkante)

54


Ein 2-dimensionales „Butterfly“-Netzwerk:


00

01

10

11

...- und identisch sind (straight

edge - direkte Kante)

- und sich nur im (i+1)-ten Bit

von links unterscheiden (cross edge –

Kreuzkante)

55


„ Benes“-Netzwerk

• Ein k-dimensionales „Benes“-Netzwerk setzt sich aus zwei

k-dimensionalen „Butterfly“-Netzwerken zusammen

• Die ersten k+1 Stufen bilden ein reguläres „Butterfly“-Netzwerk

• Die letzten k+1 Stufen ein umgekehrtes „Butterfly“-Netzwerk

• Die letzte Stufe des regulären und die erste Stufe des umgedrehten Netzwerks fallen aufeinander

56


Ein 2-dimensionales „Benes“-Netzwerk:


00

01

10

11

Stufe 3 Stufe 4

57

4. Routingtechnik

4.1 Routingalgorithmen

4.2 Switching-Strategien

58

4. Routingtechnik – Routingalgorithmen

4.1 Routingalgorithmen

4.1.1 Einordnung von Routingalgorithmen

4.1.2 Deterministische Routingalgorithmen

4.1.3 Adaptive Routingalgorithmen

59

4. Routingtechnik – Einordnung von Routingalgorithmen


Drei Punkte sind bei der Pfadbestimmung im Netzwerk im

Besonderen zu beachten:

• Topologie: Verbindungswege von Knoten a zu Knoten b hängen vom Aufbau des Netzwerk ab

• Contention (=Auseinandersetzung): zwei oder mehr Nachrichten sollen über dieselbe Kante verschickt werden Wartezeiten

• Congestion (=Stau): viele Nachrichten sollen über dieselbe Kante verschickt werden; der Puffer wird voll Nachrichten werden verworfen

60


Im schlimmsten Fall kommt es in einem Netzwerk zu einem

„Deadlock“: Dieser tritt auf wenn jede Verbindungskante, die

von einer Nachricht aus einer Menge von Nachrichten genutzt

werden soll, schon von einer Nachricht derselben Menge

benutzt wird. Somit lässt sich keine Nachricht dieser Menge

weiterschicken, und der Verkehr im Netzwerk steht still.

61



Ziel eines Routingalgorithmus:

• Vermeiden von Wartezeiten, Staus

• Deadlockfreiheit (lässt sich durch Kanalabhängigkeitsgraphen darstellen und beweisen:

Diese werden hier jedoch aufgrund der Komplexität, auch schon für kleine Netzwerke,

nicht näher erläutert.)

62


Routingalgorithmen lassen sich in zwei Klassen einteilen:

• Deterministischer Ansatz: Wahl des Pfades nur Abhängig von Start- und Zielknoten der Nachricht

• Adaptiver Ansatz: mehrere Pfade werden unter Berücksichtigung der Auslastung des Netzwerks berechnet

Bei beiden Ansätzen gibt es zwei Varianten:

• minimale Algorithmen: wählen immer den kürzesten Weg

• nichtminimale Algorithmen: erlauben auch Umwege, um Staus zu vermeiden

63

4. Routingtechnik – Deterministische Routingalgorithmen

4.1.2 Deterministische Routingalgorithmen

Dimensionsgeordnetes Routing

• XY-Routing (im 2-dimensionalen Gitter)

• E-Cube-Routing (im k-dimensionalen Hyperwürfel)

64


XY-Routing (im 2-dimensionalen Gitter)

• Knoten werden mit XY-Koordinaten beschrieben

• Nachricht von Knoten A zu Knoten B läuft erst nach links

oder rechts in horizontaler (x)-Richtung und dann hoch

oder runter in vertikaler (y)-Richtung bis zum Zielknoten

• Deadlockfreiheit durch Kanalabhängigkeitsgraph beweisbar, da keine Zyklen auftreten

65


Beispiel für XY-Routing:Pfad von Knoten A mit Position (x:1,y:2) zu Knoten B mit Position (x:4,y:1)

X-Achse

Y-Achse

A

B

x:1 x:3x:2 x:4 x:5

y:1

y:2

y:3

x:4,y:2

x:1,y:2

x:4,y:1

66


E-Cube-Routing (im k-dimensionalen Hyperwürfel)

• Knoten haben k-Bitworte als Bezeichnung

• Durch Invertieren jedes einzelnen Bits eines solchen Bitwortes können alle direkt miteinander verbundenen Knoten gefunden werden

• Eine Nachricht von Knoten A mit Bitnamen

soll an Knoten B mit Bitnamen verschickt werden, wobei mit Bitdarstellung ein Knoten auf dem Weg von A nach B ist

1... k

10 ... k

iA 10 ... k

67


Bei jedem Knoten auf dem Weg wird dies berechnet:

• berechnet das k-Bitwort

(bitweise ausschließendes ODER)

• und schickt die Nachricht in Richtung der Dimension d

(d ist die am weitesten rechts liegende Position von

mit dem Wert 1)

• Den zugehörigen Knoten erhält man durch die Invertierung des d-ten Bits

Auch für E-Cube-Routing lässt sich Deadlockfreiheit

beweisen.

iA

iA

1iA

68


Beispiel für E-Cube-Routing:Pfad von Knoten A (110) nach Knoten B (001)

000 B:001

011010

111A:110

100 101

001 110

d iA

111 1 111111 110 2 101101 100 3 001

69


Quellenbasiertes Routing

• Sender wählt den kompletten Pfad selbst aus und hängt die nacheinander auszuwählenden Ausgabekanäle als Header an die Nachricht an

• Bei jedem Knoten wird der Header überprüft, und der gerade passierte Ausgabekanal aus dem Header entfernt

• Die Nachricht wird über den nächsten Ausgabekanal weiterverschickt

70


Tabellenorientiertes Routing

• jeder Knoten des Netzwerks beinhaltet eine Tabelle mit Routinginformationen

• zu jeder Zieladresse ist der zu wählende Pfad eingetragen

71


Routing nach dem Turn-Modell

• Durch geschickt vorgegebene Richtungswechsel sollen Deadlocks vermieden werden

• Es werden einfach bestimmte Richtungswechsel verboten

• (z.B. ist beim XY-Routing nur ein einziger Richtungswechsel erlaubt!)

• Ein solches Modell für 2-dimensionale Gitter ist das West-First Routing

72


West-First Routing

• Von 8 möglichen Richtungswechseln in einem 2-dimensionalen Gitter ist der Richtungswechsel nach Westen nicht erlaubt

• Zuerst wird daher immer in Richtung Westen versendet, bis die nötige x-Koordinate erreicht ist

• Danach in die anderen möglichen Richtungen (Nord, Süd, Ost)

• Mögliche Richtungswechsel beim West-First Routing:

Erlaubte Richtungswechsel

Nicht erlaubte Richtungswechsel

N

S

OW

73


Beispiel für West-First Routing: von Knoten A zu Knoten B und zurück von B nach A

N

S

OW

blockierte Verbindungen

B

A

74

4. Routingtechnik – Adaptive Routingalgorithmen

4.1.3 Adaptive Routingalgorithmen

Hier werden zwei Konzepte herausgegriffen und vorgestellt:

• Virtuelle Kanäle (z.B. der minimal adaptive Routingalgortihmus) und

• Routing im „Omega-Netzwerk“

75


Virtuelle Kanäle

• Mehrere virtuelle Verbindungen zwischen zwei benachbarten Knoten werden bereitgestellt

• Dazu wird eine vorhandene Verbindungskante in mehrere gleichberechtigte Kanäle unterteilt

• Jeder Kanal besitzt einen Pufferspeicher, um Nachrichten zwischenzuspeichern (bis er an der Reihe ist)

• Ein Beispiel für das Konzept der virtuellen Kanäle ist der

minimal adaptive Routingalgorithmus

76


Minimal adaptiver Routingalgorithmus

• Teilt das gegebene Netzwerk in zwei logische Teilnetzwerke X- und X+ ein, die sich nur in den vertikalen Verbindungen unterscheiden

• X+ enthält nur positive vertikale Verbindungen (nach rechst führende)

• X- enthält nur negative vertikale Verbindungen (nach links führende)

• So kann je nach Auslastung des Netzwerks und Richtung des Pfades eines der beiden Teilnetze verwendet werden

• (für 2-dimensionale Gitter deadlockfrei)

77


Beispiel für minimal adaptiven Routingalgorithmus:

Aufteilung in virtuelle Kanäle

„X+“-Teilnetz „X-“-Teilnetz

78


Routing im „Omega“-Netzwerk

• Nachrichten werden anhand eines verteilten Kontrollschemas weitergeleitet

• Hierzu kann jeder Schalter ohne Koordination mit anderen Schaltern eine Nachricht weiterleiten

• Die n Ein- und Ausgabekanäle haben Bitnamen der Länge

wobei der Eingangskanal den Bitnamen und der Ausgangskanal den Bitnamen trägt

• Bei Weiterleitung muss nun der Schalter auf Stufe k mit

das k-te Bit (von links) des Ausgangskanals untersuchen und folgende Schritte unternehmen:

nlog

1log,...,0 nk k

79


• Ist das k-te Bit , so wird die Nachricht auf den oberen Ausgang des Schalters gelegt

• Ist das k-te Bit , so wird die Nachricht auf den unteren Ausgang des Schalters gelegt

Nur Nachrichten können gleichzeitig ohne Blockierung

gesendet werden (Außer im nicht-blockierenden „Benes“-

Netzwerk).

0k

1k

2

n

n

80


Beispiel für Routing im „Omega“-Netzwerk: von 010 nach 110

000001

010011

100101

110111

000001

010011

100101

110111


81

4. Routingtechnik – Switching-Strategien

4.2 Switching-Strategien

4.2.1 Einordnung von Switching-Strategien

4.2.2 Arten von Switching-Strategien

82

4. Routingtechnik – Einordnung von Switching-Strategien

4.2.1 Einordnung von Switching-Strategien

• Die Übertragung von Nachrichten zwischen benachbarten Prozessoren wird durch die Software des Prozessors (einem Protokoll folgend: ähnlich TCP/IP) übernommen

• Um die Schritte auszuführen wird eine gewisse Zeitspanne benötigt

• Diese Zeitspanne die der Prozessor zur Bearbeitung benötigt zuzüglich der Zeitspanne, die die Nachricht unterwegs ist, nennt man Latenzzeit

• Zur Beschreibung der Latenz und damit der Effizienz einer Switching-Strategie werden folgende Merkmale unterschieden:

83


• Bandbreite: maximale Frequenz der Datenübertragung in (Bytes/Sekunde)

• Bytetransferzeit: benötigte Zeit um ein Byte zu verschicken

• Übertragungszeit: benötigte Zeit um eine komplette Nachricht zu verschicken

• Signalverzögerungszeit: Zeitspanne zwischen Abschicken und Ankommen des ersten Bits beim Empfänger

• Transportlatenz: Verweildauer der Nachricht im Netzwerk

• Senderoverhead oder Startupzeit: benötigte Zeit, um Nachricht auf das Senden vorzubereiten

• Empfängeroverhead: benötigte Zeit um Nachricht zu empfangen

• Durchsatz: Netzwerkbandbreite bei einer Anwendung

BandbreiteerzeitBytetransf

1

Bandbreite

ngrößeNachrichtegszeitÜbertragun

szeitÜbertragunitögerungszeSignalverzatenzTransportl

84


Die gesamte Latenz setzt sich somit aus vier Komponenten

zusammen:

Unter Voraussetzung eines konstanten Overheads und einer

Punkt-zu-Punkt-Verbindung zwischen zwei Prozessoren, lässt

sich folgende Laufzeitformel für die Latenz herleiten:

mit , und

Wird eine Nachricht über mehrere Verbindungsleitungen

verschickt, kann dies durch folgende Switching-Strategien

erfolgen.

verheadEmpfängeroBandbreite

ngrößeNachrichteögerungSignalverzheadSenderoverLatenz

mttmT BS )(

tStartupzeitS erzeitBytetransftB ngrößeNachrichtem

85


Illustration aus Rauber, T. und G. Rünger: Parallele und verteilte Programmierung. Springer 1998.

Senderoverhead

Empfängeroverhead

Signal-verzögerung Übertragungszeit

Übertragungszeit

Transportlatenz

Gesamtlatenz

Zeit:

Beim Sender

Beim Empfänger

Im Netzwerk

Gesamtzeit

86

4. Routingtechnik – Arten von Switching-Strategien

4.2.2 Arten von Switching-Strategien

Zwei Grundformen der Switching-Strategien werden

erläutert:

• Das Circuit-Switching und

• das Paket-Switching in zwei Varianten: dem „Store-and-Forward-Routing“ und dem „Cut-Through-Routing“

87


Circuit-Switching

• Der gesamte Pfad vom Quell- zum Zielknoten wird der Nachrichtenübertragung zur Verfügung gestellt und erst wieder freigegeben, wenn die Nachricht vollständig übertragen wurde

• Intern wird die Nachricht in Teilstücke (phits: physical units) eingeteilt

• Ein „phit“ bezeichnet die Datenmenge, die pro Takt über eine Verbindungsleitung geschickt werden kann (1-64 bits)

• Zuerst wird eine kurze Nachricht („probe“) zum Aufbau der Verbindung verschickt; danach alle „phits“ der Nachricht und zum Schluss gegebenenfalls eine Empfangsbestätigung (zum Freigeben des Pfades)

88


Kosten des Circuit-Switching:

• Kosten der Kontrollnachricht („probe“) zum Aufbau des Pfades der Länge beträgt:

• wobei die Kosten zum Versenden der Kontrollnachricht je Verbindung bezeichnet

( : Größe des Kontrollpakets, : Bytetransferzeit )

• Die Gesamtkosten zum Versenden der eigentlichen Nachricht der Größe betragen somit:

ltC l

CBC mtt

Cm Bt

mtlttlmT BCSCS ),(

m

Reine Kosten des Sendens der Nachricht

Kosten der KontrollnachrichtStartupzeit

89



Aktivitäten und Latenzzeit bei einer Einzeltransferoperation über einenPfad der Länge l = 4 unter Verwendung von Circuit-Switching:

Knoten

Zeit (Aktivität des Knotens)

Quelle 0

1

2

3

Aufbau des Pfades(„probes“)

Gesamter Pfad ist für die Nachrichtenübertragung aktiv

1 2 30 ZielQuelle

90


Paket-Switching

• die Nachricht wird in Teilstücke „Pakete“ unterteilt, die unabhängig voneinander über das Netzwerk zum Ziel geschickt werden

(auch die einzelnen Pakete sind wieder in „phits“ aufgeteilt)

• Bei Verwendung von adaptiven Routingalgorithmen werden somit unterschiedliche Pfade zum Versenden benutzt

• Jedes Paket besteht aus 3 Teilen: dem Header (mit Routing- und Kontrollinformationen), dem reinen Datenteil und dem Endstück mit Fehlerkontrollcodes

91


Eine Variante des Paket-Switching ist das

„Store-and-Forward-Routing“

• In jedem Knoten (auf dem Pfad) wird das Paket vollständig zwischengespeichert, bevor es weitergeschickt wird

• Dadurch kann die gerade benutzte Kante schnell freigegeben werden

• Nachteil: hohe Speicherkapazität im Knoten erforderlich

• Vorteil: geringere Deadlock-Gefahr

92


Kosten des „Store-and-Forward-Routing“ (bzw. des

Versendens eines Paketes):

• Konstante Zeit in jedem Knoten, zum Kontrollieren des Headers und wählen des Ausgabekanals:

• Zeit zur Versendung des Pakets der Größe m zum nächsten Knoten:

• Die Gesamtkosten zur Versendung eines Paketes auf einem Pfad der Länge betragen somit:

ht

mtB

l

)(),( mttltlmT BhSSF Startupzeit

Zeit pro Knoten (Headerkontrolle) + Versendung zum nächsten Knoten * Pfadlänge

93



Aktivitäten und Latenzzeit bei einer Einzeltransferoperation über einenPfad der Länge l = 4 unter Verwendung vonStore-and-Forward-Routing:

Knoten


Quelle 0

1

2

3

1 2 30 ZielQuelle

H

Übertragung über erste Verbindung

H

Übertragung über zweite Verbindung

H

Übertragung über dritte Verbindung

H

Übertragung über vierte Verbindung

94


Eine zweite Variante des Paket-Switching ist das

„Cut-Through-Routing“

• Auch hier Einteilung in Pakete und „phits“ wie bei Store-and-Forward-Routing

• Im Unterschied zu SFR wird, sobald der Header im nächsten Knoten angekommen ist, eine neue Verbindung zum nächsten Knoten aufgebaut, bevor(!) alle „phits“ des Paketes übertragen wurden

• Alle „phits“ werden auf dem selben Pfad dem Header hinterhergeschickt

• Die Verbindungskante wird erst freigegeben, sobald alle „phits“ eines Paketes übertragen wurden (wie bei SFR)

95


Kosten des „Cut-Through-Routing“ (bzw. des Versendens

eines Paketes):

• Zeit für Übertragung des Headers:

(mit = Größe des Headers)

• Gesamtkosten für Übertragung eines Paketes bei

Pfadlänge :

HBH mtt

Hm

l

)(),( HBHSCT mmttltlmT Startupzeit

Kosten für Headerübetragung

über die Pfadlänge

Kosten für Übertragung der restlichen Nachricht (nur einmal, da immer gleich hinterhergeschickt! Siehe Grafik nächste Folie)

96



Aktivitäten und Latenzzeit bei einer Einzeltransferoperation über einenPfad der Länge l = 4 unter Verwendung vonCut-Through-Routing:

Knoten


Quelle 0

1

2

3

1 2 30 ZielQuelle

Übertragung desHeaders

Übertragung des Paketes

H

H

H

H

97

5. Fazit

Dies sollte vermittelt werden:

• Grundlagen der existierenden Verbindungsnetzwerke

• Grundlagen der Einbettung von Verbindungsnetzwerken

• Einige spezielle Routing-Algorithmen und Switching- Strategien

98

Fragen ?

99


1

2

3 4 5

6

4

78 1

2

3 4 5

67

8

N‘ N

Zurück

Documents

Verbindungsnetzwerke, Einbettungen, Routing- und Switchingstrategien Seminar „Parallele Programmierung“ Gunnar Thies