Date post: | 06-Apr-2015 |
Category: |
Documents |
Upload: | karoline-weissinger |
View: | 113 times |
Download: | 3 times |
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
2. Grundbegriffe - Einbettung
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
2. Grundbegriffe - Einbettung
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
2. Grundbegriffe - Einbettung
Einbettung eines Netzwerks N‘ in N mit Streckungsgrad 1:
1
2
3 4 5
6
4
78 1
2
3 4 5
67
8
Einbettung eines Netzwerks N‘ in N mit Streckungsgrad 3:
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
3. Arten von Verbindungsnetzwerken–Einordnung statischer V.-Netzwerke
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
3. Arten von Verbindungsnetzwerken–Einordnung statischer V.-Netzwerke
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
3. Arten von Verbindungsnetzwerken–Einordnung statischer V.-Netzwerke
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
3. Arten von Verbindungsnetzwerken–Einordnung statischer V.-Netzwerke
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
3. Arten von Verbindungsnetzwerken–Einordnung statischer V.-Netzwerke
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
3. Arten von Verbindungsnetzwerken–Einordnung statischer V.-Netzwerke
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
3. Arten von Verbindungsnetzwerken–Einordnung statischer V.-Netzwerke
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
3. Arten von Verbindungsnetzwerken–Einordnung statischer V.-Netzwerke
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
3. Arten von Verbindungsnetzwerken–Topologien statischer V.-Netzwerke
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
3. Arten von Verbindungsnetzwerken–Topologien statischer V.-Netzwerke
Durchmesser:
Grad:
Konnektivität:
Bisektionsbreite: (für gerade n)
1)( G1)( nGg
1)( nGnc
4)(
2nGB
28
3. Arten von Verbindungsnetzwerken–Topologien statischer V.-Netzwerke
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
3. Arten von Verbindungsnetzwerken–Topologien statischer V.-Netzwerke
Durchmesser:
Grad:
Konnektivität:
Bisektionsbreite:
2
)(n
G2)( Gg
2)( Gnc2)( GB
30
3. Arten von Verbindungsnetzwerken–Topologien statischer V.-Netzwerke
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
3. Arten von Verbindungsnetzwerken–Topologien statischer V.-Netzwerke
Durchmesser:
Grad:
Konnektivität:
)1()( d ndGdGg 2)(
dGnc )(
Abbildung: 2-dimensionales Gitter
32
3. Arten von Verbindungsnetzwerken–Topologien statischer V.-Netzwerke
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
3. Arten von Verbindungsnetzwerken–Topologien statischer V.-Netzwerke
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
3. Arten von Verbindungsnetzwerken–Topologien statischer V.-Netzwerke
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
2-dimensionaler Hyperwürfel
3-dimensionaler Hyperwürfel
Durch Dimensionssprung hinzugekommene Knoten: Durch Dimensionssprung vorangestelltes Bit: 0 oder 1
35
3. Arten von Verbindungsnetzwerken–Topologien statischer V.-Netzwerke
000 001
011010
111110
100 101
Durchmesser:
Grad:
Konnektivität:
kG )(kGg )(
kGnc )(
36
3. Arten von Verbindungsnetzwerken–Topologien statischer V.-Netzwerke
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
3. Arten von Verbindungsnetzwerken–Topologien statischer V.-Netzwerke
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
3. Arten von Verbindungsnetzwerken - Einbettung statischer V.-Netzwerke
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
3. Arten von Verbindungsnetzwerken - Einbettung statischer V.-Netzwerke
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
3. Arten von Verbindungsnetzwerken - Einbettung statischer V.-Netzwerke
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
3. Arten von Verbindungsnetzwerken - Einbettung statischer V.-Netzwerke
• 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
3. Arten von Verbindungsnetzwerken - Einbettung statischer V.-Netzwerke
• 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
3. Arten von Verbindungsnetzwerken–Topologien dynamische V.-Netzw.
„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
3. Arten von Verbindungsnetzwerken–Topologien dynamische V.-Netzw.
P1
P2
Pn
M1 M2 Mm
n x m „Crossbar“-Netzwerk
Schalter wird auf umleitengesetzt !
Nachricht von P2 nach M2:
49
3. Arten von Verbindungsnetzwerken–Topologien dynamische V.-Netzw.
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
3. Arten von Verbindungsnetzwerken–Topologien dynamische V.-Netzw.
„ 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
3. Arten von Verbindungsnetzwerken–Topologien dynamische V.-Netzw.
• 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
3. Arten von Verbindungsnetzwerken–Topologien dynamische V.-Netzw.
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
3. Arten von Verbindungsnetzwerken–Topologien dynamische V.-Netzw.
„ 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
3. Arten von Verbindungsnetzwerken–Topologien dynamische V.-Netzw.
Ein 2-dimensionales „Butterfly“-Netzwerk:
Stufe 0 Stufe 1 Stufe 2
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
3. Arten von Verbindungsnetzwerken–Topologien dynamische V.-Netzw.
„ 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
3. Arten von Verbindungsnetzwerken–Topologien dynamische V.-Netzw.
Ein 2-dimensionales „Benes“-Netzwerk:
Stufe 0 Stufe 1 Stufe 2
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
4.1.1 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
4. Routingtechnik – Einordnung von Routingalgorithmen
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
4. Routingtechnik – Einordnung von Routingalgorithmen
4.1.1 Einordnung von Routingalgorithmen
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
4. Routingtechnik – Einordnung von Routingalgorithmen
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
4. Routingtechnik – Deterministische Routingalgorithmen
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
4. Routingtechnik – Deterministische Routingalgorithmen
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
4. Routingtechnik – Deterministische Routingalgorithmen
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
4. Routingtechnik – Deterministische Routingalgorithmen
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
4. Routingtechnik – Deterministische Routingalgorithmen
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
4. Routingtechnik – Deterministische Routingalgorithmen
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
4. Routingtechnik – Deterministische Routingalgorithmen
Tabellenorientiertes Routing
• jeder Knoten des Netzwerks beinhaltet eine Tabelle mit Routinginformationen
• zu jeder Zieladresse ist der zu wählende Pfad eingetragen
71
4. Routingtechnik – Deterministische Routingalgorithmen
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
4. Routingtechnik – Deterministische Routingalgorithmen
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
4. Routingtechnik – Deterministische Routingalgorithmen
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
4. Routingtechnik – Adaptive Routingalgorithmen
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
4. Routingtechnik – Adaptive Routingalgorithmen
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
4. Routingtechnik – Adaptive Routingalgorithmen
Beispiel für minimal adaptiven Routingalgorithmus:
Aufteilung in virtuelle Kanäle
„X+“-Teilnetz „X-“-Teilnetz
78
4. Routingtechnik – Adaptive Routingalgorithmen
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
4. Routingtechnik – Adaptive Routingalgorithmen
• 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
4. Routingtechnik – Adaptive Routingalgorithmen
Beispiel für Routing im „Omega“-Netzwerk: von 010 nach 110
000001
010011
100101
110111
000001
010011
100101
110111
Stufe 1 Stufe 2 Stufe 3
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
4. Routingtechnik – Einordnung von Switching-Strategien
• 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
4. Routingtechnik – Einordnung von Switching-Strategien
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
4. Routingtechnik – Einordnung von Switching-Strategien
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
4. Routingtechnik – Arten von Switching-Strategien
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
4. Routingtechnik – Arten von Switching-Strategien
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
4. Routingtechnik – Arten von Switching-Strategien
Illustration aus Rauber, T. und G. Rünger: Parallele und verteilte Programmierung. Springer 1998.
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
4. Routingtechnik – Arten von Switching-Strategien
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
4. Routingtechnik – Arten von Switching-Strategien
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
4. Routingtechnik – Arten von Switching-Strategien
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
4. Routingtechnik – Arten von Switching-Strategien
Illustration aus Rauber, T. und G. Rünger: Parallele und verteilte Programmierung. Springer 1998.
Aktivitäten und Latenzzeit bei einer Einzeltransferoperation über einenPfad der Länge l = 4 unter Verwendung vonStore-and-Forward-Routing:
Knoten
Zeit (Aktivität des Knotens)
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
4. Routingtechnik – Arten von Switching-Strategien
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
4. Routingtechnik – Arten von Switching-Strategien
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
4. Routingtechnik – Arten von Switching-Strategien
Illustration aus Rauber, T. und G. Rünger: Parallele und verteilte Programmierung. Springer 1998.
Aktivitäten und Latenzzeit bei einer Einzeltransferoperation über einenPfad der Länge l = 4 unter Verwendung vonCut-Through-Routing:
Knoten
Zeit (Aktivität des Knotens)
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
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
Zurück