Upload
others
View
1
Download
0
Embed Size (px)
Citation preview
Center for Information Services and High Performance Computing (ZIH)
Theorie und Einsatz von Verbindungseinrichtungen inparallelen Rechnersystemen
Routing in statischen Verbindungsnetzwerken
08. Juni 2012
Andy Georgi
INF 1046Nothnitzer Straße 4601187 Dresden
0351 - 463 38783
m
Agenda
1 Einfuhrung
2 Dead- und Livelocks
3 Klassifizierung von Routing-Algorithmen
4 Deterministisches Routing
5 Adaptives Routing
6 Literaturverzeichnis
2/53
Agenda
1 Einfuhrung
3/53
Routing I
DefinitionIm Allgemeinen wird die Festlegung des Weges einer Nachricht von einerQuelle zu einer oder mehrerer Senken als Routing bezeichnet. Dabeigreifen verschiedene, voneinander unabhangige, Mechanismen ineinanderund tragen zum Datentransport bei. Im engeren Sinne zahlen zumRouting der Verbindungsaufbau, die Dekodierung von Adressen, einegeeignete Datenflusssteuerung und optional eine alternative Wegewahl zurLeistungsoptimierung.
4/53
Routing II
Forderungen an die Datenubertragung:
Eintreffen der Nachricht an der Senke in endlicher ZeitMinimale Ubertragungszeit zu jedem beliebigen Zeitpunkt
Realisierung der minimalen Ubertragungszeit durch Auswahl der Routemit der
kurzesten physikalischen Entfernung,kleinsten Konfliktwahrscheinlichkeit oderder geringsten Auslastung
5/53
Routing II
Forderungen an die Datenubertragung:
Eintreffen der Nachricht an der Senke in endlicher ZeitMinimale Ubertragungszeit zu jedem beliebigen Zeitpunkt
Realisierung der minimalen Ubertragungszeit durch Auswahl der Routemit der
kurzesten physikalischen Entfernung,kleinsten Konfliktwahrscheinlichkeit oderder geringsten Auslastung
5/53
Herausforderungen
Globale Lastbalancierung
Keine Beschrankung auf eine spezielle Menge von Topologien
Geringe Laufzeiten fur den Einsatz in Produktivsystemen
Garantierte endliche Ubertragungszeiten fur beliebige – ggf. auchunvollstandige – Topologien
6/53
Agenda
2 Dead- und LivelocksBegriffserklarungDeadlocks in VerbindungsnetzwerkenAnsatze fur deadlockfreies RoutingKanalabhangigkeitsgraphSatz von Dally und Seitz [DaS87]Virtuelle Kanale und Kanalabhangigkeitsgraphen
7/53
Deadlock
Definition Deadlock [Tan07]
Eine Menge von Prozessen befindet sich in einem Deadlock-Zustand, wennjeder Prozess aus der Menge auf ein Ereignis wartet, welches nur ein andererProzess der Menge auslosen kann.
Notwendige Kriterien [CoE71]1 Betriebsmittel werden ausschließlich durch den Prozess freigegeben
2 Prozess fordert neue Betriebsmittel an, behalt aber Zugriff auf aktuelle
3 Exklusiver Zugriff auf die Betriebsmittel
4 Zyklische Abhangigkeit der Betriebsmittel fur zwei Prozesse
8/53
Livelock
DefinitionLivelocks verhindern wie Deadlocks eine Datenubertragung in endlicher Zeit.Dabei verharren die Prozesse jedoch nicht in einem Zustand, sondern anderndiesen permanent, ohne das dabei der Zielzustand erreicht wird.
9/53
Deadlocks in Verbindungsnetzwerken
Paketquelle
Puffer des Switch
Paketziel
Abbildung: Deadlock Situation in einem Gitter-Netz
10/53
Ansatze fur deadlockfreies Routing
Lebensdauer fur Pakete (nur zum Auflosen)
Controller Prinzip [Tou80]
Vermeidung zyklischer Abhangigkeiten durch Beschrankung dererlaubten Pfade (z.B. Up*/Down* [SBB91])
Eliminierung auftretender Zyklen durch den Einsatz virtueller Kanale
11/53
Virtuelle Kanale
Bereitstellung mehrerer virtueller Kanale pro physischem Link
Dynamische Zuteilung von Datenrate und Speicherplatz
Reduzierung von Verzogerungszeiten und Ausschluss von Deadlocksmoglich
Eliminierung zyklischer Wartebedingungen durch Verteilung derKommunikationen auf unterschiedliche virtuelle Kanale
Formale Beschreibung mit Hilfe von Kanalabhangigkeitsgraphen (engl.channel dependency graph) [DaS87]
12/53
Kanalabhangigkeitsgraph
Definition 1
Eine Route (c1, c2, . . . , cn) ist die Folge der Kanale, auf denen ein Paket vomSender zum Empfanger gelangt.Eine Routingfunktion R : C × N → C , R(ci , nd) := ci+1 weist jedem Paaraus aktuellem Kanal ci und Zielknoten nd den nachsten Kanal zu, dabei giltci 6= ci+1.
Definition 2Der Kanalabhangigkeitsgraph fur eine Routingfunktion und ein Netzwerk istder gerichtet Graph CDG = G (C ,E ). Dabei gilt fur die Kantenmenge E :
E = { (ci , cj) | R(ci , n) = cj fur n ∈ N bel. }
13/53
Satz von Dally und Seitz [DaS87]
DefinitionEine Routingfunktion fur ein Verbindungsnetzwerk ist genau dann deadlockfrei,wenn es keine Zyklen im zugehorigen Kanalabhangigkeitsgraphen gibt.
14/53
Virtuelle Kanale und Kanalabhangigkeitsgraphen I
c2c1
c3c4
n4
c1 n1c2
n2
c3n3c4
15/53
Virtuelle Kanale und Kanalabhangigkeitsgraphen II
c2,2c2,1
c1,1 c1,2
c1,3c1,4
c2,3c2,4
c2,2n1c2,1
c1,2c1,1
n2n4
c1,4 c1,3
c2,3n3c2,4
16/53
Virtuelle Kanale und Kanalabhangigkeitsgraphen III
c2
c3c4
c1r2
r3
r1
c1,2c1,1r2
r1
c1,3
r3
c2,1 c2,2
c2,4 c2,3
17/53
Gegenuberstellung I
Lebensdauer fur Pakete:
+ Meist einfache Implementierung+ Kann auch zum Auflosen von Livelocks verwendet werden− Nicht zur Vermeidung von Deadlocks geeignet
Controller-Prinzip:
+ Ermoglicht die Vermeidung oder ggf. auch die Auflosung vonDeadlocks und Livelocks− Single Point of Failure− Hohere Verzogerungszeiten− Steigender Aufwand mit zunehmender Anzahl an Kommunikationen
18/53
Gegenuberstellung II
Zyklenfreie Routingfunktion (z.B. Up*/Down*)
+ Keine zeitaufwendige Zyklensuche notig (s. Satz von Dally undSeitz [DaS87])− Nicht fur alle Topologien moglich (z.B. 2D-Torus)− Einschrankung der Bandbreite durch nicht nutzbare Links
Zyklen brechen, indem Pfade unterschiedlichen virtuelle Kanalezugewiesen werden (z.B. LASH [SLT02])
+ Hohere Bandbreite+ Nahezu beliebiege Topologien− Zeitaufwendige Zyklensuche− Anzahl der virtuelle Kanale ist beschrankt
19/53
Agenda
3 Klassifizierung von Routing-AlgorithmenSource Routing vs. Distributed RoutingDeterministisches vs. adaptives RoutingProgressives Routing vs. BacktrackingUmwegloses vs. umwegbehaftetes RoutingVollstandige vs. eingeschrankte Adaption
20/53
Source Routing vs. Distributed Routing
Source Routing
Wird die Verbindung zwischen Quelle und Senke ausschließlich von der Quelledefiniert, so spricht man vom Source Routing.
Distributed Routing
Beim Distributed Routing hingegen, wird lokal an jedem Zwischenknoten uberden weiteren Verlauf der Nachricht entschieden.
21/53
Deterministisches vs. adaptives Routing
Deterministisches Routing
Deterministische Routing Verfahren verwenden ausschließlich die Adressen vonQuelle und Senke als Berechnungsgrundlage. Somit ist der Weg einer Nachrichtzwischen einem Sender und einem Empfanger durch das Verbindungsnetzwerkstets identisch.
Adaptives Routing
Adaptive Routing Verfahren beziehen hingegen weitere Informationenmit in die Berechnung des Wegs ein, so dass dieser zwischen zweiKommunikationspartnern erst dynamisch zur Laufzeit definiert wird.
22/53
Progressives Routing vs. Backtracking
Progressives Routing
Bei Einsatz eines progressiven Routing Verfahrens ist eine getroffeneEntscheidung endgultig, unabhangig vom weiteren Verlauf.
Backtracking
Backtracking Verfahren bieten die Moglichkeit beim Auftreten definierterEreignisse die Ruckverfolgung des bisher zuruckgelegten Weges und dieAuswahl alternativer Routen.
23/53
Umwegloses vs. umwegbehaftetes Routing
Umwegloses Routing
Bei Einsatz eines umweglosen Routing Verfahrens wird mit jedem Schritt dieEntfernung zur Senke reduziert. Trifft die Nachricht auf eine Blockierung, sokann sie nur entlang solcher Verbindungsleitungen weiter vermittelt werden,die zu einem Weg gleicher Lange fuhren.
Umwegbehaftetes Routing
Bei Verwendung eines umwegbehafteten Routing Verfahrens wird dieBeschrankung auf minimale Weglange aufgehoben und ein Umweg einerBlockierung vorgezogen. Somit kann die Weglange uber dem Mindestabstandvon Quelle und Senke liegen.
24/53
Vollstandige vs. eingeschrankte Adaption
Vollstandige Adaption
Die Adaption definiert Klassen von Wegen durch das Verbindungsnetzwerk,welche vom Suchalgorithmus genutzt werden konnen. Bei einer vollstandigenadaptiven Wegsuche kann der Algorithmus beliebige Wege aus dieser Klassenutzen.
Eingeschrankte Adaption
Die eingeschrankte Adaption erlaubt lediglich die Nutzung einer Untermengealler verfugbaren Wege durch das Verbindungsnetzwerk.
25/53
Agenda
4 Deterministisches RoutingXY-Routing (Dimension Order Routing)e-Cube-Routing (Verallgemeinerung von XY-Routing)Up*/Down*MinHop RoutingLayered Shortest Path RoutingSingle-Source-Shortest-Path RoutingDeadlockfreier SSSP Routingalgorithmus
26/53
XY-Routing (Dimension Order Routing)
Horizontale Vermittlung der Nachrichten bis zum Erreichen der Zielspalte
Vertikale Transfers im Anschluss bis die Zielreihe erreicht ist
Impliziert Deadlock-Freiheit
27/53
e-Cube-Routing (Verallgemeinerung von XY-Routing)
Entwurf des e-Cube-Algorithmus fur binare n-Cube-NetzeNachricht durchlauft die Dimensionen eines Netzes stets in der gleichenReihenfolgeKeine zyklischen Abhangigkeiten
28/53
Up*/Down*
Erstellung eines Spannbaums mittels Breitensuche
Klassifizierung aller Ports mit ”up” oder ”down”
Up*/Down* Routing: Eine zulassige Route muss keinen oder mehr ”Up”Ports durchlaufen, gefolgt von keinem oder mehr ”Down” Ports
Zyklische Abhangigkeiten sind ausgeschlossen da ein Paket nach derVerwendung von ”down” Ports keinen ”Up” Port mehr durchlaufen darf
29/53
MinHop Routing
Routing entlang der kurzesten Pfade im Netzwerk
Basierend auf Dijkstra Algorithmus
Keine globale Lastbalancierung
Deadlocks sind nicht ausgeschlossen
30/53
Layered Shortest Path Routing I
Algorithmus 1 LASH Routingalgorithmus [Skeie02]
MinHop(. . .)for all < Source,Destination > do
Suche einen virtuellen Layer dem der Pfad hinzugefugt werden kann ohnedas dadurch ein Zyklus entstehtFalls ein solcher Layer nicht gefunden werden kann, erstelle einen Neuenif currLayer == maxLayer then
BREAKend if
end for
31/53
Layered Shortest Path Routing II
Routing entlang der kurzesten Pfade im Netzwerk
Basierend auf Dijkstra Algorithmus
Keine globale Lastbalancierung
Deadlockfrei, insofern ausreichend virtuelle Kanale vorhanden sind
32/53
Single-Source-Shortest-Path Routing I
Algorithmus 2 SSSP Routingalgorithmus [HSL09]
/* N-zu-N, Multigraph Dijkstra Algorithmus */for all Port ∈ Subnetz do
Dijkstra(. . .) fur den Port als QuelleAktualisierung alle Linear Forwarding TabellenVerandere die Kantengewichte
end for
33/53
Single-Source-Shortest-Path Routing II
Routing entlang der kurzesten Pfade im Netzwerk
Basierend auf dem Dijkstra Algorithmus
Update der Kantengewichtungen nach jeder Iteration fuhrt zur globalenLastbalancierung
Deadlocks sind nicht ausgeschlossen
34/53
Deadlockfreier SSSP Routingalgorithmus I
Algorithmus 3 DFSSSP Routingalgorithmus
/* Phase 1: Identifikation der Komponenten */Scan(. . .)/* Phase 2: Routenberechnung */SSSP(. . .)/* Phase 3: Verteilung auf virtuelle Schichten */DeadlocksBeseitigen(. . .)/* Phase 4: Balancierung der virtuellen Schichten */Balancierung(. . .)
35/53
Deadlockfreier SSSP Routingalgorithmus II
Algorithmus 4 Entferne Deadlocks aus Kanalabhangigkeitsgraph (Phase 3)
/* Initialisierung der Schicht 1 */for all Portpaare (Quelle, Ziel) do
Aktualisiere CDG[1] mit Route von Quelle zum Zielend for/* Suche Zyklen in den Kanalabhangigkeitsgraphen */for i = 1, . . . ,max − 1 do
repeatFuhre Zyklensuche in CDG[i ] ausIdentifiziere ”schwachste” Kante des ZyklusVerschiebe Portpaare/Routen der Kante in CDG[i + 1]
until kein Zyklus gefunden in CDG[i ]end forFuhre Zyklensuche in CDG[max ] aus
36/53
Agenda
5 Adaptives RoutingIdle-AlgorithmusDouble-Y-Channel-RoutingDuato’s MethodikTurn-ModellA1-AlgorithmusBacktracking
Vollstandige SucheEingeschrankte Suche
37/53
Idle-Algorithmus
Grundlage des Idle-Algorithmus [GrR89] bildet ein deterministischesRouting-Verfahren
Tritt eine Blockierung auf, wird der nachste Ausgang gewahlt, welcherdie Entfernung zur Senke reduziert
Existiert dieser nicht, wird die bestehende Verbindung blockiert oder derVermittlungsversuch beendet
Umsetzung bspw. im Mad-Postman-Routing [Jel93]
38/53
Double-Y-Channel-Routing
Double-Y-Channel-Routing [NiM93] beruht auf der Zuordnung derverfugbaren Kanale zu mehreren unabhangigen Subnetzen
Auswahl des entsprechenden Subnetzes fur jede Verbindung
Erfordert mehrere physische oder virtuelle Kanale zwischen den Knoten
39/53
Duato’s Methodik
Erweiterung des Kanalabhangigkeitsgraphen 1991 durch Duato [Dua91a]
Existiert eine Untermenge R1 aller Routing-Kanale, deren Abhangigkeits-graph keine Schleifen aufweist, so ist der Algorithmus frei von Deadlocks
40/53
Turn-Modell
Ziel des Turn-Modells [GlN92]: Zulassung von Umwegen, beigleichzeitigem Ausschluss von Deadlocks
Vorgehensweise:
Aufbrechen von Zyklen durch Unterbindung eines Wechsels in einedefinierte RichtungErfordert das zunachst alle Transfers in die untersagte Richtungausgefuhrt werden
41/53
A1-Algorithmus
Ziel des A1-Algorithmus [ChS90]: Wegfindung innerhalb einesCube-Netzes, insofern einer existiert
Mitfuhrung zusatzlicher Informationen notwendig:
Verbleibende Weglange kNoch zu durchlaufende Dimensionen dUmwegvektor u
Priorisierung der Wege minimaler Lange, andernfalls Markierung desUmwegs und der blockierten Verbindung im Umwegvektor u
42/53
Backtracking
Ruckverfolgung des bereits zuruckgelegten Wegs im Falle einerBlockierung
Mitfuhrung, Speicherung und Auswertung von Informationen uberbereits untersuchte Verbindungen
Frei von Dead- und Livelocks
43/53
Vollstandige Suche
Vollstandige umwegbehaftete Suche
Das Verfahren der vollstandigen umwegbehafteten Suche bezieht alle Wegezwischen Quelle und Senke in die Suche mit ein und garantiert damit, dass einWeg gefunden wird, insofern einer existiert.
Vollstandige profitable Suche
Bei dem Verfahren der vollstandigen profitablen Suche werden alle Wegezwischen Quelle und Senke berucksichtigt, welche uber die minimale Weglangeverfugen.
44/53
Eingeschrankte Suche
k-FamilieBei Protokollen der k-Familie wird die Wegsuche durch die Unterteilung inzwei Phasen beschleunigt. Ist die Nachricht weiter als k Schritte von der Quelleentfernt, wird eine heuristische Suche eingesetzt. Erst im Anschluss wird dievollstandige Suche verwendet.
Two-Phase Misroute Backtracking
Bei dem Two-Phase Misroute Backtracking erfolgt die Berechnung desWegs in zwei Phasen. Ist der Abstand zur Quelle großer als eine definierteKonstante wird eine vollstandige profitable Suche, andernfalls eine vollstandigeumwegbehaftete Suche durchgefuhrt.
45/53
Agenda
6 Literaturverzeichnis
46/53
Literaturverzeichnis I
[Dom11] J. Domke, T. Hoefler, W. E. NagelDeadlock-Free Oblivious Routing for Arbitrary Topologies, May. 2011.Proceedings of the 25th IEEE International Parallel & DistributedProcessing Symposium (IPDPS), S. 613–624
[Skeie02] Tor Skeie and Olav Lysne and Ingebjorg TheissLayered Shortest Path (LASH) Routing in Irregular System AreaNetworks, 2002.Proceedings of Communication Architecture for Clusters, , IEEEComputer Society
[HSL09] T. Hoefler, T. Schneider, A. LumsdaineOptimized Routing for Large-Scale InfiniBand Networks, 2009.17th Annual IEEE Symposium on High Performance Interconnects
47/53
Literaturverzeichnis II
[SHL09] T. Schneider, T. Hoefler, A. LumsdaineORCS: An Oblivious Routing Congestion Simulator, Feb. 2009.Techreport 675, Indiana University Computer Science
[HML07] T. Hoefler, T. Mehlan, A. Lumsdaine, W. RehmNetgauge: A Network Performance Measurement Framework, Sep. 2007.Proceedings of High Performance Computing and Communications,HPCC’07, Springer Verlag, S. 659-671
[Tan07] A. TanenbaumModern Operating Systems, Band 3, 2007.
48/53
Literaturverzeichnis III
[JBK04] G. Juckeland, S. Borner, M. Kluge, S. Kolling, W.E. Nagel, S.Pfluger, H. Roding, S. Seidl, T. William, R. WlochBenchIT – Performance measurement and comparison for scientificapplications, 2004.Parallel Computing - Software Technology, Algorithms, Architectures andApplications, S. 501–508
[SLT02] T. Skeie, O. Lysne, I. TheissLayered Shortest Path (LASH) Routing in Irregular System AreaNetworks, 2002.IPDPS ’02: Proceedings of the 16th International Parallel andDistributed Processing Symposium, S. 194-
[BHS95] D. Bailey, T. Harris, W. Saphir, R. Wijngaart, A. Woo, M.YarrowThe NAS Parallel Benchmarks 2.0, 1995.Techreport NAS-95-020, NASA Ames Research Center
49/53
Literaturverzeichnis IV
[NiM93] L. M. Ni, P. K. McKinleyA survey of wormhole routing techniques in direct networks, Feb 1993.IEEE Computer, Band 26, Nr. 2, S. 62-76
[Jel93] C. R. Jesshope, C. IzuThe MP1 Network Chip and its Application to Parallel Computers, 1993.The Computer Journal, Band 36, Nr. 8
[GlN92] C. J. Glas, L. M. NiThe turn model for adaptive routing, May 1992.19th International Symposium on Computer Architecture, S. 278-287
50/53
Literaturverzeichnis V
[SBB91] M. Schroeder, A. Birrell, M. Burrows, H. Murray, R. Needham,T. Rodeheffer, E. Satterthwaite, C. ThackerAutonet: A High-Speed, Self-Configuring Local Area Network UsingPoint-to-Point Links, 1991.IEEE Journal on Selected Areas in Communications, Vol. 9, Nr. 8, S.1318-1335
[Dua91a] J. DuatoDeadlock-free adaptive routing algorithms for multicomputers:Evaluation of a new algorithm, 1991.Third IEEE Symposium on Parallel and Distributed Processing, S.840-847
[Dua91b] J. DuatoOn the design of deadlock-free adaptive routing algorithms formulticomputers: Theoretical aspects, Apr 1991Distributed Memory Computing, Springer Verlag, S. 234-243
51/53
Literaturverzeichnis VI
[ChS90] M.-S. Chen, G. K. ShinAdaptive fault-tolerant routing in hypercube multicomputers, Dec 1990.IEEE Transactions on Computers, Band C-39, Nr. 12, S. 1406-1415
[Tou80] S. TouegDeadlock- and livelock-free packet switching networks, 1980.STOC ’80: Proceedings of the twelfth annual ACM symposium onTheory of computing, S. 94-99
[GrR89] D. Grunwald, D. ReedAnalysis of Backtracking routing in binary hypercube computers, 1989.Technical Report UIUC-DCS-R-89-1486, University of Illinois
[DaS87] W. J. Dally, C. L. SeitzDeadlock-free message routing in multi-processor interconnectionnetworks, May 1987.IEEE Transactions on Computers, Band C-36, Nr. 5, S. 547-553
52/53
Literaturverzeichnis VII
[CoE71] E. G. Coffman, M. J. Elphick, A. ShoshaniSystem deadlocks, 1971.ACM Computer Surveys, Band 3, S. 67-78
53/53