Center for Information Services and High Performance Computing (ZIH)
Theorie und Einsatz von Verbindungseinrichtungen inparallelen Rechnersystemen
Statische Verbindungsnetzwerke
04. Mai 2012
Andy Georgi
INF 1046Nothnitzer Straße 4601187 Dresden
0351 - 463 38783
m
Foliensatz
Verfugbarkeit der Folien
Vorlesungswebseite:http://tu-dresden.de/die_tu_dresden/zentrale_einrichtungen/
zih/lehre/ss2012/tevpr
2/64
Agenda I
1 Einfuhrung
2 Vollstandige Vermaschung
3 Stern
4 Ring
5 Gitter
6 Baum
7 Cube
3/64
Agenda II
8 Topologien aktueller Systeme
9 Literaturverzeichnis
4/64
Agenda
1 Einfuhrung
5/64
Einfuhrung I
Kommunikation zwischen Knoten uber feste Verbindungsleitungen wie inKapitel 2 beschrieben
Kosten beschranken sich auf Hardware-Unterstutzung in den Knoten undLeitungen
Beschreibung der topologischen Verbindungsstrukturen mittelsVerbindungsfunktionen
6/64
Einfuhrung II
Verbindungsfunktion
Verfugt ein Knoten A uber eine Verbindungsfunktion f (A), so werden beiAusfuhrung dieser Funktion Daten vom Knoten A zu Knoten f (A) = Btransferiert.
7/64
Agenda
2 Vollstandige Vermaschung
8/64
Vollstandige Vermaschung
Dedizierte Verbindungen von jedem Knoten zu jedem anderen Knoten
Interne Konflikte ausgeschlossen
Beschrankung der maximal erzielbaren Kommunikationsleistung erfolgtausschließlich durch die technische Realisierung
9/64
Agenda
3 Stern
10/64
Stern
Master-Slave-Architektur
Verbindungsaufbau erfolgt uber zentralen Knoten (Master)
Effizient bei Multicast-Operationen oder Prozesssynchronisation
11/64
Agenda
4 RingKlassische Ring-TopologieChordaler RingToken-RingRegister-Insertion-RingScalable Coherent Interface
12/64
Klassische Ring-Topologie
Verbindungsfunktionen in einem bidirektionalen Ring:
ring+ = (P + 1) mod Nring− = (P − 1) mod N
Ein unidirektionaler Ring implementiert nur eine der beidenVerbindungsfunktionen
Keine Zugriffsbeschrankungen
13/64
Chordaler Ring
Ziel: Reduzierung des Durchmessers und der mittleren Weglange
Umsetzung: Einfugen zusatzlicher Verbindungen, sog. Chords
Die Chord-Lange C bezeichnet den Abstand der verbundenen Knoten
Ein Chordaler Ring nach Arden und Lee [ArL81] enthalt stets einegerade Anzahl von Knoten und vier Verbindungsfunktionen:
ring+1 = (P + 1) mod Nring−1 = (P − 1) mod Nring+C = (P + C ) mod N, wenn P ungeradering−C = (P − C ) mod N, wenn P gerade
14/64
Token-Ring
Zugangsregelung mit Hilfe von Token
Ablauf im IEEE 802.5 Token-Ring-Protokoll standardisiert:
1 Sender wartet auf Free-Token2 Umwandlung in Busy-Token, welches zusammen mit den zu sendenden
Daten an den Ring ubergeben wird3 Weiterleitung der Nachricht entsprechend der Verbindungsfunktion4 Entfernung der Nachricht vom Netz durch den Quellknoten5 Freigabe des Tokens nach der vollstandigen Ubertragung der Nachricht
15/64
Register-Insertion-Ring
EP AP
Schieberegister
PE 0
EP AP
Schieberegister
PE 1
Abbildung: Register-Insertion-Ring mit zwei Knoten
16/64
Scalable Coherent Interface
Prozessor
Dekoder RingpufferVorgänger
Nachfolger
Empfangs-puffer
Sende-puffer
PE n
Abbildung: Blockschaltbild eines SCI-Knotens
17/64
Agenda
5 GitterMesh-NetzTorusIlliac-Netz
18/64
Zweidimensionale Gitter
Verteilung der Knoten auf MR Reihen und MS Spalten
Unterscheidung zwischen offenem und geschlossenem Gitter
Befindet sich der betrachtete Knoten in Reihe k auf Spalte j , so ergibtsich sein Index I aus
IH = j + MS ∗ k bei horizontaler, bzw.IV = k + MR ∗ j bei vertikaler Zahlrichtung
19/64
Mesh-Netz
Offenes Gitter mit horizontalen und vertikalen Verbindungen der direktenNachbarn
Implementiert vier Verbindungsfunktionen:
meshright (IH) = (j + 1) + MS ∗ kmeshleft (IH) = (j − 1) + MS ∗ kmeshdown (IH) = j + MS ∗ (k + 1)meshup (IH) = j + MS ∗ (k − 1)
20/64
Torus
Geschlossenes Gitter mit horizontalen und vertikalen Verbindungenzwischen Randknoten einer Reihe bzw. Spalte
Verbindungsfunktionen:
torusright (IH) = ((j + 1) mod MS) + MS ∗ ktorusleft (IH) = ((j − 1) mod MS) + MS ∗ ktorusdown (IH) = j + MS ∗ ((k + 1) mod MR)torusup (IH) = j + MS ∗ ((k − 1) mod MR)
21/64
Illiac-Netz I
Benannt nach dem Rechner Illiac-IV [BoD72], welcher diese Topologieimplementierte
Geschlossenes Gitter mit folgenden Eigenschaften:
Vertikale und horizontale Verbindungen zu den direkten NachbarnVerbindung der Randknoten einer SpalteVerbindung des Endknotens einer Reihe mit dem Anfangsknoten dernachfolgenden Reihe
22/64
Illiac-Netz II
Verbindungsfunktionen:
illiacright (IH) = ((j + 1) + MS ∗ k) mod Nilliacleft (IH) = ((j − 1) + MS ∗ k) mod Nilliacdown (IH) = (j + MS ∗ (k + 1)) mod Nilliacup (IH) = (j + MS ∗ (k − 1)) mod N
23/64
Gitter hoheren Grades
0 1 2
3 4 5
6 7 8 9
10 11 12 13
14 15 16
17 18
Node i connected to i ± 1, i ± 7, and i ± 8 (mod 19).Abbildung: 8-Nachste-Nachbarn-Netz und Hexagonales Gitter
24/64
Mehrdimensionale Gitter I
Circuit Board
Backplane
Abbildung: 3D und 2.5D Gitterstrukturen
25/64
Mehrdimensionale Gitter II
0
1
2
3
4
5
6
16
17
8
10 13
X
Y
Z
Abbildung: Indizierung mehrdimensionaler Gitterstrukturen
26/64
Mehrdimensionale Gitter III
PC board
Backplane
Memory
CPU
Bus
Connector
(b) 3D packaging of the future (a) 2D or 2.5D packaging now common
Stacked layers glued together
Interlayer connections deposited on the
outside of the stack Die
Abbildung: Physikalische Realisierung mehrdimensionaler Gitterstrukturen
27/64
Agenda
6 BaumBinarbaumek-fache BaumeRing-erweiterte BaumeHypertreeFat-Tree
28/64
Baumstrukturen
DefinitionAus graphentheoretischer Sicht handelt es sich bei einem Baum um einenungerichteten zusammenhangenden azyklischen Graphen. Dabei ist dieserdurch eine Wurzel gekennzeichnet, von der keine, eine oder mehrere Kantenausgehen. Die Kanten verbinden die Wurzel mit ihren Kindsknoten, wobei essich entweder um Blatter - d.h. Knoten ohne weiterfuhrende Kanten - oderrekursiv um Wurzeln weiterer Baume handelt. Die Tiefe T eines Baumesentspricht der maximalen Anzahl von Kanten, welche durchlaufen werdenmussen, um von der Wurzel zu einem Blatt zu gelangen.
29/64
Binarbaume I
DefinitionDie Wurzel eines Binarbaumes besitzt stets einen rechten und einen linkenKindsknoten. Dabei handelt es sich entweder um ein Blatt oder die Wurzeleines weiteren Teilbaumes, welcher wiederum einem Binarbaum entspricht. Istzudem die Entfernung von der Wurzel zu allen Blattern identisch, so sprichtman von einem vollstandigen Binarbaum.
30/64
Binarbaume II
Ein Knoten mit dem Index I kann in einem vollstandigen Binarbaumfolgende Verbindungsfunktionen ausfuhren:
childright (I ) = 2I ; wenn I kein Blattchildleft (I ) = 2I + 1 ; wenn I kein Blattparent (I ) = bI/2c ; wenn I nicht der Wurzel entspricht
31/64
k-fache Baume
Ziel: Reduzierung des Durchmessers bei gleichbleibender Knotenzahl
Losung: Reduzierung der Tiefe
Umsetzung: Erhohung der erlaubten Anzahl von Kindern pro Knoten
32/64
Ring-erweiterte Baume
Erweiterung des Baumes um horizontale Verbindungsleitungen
Verbindung der Blattebene mit Hilfe einer Ring-Topologie ergibtvollstandig verknupften Binarbaum [HoZ81]
Durch Anwendung der Ring-Erweiterung auf alle Ebenen entsteht einBinarbaum mit vollstandigen Ringverbindungen [HoZ81]
33/64
Hypertree I
Hamming-Distanz
Als Hamming-Distanz H wird die minimale paarweise Stellendistanz einesCodes definiert [Ham86]. Die Stellendistanz d(x,y) bezeichnet dabei die Anzahlder Stellen, in denen sich zwei gleich lange Worter x und y unterscheiden. FurWorter unterschiedlicher Lange ist die Stellendistanz hingegen nicht definiert.
34/64
Hypertree II
Grundlage bildet ein vollstandiger Binarbaum
Verbindung der Knoten A und B einer Ebene, wenn H(A,B) = 1
Unterscheidung zwischen Hypertree I und Hypertree II [Goo81]
35/64
Beispiel
000001
000010
000100
001000
010000
100000 100001
010001
100010 100011
001001
010010
100100 100101
010011
100110 100111
000101
001010
010100
101000 101001
010101
101010 101011
001011
010110
101100 101101
010111
101110 101111
000011
000110
001100
011000
110000 110001
011001
110010 110011
001101
011010
110100 110101
011011
110110 110111
000111
001110
011100
111000 111001
011101
111010 111011
001111
011110
111100 111101
011111
111110 111111
Abbildung: Beispiel: Hypertree mit 63 Knoten veteilt auf sechs Ebenen
36/64
Fat-Tree
Erhohung der verfugbaren Datenrate in Richtung der Wurzel [Lei85]
Beibehaltung des Routingalgorithmus und wesentlicher Eigenschaftender ursprunglichen Baumstruktur
37/64
Agenda
7 CubeKlassisches Cube-NetzTwisted Cube-NetzCrossed Cube-NetzEnhanced HypercubeFolded HypercubeIncomplete Hypercubes
38/64
Klassisches Cube-Netz I
DefinitionDas klassische Cube-Netz besteht aus N = 2n Knoten, wobei n auchals Dimension bezeichnet wird. Zwei Knoten A und B sind jeweils dannmiteinander verbunden, wenn H(A,B) = 1.
39/64
Klassisches Cube-Netz II
Per Definition verfugt in einem klassischen Cube-Netz jeder Knotenuber n Ein- und Ausgange
Entsprechend ist auch die Implementierung von n Verbindungsfunktionennotwendig:
cubek(bn−1bn−2...bk ...b1b0) = bn−1bn−2...bk ...b1b0, mit 0 ≤ k < n
40/64
Twisted Cube-Netz
Umstrukturierung vorhandener Verbindungsleitungen zur Reduzierungdes Durchmessers
Vorgehensweise [EsN91]:
1 Auswahl eines Zyklus uber vier Knoten a, b, c, d ∈ V in einem klassischenCube-Netz
2 Bestimmung zweier Kanten {a, b}, {c, d} ∈ E aus diesem Zyklus, welchenicht uber einen Knoten miteinander verbunden sind
3 Ersetzung der gewahlten Kanten: ϕ({a, b}, {c, d}) = {a, c}, {b, d}
41/64
Crossed Cube-Netz I
Definition
Als CQn wird ein n-dimensionales Crossed Cube-Netz [Efe92] bezeichnet. CQ1
besteht aus zwei miteinander verbundenen Knoten. Ist n > 1 so wird CQn
aus den beiden Subnetzen CQ0n−1 und CQ1
n−1 gebildet, indem die Knotenu = 0un−2...u0 und v = 1vn−2...v0 mit u ∈ CQ0
n−1 und v ∈ CQ1n−1 genau
dann miteinander verbunden werden wenn gilt:
1 un−2 = vn−2, falls n gerade ist, und
2 u2i+1u2i ∼ v2i+1v2i , fur alle i mit 0 ≤ i < b(n − 1)/2c
42/64
Crossed Cube-Netz II
Paarweise VerwandtschaftZwei binare Sequenzen x = x1x0 und y = y1y0 werden als paarweise verwandtbezeichnet, wenn (x , y) ∈ {(00, 00), (10, 10), (01, 11), (11, 01)}. Sind x und ypaarweise miteinander verwandt so schreibt man x ∼ y , andernfalls x � y .
43/64
Enhanced Hypercube
Definition
In einem Enhanced Hypercube [TzW91] der Ordnung ω, mit 0 ≤ ω < n − 1,werden gegenuber der klassischen Cube-Topologie Verbindungsleitungenzwischen allen Knotenpaaren
{(xn−1 ... xn−ω xn−ω−1 ... xi ... x0), (xn−1 ... xn−ω xn−ω−1 ... xi ... x0)}
hinzugefugt.
44/64
Folded Hypercube
Spezialfall des Enhanced Hypercubes der Ordnung ω = 0 [ElL91]
Erweiterung um N/2 Verbindungsleitungen zwischen Knoten mit dermaximalen Hamming-Distanz
Reduzierung des Durchmessers auf dn/2e
45/64
Incomplete Hypercubes
Erweiterung der bisher vorgestellten Cube-Topologien um eineDimension erfordert eine Verdopplung der Knotenzahl
Incomplete Hypercubes lassen eine beliebige Knotenanzahl zu
Eingrenzung auf Netze, welche aus zwei vollstandigen Cube-Netzenunterschiedlicher Große 2n und 2k bestehen [TzC92]
46/64
Agenda
8 Topologien aktueller SystemeSGI AltixK ComputerDragonfly
47/64
SGI Altix - Individual Rack Unit (IRU)
Abbildung: Aufbau einer einzelnen IRU [RV05]
48/64
SGI Altix - Single Rack
Abbildung: Verknupfung der IRUs innerhalb eines Racks [RV05]
49/64
SGI Altix - 128 Compute Blades
Abbildung: Verbindungsstruktur zwischen 128 Processor Blades [RV05]
50/64
SGI Altix - 256 Compute Blades
Abbildung: SHub2 Building Block fur 256 Processor Blades [RV05]
51/64
K Computer - Tofu Interconnect
Abbildung: Aufbau des 6D Torus des K Computers [MO10]
52/64
Dragonfly - Uberblick
Erhohung der Gradzahl aktiverNetzwerkkomponenten:
+ Reduzierung von Durchmesser undmittlerer Weglange
− Kabellangen nehmen zu
Minimierung der globalen Verbindungentrotz hoher Gradzahl durch:
Gruppierung mehrerer low-radix Routerzu einem virtuellen high-radix RouterVerwendung kurzer Kabel innerhalbeiner GruppeLange Kabel ausschließlich fur dieVerbindung verschiedener Gruppen
Abbildung: Dragonfly [SD07]
53/64
Dragonfly - Aufbau
Hierarchisches Netzwerk bestehend aus drei Ebenen:
RouterGruppenSysteme
Relevante Parameter:
a Anzahl der Router innerhalb einer Gruppep Anzahl der Knoten pro Routerh Anzahl der globalen Verbindungen pro Routerg Anzahl der Gruppen im System
54/64
Dragonfly - Router
Anbindung von p Knoten
a− 1 lokale Verbindungen zu anderen Routern der Gruppe
h globale Verbindungen zu anderen Gruppen
Abbildung: Dragonfly Blockdiagramm [JK09]
55/64
Dragonfly - Gruppe
Zusammenfassung von a Routern zu einer Gruppe
Verfugt uber a ∗ p lokale Verbindungen zu den Knoten der Gruppe unda ∗ h globalen Verbindungen zu anderen Gruppen
Gruppeninterne Router agieren als ein einzelner virtueller Router
Abbildung: Dragonfly Blockdiagramm [JK09]
56/64
Dragonfly - Beispiel Deimos I
Abbildung: Verbindungsnetzwerk Deimos (Original) [JD12]
57/64
Dragonfly - Beispiel Deimos II
Abbildung: Verbindungsnetzwerk Deimos (Dragonfly) [JD12]
58/64
Agenda
9 Literaturverzeichnis
59/64
Literaturverzeichnis I
[IE1596] David B. Gustavson, Qiang LiThe Scalable Coherent Interface (SCI), Santa Clara University 1996.http://userweb.cs.utexas.edu/users/dburger/teaching/
cs395t-s08/papers/9_sci.pdf
[ArL81] B. W. Arden, H. LeeAnalysis of chordal ring networks, Apr 1981.IEEE Transactions on Computers, Band C-30, Nr. 4, S. 291-295
[Dot84] K. W. DotyNew designs for dense processor interconnection networks, May 1984.IEEE Transactions on Computers, Band C-33, Nr. 5, S. 447-450
[BoD72] W. J. Bouknight, S. A. Denenberg, D.E. McIntyre, J. M.Rundall, A. H. Sameh, D.L. SlotnickThe Illiac IV system, Apr 1972.Proceedings of the IEEE, Band 60, Nr. 4, S. 369-388
60/64
Literaturverzeichnis II
[HoZ81] E. Horowitz, A. ZoratThe binary tree as an interconnection network: Applications tomultiprocessor system and VLSI, Apr 1981IEEE Transactions on Computers, Band C-30, Nr. 4, S. 247-253
[Ham86] R. W. HammingCoding and Information Theory, Jan 1986Prentice Hall, ISBN-13: 978-0131390720
[Goo81] J. R. Goodman, C. H. SequinHypertree – A multiprocessor interconnection topology, Apr 1981Computer Sciences Technical Report #427
[Lei85] C. E. LeisersonFat-Trees: Universal networks for hardware-efficient supercomputing, Oct1985IEEE Transactions on Computers, Band C-34, Nr. 10, S. 892-901
61/64
Literaturverzeichnis III
[EsN91] A.-H. Esfahanian, L. M. Ni, B. E. SaganThe twisted N-cube with application to multiprocessing, Jan 1991IEEE Transactions on Computers, Band C-40, Nr. 1, S. 88-93
[Efe92] K. EfeThe crossed cube architecture for parallel computation, Sep 1992IEEE Transactions on Parallel and Distributed Systems, Band 3, Nr. 5,S. 513-524
[TzW91] N.-F. Tzeng, S. WeiEnhanced Hypercubes, Mar 1991IEEE Transactions on Computers, Band C-40, Nr. 3, S. 284-294
[ElL91] A. El-Amawy, S. LatifiProperties and performance of folded hypercubes, Jan 1991IEEE Transactions on Parallel and Distributed Systems, Band 2, Nr. 1,S. 31-42
62/64
Literaturverzeichnis IV
[Kat88] H. P. KatseffIncomplete hypercubes, May 1988IEEE Transactions on Computers, Band C-37, Nr. 5, S. 604-608
[TzC92] N.-F. Tzeng, H.-L. ChenAn effective approach to the enhancement of incomplete hypercubecomputers, Feb 1992Journal of Parallel and Distributed Computing, Band 14, Nr. 2, S.163-174
[RV05] Reiner VogelsangSGI Altix Hardware Architecture, SGI GmbH, June 2005.http://wwwuser.gwdg.de/~parallel/parallelrechner/altix_
documentation/Altix_Hardware_revised_4.pdf
63/64
Literaturverzeichnis V
[MO10] Motoi OkudaApproach to Application Centric Petascale Computing, Fujitsu Ltd., Nov2010.http://www.fujitsu.com/downloads/TC/sc10/
when-high-performance-computing-meets-energy-efficiency.
[SD07] Science DailySolving A Dragonfly Flight Mystery, Sep. 24, 2007.http://www.sciencedaily.com
[JK09] John Kim, William J. Dally, Steve Scott, Dennis AbtsCost-Efficient Dragonfly Topology for Large-Scale Systems, 2009IEEE Micro, Band 29, Nr. 1, S. 33-40http://doi.ieeecomputersociety.org/10.1109/MM.2009.5
[JD12] Jens Domke, 2012
64/64