elta mp 212

Transcrição

elta mp 212

K Netzwerke
Vorlesung Rechnerarchitektur im SS 2010
Inhalt von K




1. Allgemeines




Leistungsmerkmale
Begriffe
Dynamische Netzwerke
Routing
2. Netzstrukturen





Merkmale
Ringstruktur
MC: Mesh Connected (Gitter)
Illiac-Netzwerk
Baumstruktur

Fat Tree
CC: Cube Connected (Hypercube)
CCC
Barrel-Shifter
Dynamische Verbindungsnetze



Crossbar-Switch
Mehrfachbussysteme
Permutationsnetze







Perfect-Shuffle
Omega-Netz
Bidelta-Netze
Banyan
Butterfly
CLOS-Netz
Verilog-Beispiel: Datenaustausch auf
einem Ringnetz
3. Zusammenfassung
RA – SS 10, R. Hoffmann, Rechnerarchitektur, TU Darmstadt
R. Hoffmann, FB Informatik, TU-Darmstadt
E-1
 max. Anzahl der gleichzeitigen
Verbindungen
 Art der Verbindung,
Funktionalität
 Simplex, Duplex
 Broadcasting/Multicasting 1:n,
Vereinigung n:1
 Leitungsvermittlung (circuit
switching)
 Paketvermittlung (packet
switching),
 Datenübertragungsrate
 auch "Übertragungsbandbreite"
(MBit/s, MByte/s)
 konstant oder variabel
 abhängig von der Anzahl der
Verbindungen, evtl. Blockierung
 abhängig von der Anzahl der
angeschlossenen Stationen
 abhängig von der Ausdehnung
des Netzes
 Latenzzeit
 Zeit bis zum Empfangen des
ersten Zeichens
E-3
RA – SS 10 , R. Hoffmann, Rechnerarchitektur, TU Darmstadt
1. Allgemeines: Leistungsmerkmale
 Zuverlässigkeit,
 Technische Zuverlässigkeit,
Ausfallsicherheit
 Fehlertoleranz
 Redundante Wege
 Flexibilität
 für viele verschiedene
Algorithmen/Anwendungen
geeignet
 Erweiterbarkeit
 Möglichkeit, weitere Knoten und
Kanten dem Netz hinzufügen
 Skalierbarkeit
 (Voraussetzung:
Erweiterbarkeit): Durch die
Erhöhung der Anzahl der
Knoten/Links bleiben die
wesentlichen Eigenschaften (wie
Latenzzeit oder Verkehrsdichte)
konstant oder steigen nur
höchstens linear.
 Aufwand, Kosten, Komplexität
 Anzahl der Inputs/Outputs,
Verbindungsleitungen, Puffer,
Schalter, Steuerung der Schalter
E-4
Weitere Leistungsmerkmale
 Netztopologie, auch
Netzstruktur,
Verbindungsstruktur wie z. B.
 Linie (1D Feld), nicht symm.
 Ring, symmetrisch
 Stern
 Masche, teilweise oder
vollständig
 Funknetz
 Symmetrische Topologie
 Bei einer symmetrischen Topologie
sieht das Netz von jedem
Betrachtungspunkt (Knoten/Links)
gleich aus, d.h. es existieren für
Knoten und/oder Kanten sog.
Automorphismen.
 Einfach gesprochen heißt dies, dass
sich Knoten und/oder Links in einem
symmetrischen Netz gleich
verhalten, egal von welchem Knoten
oder welchem Link man es
betrachtet.
 Dies vereinfacht die Hardware, das
Routing, die Programmierung, und
die Lastverteilung, da keine
Spezialfälle zu behandeln sind.
E-5
RA – SS 10 , R. Hoffmann, Rechnerarchitektur, TU Darmstadt
Netztopologie
 Die logische Topologie kann von der physischen abweichen.
 Ethernet
 physisch: Stern oder Bus
 logisch: Bus
 Token-Ring
 physisch: Ring oder Stern
 logisch: Ring
 USB
 physisch: Baum
 logisch: Bus
E-6
Physische und Logische Topologie
 Das Herstellen von Verbindungen
 insbesondere die Steuerung zur Wahl der Wege einer
Verbindung (Routing)
 Routingalgorithmus legt den Weg (Pfad) fest, Ziel: möglichst kurz
 dezentral: selbständig durch die Teilnehmerstationen,
 durch eine zentrale Verbindungsstation
 durch mehrere verteilte Verbindungsstationen
E-7
Vermittlung
 Weg (Link)
 Fest installierter
Kommunikationskanal zwischen
zwei Knoten
(Kante im Graphen)
 Verbindung (auch Pfad, Path)
 die benutzten Wege vom Sender
zum Empfänger
 Kanal
 die Kommunikationsmöglichkeit
zwischen zwei Knoten
 ein Kanal kann über alternative
Pfade laufen
E-8
 Multicasting/Broadcasting
 Die Daten werden vom Sender
gleichzeitig an mehrere/alle
Empfänger geschickt.
 Datenvereinigung
 Mehrere Sender schicken parallel
Nachrichten an einen Empfänger.
Die Daten überlagern sich.
Ergebnis kann sinnvoll sein
(Maximum, Summe)
 Statische Verbindungen
 Fest vorhandene (permanente)
ungesteuerte Wege, die von den
Knoten bei Bedarf benutzt werden.
Weitere Begriffe
 Die gewünschten Verbindungen
werden auf Anforderung
dynamisch aufgebaut. Eine
Steuerung des Netzwerks ist
erforderlich.
 Wegewahl durch RoutingAlgorithmus
 Das Routing sollte einfach sein,
um es in den
Verbindungsknoten durch eine
einfache Hardware
implementieren zu können.
 nicht-blockierend
 beliebige Verbindungen können
inkrementell (dynamisch) aufgebaut
werden
 universell: eine beliebige
Permutation ist (re)arrangierbar
 blockierend
 bestehende Verbindungen können
weitere verhindern
 ggf. kann man durch Rearrangieren
(Umordnung bestehender
Verbindungen) noch weitere
hinzufügen
E-9
Dynamische Verbindungstechnik
auch Leitungsvermittlung,
Durchschaltvermittlung
 fest geschaltete Verbindungen
für die gesamte Dauer der
Übertragung mit kurzen
Latenzzeiten
 Ablauf
1. Senden der
Adressierungsdaten.
2. Verbindungsaufbau
3. Übertragung der Nachrichten
(Während der Übertragung kein
weiterer Vermittlungsaufwand)
4. Verbindungsabbau nach der
Übertragung
 Oft gesteuert durch zentrale
Vermittlungseinrichtung
 Vorteil
 nach der Schaltung schnelle
Verbindung
 Nachteil
 Zeitaufwand zum Aufbauen
und Abbauen der Verbindung
 Verbindung kann nach der
Belegung nicht anderweitig
genutzt werden
E-10
Eine Vermittlungstechnik: Circuit Switching
Eine andere Vermittlungstechnik: Paketvermitlung
 Vorteile
 Gute Ausnutzung der
Netzressourcen
 Alternative Wege können
benutzt werden
 Kein expliziter Schritt zum
Aufbauen der Verbindung
notwendig
 Nachteile
 Nachrichten müssen in Pakete
aufgeteilt und wieder
zusammengesetzt werden
 Aufwand: Puffer in den Knoten,
Routing
 Staus und evtl. auch Deadlocks
sind möglich
 Latenzzeiten sind variabel (abh.
von Organisation, Route,
Belastung)
 Eine Nachricht besteht aus
Datenpaketen.
 Eine Nachricht wird über eine
logische Verbindung (Kanal)
vom Sender zum Empfänger
übertragen
 Datenpakete wird dem Netz
übergeben und können über
verschiedene physikalische
Verbindungen transportiert
werden.
 Die Links zwischen den
Knoten werden dynamisch für
Pakete von verschiedenen
Kanälen benutzt
E-11
Paketvermittlung: Pakete, Phits
E-12
Paket
D
D
D
D
D
Paket
D
Paket
Paket
D
D
S
R
Phit
Routing Information
Datenphits



Paket
Sequenzangabe
Nachricht wird in Pakete zerlegt
Paket wird in Einheiten (Phits) zerlegt
Phit
 physical transfer unit
 (Flit = flow control unit, kann mehrere Phits umfassen)

Beispiel High Performance Switch IBM SP1 / SP2: Phit= 8 Bit,
Paket ≤ 255 Phits
Nachricht
 Pakete
 können auf verschiedenen
Wegen übertragen werden
 können verloren gehen oder in
veränderter Reihenfolge
ankommen.
 werden beim Empfänger wieder
zusammengesetzt.
 Paketkopf enthält
Adressierungsinformation
 Zwischenpufferung der
Teilpakete (Blöcke, Phits) erfolgt
in den Verbindungsknoten.
 Puffer in den Verbindungsknoten
dürfen nicht überlaufen: wird
verhindert durch Flow-Control
 durch spezielle Signale:
ack, strobe
 oder FlussSteuerungspaket
http://ds.e-technik.uni-dortmund.de/new/CEI/resource/prs/PRS_Slides_2004.ppt
E-13
Paketvermittlung: Übertragung
1. Source-based (quell-basiert)



Alle Wege zu der Verbindung
werden vom Sender (Source)
festgelegt
Das Paket wird mit allen
Abzweiginformationen
(Ausgangsnummer) versehen,
um vom Sender zum
Empfänger zu kommen.
2. Destination-based (zielbasiert)

3. Tabellenbasiert

Eine verwendete
Ausgangsnummer wird an den
nächsten Knoten nicht mehr
weiter geschickt.
Das Paket enthält eine
systemweit eindeutige
Empfängeradresse, die von den
Verbindungsknoten zum Routing
benutzt wird.

Die Route ist für alle
Zieladressen vorausberechnet
Verbindungsknoten liest aus
Tabelle den zu verwendenden
Ausgang
E-14
Paketvermittlung: Routing, Adreßdecodierung
 Deterministisches Routing
 Pakete benutzen immer die
gleichen Wege für eine
Verbindung
 einfach, aber höhere
Blockierungswahrscheinlichkeit
geringere Fehlertoleranz
 Adaptives Routing
 alternative Wege können
benutzt werden. Blockierte
Wege oder ausgefallene
Knoten/Wege können
umgangen werden
E-15
Routing
Pfad
Paketkopf
Daten (bel. Länge)
CRC, Endemark
 Pfad wird vom Sender vorbestimmt und von den
durchlaufenen Vermitttlungsstufen auf dem Weg schrittweise
entfernt (Deterministisches Source Routing).
 Paketkopf ermöglicht unterschiedliche Protokolle
(Administrationsdaten, Ack-Pakete, Datenpakete,
Adressierung des Empfangsprozesses, Absenderangaben)
 Datenpakete unterliegen keiner Längenbeschränkung
 Paket-Ende: Prüfsumme und Endemarkierung
 reihenfolgegetreue Paketauslieferung
E-16
Beispiel: Myrinet Paketvermittlung
Store-and-Forward Routing
E-17
S = Source, Z = Zwischenknoten, D = Destination
Z
Z
D







Paket ist kleinste Einheit, besitzt alle Wegeinformation,
Pakete einer Nachricht sind voneinander unabhängig
und können (müssen aber nicht) auf verschiedenen
Pfaden übertragen werden
Das Paket wird vollständig von einem Knoten
empfangen (store), danach dekodiert und danach zum
ausgewählten Weg weitergeleitet (forward)
Wenn die Pakete einer Nachricht auf demselben Pfad
übertragen werden, ist Paket-Pipelining möglich
(Internet)

Paket ist immer auf
höchstens zwei Knoten und
einen Weg verteilt.
Paket-Laufzeit proportional
zur Paketlänge und Anzahl
der Wege
Geringe Blockierungsrate, da
nur zwei Knoten (lokal)
beteiligt
Bei einem Fehler: nur die
letzte Paketübertragung
muss wiederholt werden
geeignet für fehleranfällige
Netzwerke
S
Wormhole Routing
E-18




Nur ein Sende- und ein Empfangspuffer (weniger
Speicherplatzbedarf als Store-and-Forward)
Nur das erste Phit enthält die Routing Information, die
weiteren Phits folgen diesem.
Phits werden einzeln übertragen, aber guter Durchsatz
durch Phit-Pipelining
Phits werden nur übertragen, wenn der Weg nicht
blockiert ist und der Empfangspuffer des nächsten
Knotens nicht voll ist.

Problem: Paket ist über viele
Knoten und Leitungen verteilt.

Korrektheit der Übertragung
wird im Zielknoten überprüft,
bei einem Fehler muss das
ganze Paket erneut über den
gesamten Weg übertragen
werden.
Blockiert
durch andere
Übertragung

Die Knoten können eine
begrenzte Zahl von Phits
puffern.

Im Unterschied zum
Wormhole-Routing, wird im
Blockierungsfall ein Teil des
Paketrestes empfangen und
zwischengespeichert.

Das führt in der Tendenz
dazu, dass Blockierungen
sich über weniger Knoten
ausdehnen und sich leichter
wieder auflösen.
blockiert
blockiert
voll
Die Nachricht kann verteilt über mehrere
Zwischenknoten gepuffert werden.
angewendet im massiv-parallelen
Rechner CRAY T3E
E-19
Buffered Wormhole Routing
Virtual-Cut-Through Routing
Z
Z
D
blockiert

Paketpuffer in den Knoten

Phits werden von Knoten zu
Knoten sofort weitergegeben,
falls Weg nicht blockiert

Im Unterschied zum WormholeRouting, wird im
Blockierungsfall der gesamte
Paketrest am Kopf
aufgesammelt.

Das führt in der Tendenz dazu,
dass Blockierungen lokalen
Charakter haben und sich noch
leichter wieder auflösen.
S
E-20
Knoten mit Paketpuffer
Flitspeicher
Paket 1
Eingang
Ausgang
Paket 2
Temporärer Paketpuffer
Demultiplexer
E-21
Virtual-Cut-Through
Veranschaulichung
E-22
Wormhole
n
R
Anzahl der Knoten (z. B.
Prozessoren, Speicherbänke)
Anzahl der Ports pro Prozessor (Grad
eines Knotens)

Je höher der Grad, desto




schneller ist die
Kommunikation,
teurer ist die Hardware; steigt
mit Anzahl der Pins am Chip.
weniger skalierbar ist die
Architektur, weil Zahl der Pins
begrenzt
Ziel: kleiner Grad, möglichst
konstant ( reguläre Struktur)
W Summe der Wege (alle direkten
bidirektionalen Verbindungen
zwischen den Knoten)
d Distanz, min. Anzahl der Wege einer
Verbindung, Entfernung
 Je größer die Distanz, desto
mehr Knoten/Links muss die
Nachricht durchlaufen
E-23
2. Netzstrukturen: Merkmale
Linie (1D Feld, lineares Feld)
1
2
3
4
Distanzen






0
n=5
R=2
R=1
W=n-1
Knoten
Ports (innere Knoten)
Ports (äußere Knoten)
Wege
nicht symmetrisch
gut erweiterbar am Rand
0
Distanzen
1
2
3
4
1
2
3
4
1
2
3
1
2
1
1
2
2
1
3
3
2
1
4
4
3
2
1
1
Summe
geteilt durch 20 :
Mittlere Distanz
10
7
6
7
10
40
2
0
E-24
n=8
R=2
W=8=n
d=3
Knoten
Ports
Wege
Distanz für die markierte
Verbindung
Achtung: Bei den folgenden Berechnungen werden bidirektionale Links (Wege) vorausgesetzt.
E-25
Beispiel n, R, W, d für Ringnetz
Dmax Durchmesser, max. Distanz aller Verbindungen (Knotenpaare)
im Netz
 Je größer der Durchmesser, desto
 länger dauert die Übertragung (mehr Knoten/Links müssen durchlaufen
werden)
 kleiner ist die Ausfallsicherheit, weil mehr Knoten/Links korrekt
funktionieren müssen
 Ziel: kleiner Durchmesser
S Summe der Distanzen aller kürzesten Verbindungen (dient zur
Berechnung der mittleren Distanz)
 Berechnung:
 reguläres Netz mit R=const.: Betrachte Verb. von einem Startknoten zu
allen Endknoten,
 sonst: betrachte alle n Knoten als Starknoten und bilde Mittelwert
E-26
Weitere Merkmale: Durchmesser, Summe ...
Beispiel Dmax und S für Ringnetz
n gerade
Dmax = 4 = n / 2
S = 1*2 + 2*2 + 3*2 + 4*1 = 16
n/2
S  2   i  n2
i 1
n ungerade

n
2
 ( n2  1)  n2
 ( n2 )2
Dmax = 3 = ( n - 1 ) / 2
S=1*2 + 2*2 + 3*2 = 12
S  2
( n 1) / 2
i
i 1
 ( n21 )2  n21
2
 Dmax
 Dmax
2
 Dmax
E-27
Weitere Merkmale: Distanzen
mittlere Distanz
 Gibt an, wie lang die Verbindung im Mittel ist, n-1: Anzahl der
Zielknoten
 1/D = Maß für die Geschwindigkeit des Netzes
 Ziel: D möglichst klein
DR = D*R
normalisierte Distanz
 zur vergleichenden Bewertung: Bei mehr Ports wird die mittlere
Distanz kleiner, aber die Kosten sind dafür höher. Es wird deshalb mit
R multipliziert, um den Kostenfaktor einzubeziehen.
 Grobes Maß für die Kosten/Geschwindigkeit
 Formel gilt nur für reguläres Netz mit R=const.
 Ziel: möglichst klein
D = S/(n-1)
E-28
Weitere Merkmale: Verkehrsdichte
E-29
 Maß für die notwendige Übertragungskapazität der Wege, zur
vergleichenden Bewertung, Annahmen:




jeder Prozessor erzeugt permanent die Einheitslast 1
n Prozessoren erzeugen die Last n
im Mittel werden D Wege belastet
die Gesamtlast verteilt sich gleichmäßig auf alle Wege W
V = (D*n)/W mittlere Verkehrsdichte
n gerade
Summe Distanzen
Durchmesser
Norm. Distanz
Verkehrsdichte
S = 16 = n2/4
D = 16/7 = n2/(4n-4)  n/4
DR  n/2
V  n/4
E-30
Beispiel D, DR und V für Ringnetz
Weitere Merkmale: Bisektionsweite Bmin
 Je niedriger also die
Bisektionsweite, desto
ungünstiger wirkt sich dies auf den
Zeitbedarf für den Datenaustausch
zwischen den beiden Netzhälften
aus.
B=8
Bmin=6
Bmin=6
 Die Bisektionsweite Bmin gibt die
minimale Anzahl von Links an, die
durchschnitten werden müssen,
um ein Netz mit N Knoten in zwei
Netze mit jeweils N/2 Knoten zu
teilen.
 Damit ist sie ein Maß für die
Kommunikationsfähigkeit eines
Netzes, da in vielen Algorithmen
die Knoten der einen Netzhälfte mit
den Knoten der anderen Hälfte
kommunizieren.
 Die Bisektionsweite mulitpliziert mit
der Bandbreite eines Links
entspricht der
Bisektionsbandbreite
E-31
Weitere Merkmale: Konnektivität Hmin
Hmin = 2
Bemerkung: Es läßt sich analog zur
Kanten-Konnektivität eine KnotenKonnektivität definieren (Wieviele
Knoten müssen entfernt werden um
die Weiterleitung von Nachrichten zu
unterbrechen)
 Minimale Anzahl Hmin von
Wegen, die aus dem Netz
entfernt werden müssen, um das
Netz zu unterbrechen, d.h. in
zwei unverbundene Teilnetze zu
zerlegen.
 Je höher die Konnektivität, desto
 mehr unabhängige
Verbindungen zwischen je zwei
Knoten gibt es im Mittel
 besser ist die Ausfallsicherheit,
weil es alternative Pfade
(Umwege) gibt.
 schneller ist die Kommunikation,
weil hoch belastete Stellen des
Netzes (Staus, Blockierungen)
umgangen werden können.
 Ziel: Hohe Konnektivität
E-32
Weitere Merkmale: Fehlertoleranz F
 Allgemein: die Eigenschaft eines
technischen Systems, seine
Funktionsweise auch
aufrechtzuerhalten, wenn Fehler
in der Hardware, der Software
oder bedingt durch unzulässige
Eingaben auftreten.
 verschiedene Definitionen sind
möglich, hier wird vereinfachend
definiert
 F = Hmin - 1
E-33
 Ziel: hohe Fehlertoleranz
F=1
Fehlertoleranz
H=6
F=5
H=8
F=7
Es sind alle möglichen
Schnitte zu betrachten,
die das Netz in zwei
Teile zerlegen. Hier
einige davon 
H=9
F=8
Hmin=4
Fmin=3
E-34
Ringnetz, Bewertung
Chordaler
Ring
n
R=2
W=n
Dmax  n/2
D  n/4
DR  n/2
V  n/4
F=1
Durch zusätzliche Verbindungen ergeben
sich Strukturen mit höhereren Leistungen
und höherer Fehlertoleranz
Anzahl der Prozessoren
Ports
Summe Wege
Durchmesser
Mittlere Distanz
Normalisierte Distanz
Verkehrsdichte
Fehlertoleranz
E-35
 EIB data ring for internal
communication
 Four 16 byte data rings,
supporting multiple transfers
 96B/cycle peak bandwidth
 Over 100 outstanding requests
(c) Dr. Michael Perrone, IBM
6.189 IAP 2007, Lecture 2
Introduction to the Cell Processor
Michael Perrone ([email protected]).
E-36
IBM Cell Processor: Element Interconnect Bus
 Four 16B data rings connecting 12 bus elements
 Two clockwise / Two counter-clockwise
 Physically overlaps all processor elements
 Central arbiter supports up to three concurrent transfers per data ring
 Two stage, dual round robin arbiter
 Each element port simultaneously supports 16B in and 16B out data path
 Ring topology is transparent to element data interface
E-37
Element Interconnect Bus – Data Topology
Vollständig vernetzt
n
R = n-1
W = n *(n-1)/2
Dmax = 1
D=1
DR = n-1
V = 2/(n-1)
F = n-2
Ports
Summe Wege
Durchmesser
Mittlere Distanz
Verkehrsdichte
Fehlertoleranz
E-38
Modell MC: Mesh Connected,
(n-dimensionales Gitter)
Dimension
Modell
Bezeich.
Ports
Ports
am Rand
1
MC1
Reihe
2
1..2
2
MC2
Gitter
4
2..4
3
MC3
Würfel
Cube
6
3..6
n
MCn
n-Cube
2n
n..2n
 Varianten
 zyklische Verbindung der Ränder
(wrap-around)
 zyklische Verbindung, um eine
Zeile versetzt (Illiac-Netzwerk)
 Merkmale
 nur lokale Kommunikation
zwischen den Nachbarn
 für massiv parallele Anwendungen
gut geeignet
 gut erweiterbar, Ports=const.
 Anwendungen
 Algorithmen mit lokaler
Kommunikationstruktur,
Modellierung physikal. Prozesse
 2-dim. Gitter zur Lösung partieller
Differentialgleichungen
 Zellularautomat, CRAY-T3 (3-dim
Prozessorfeld)
E-39
 MPP = Massively Parallel
Processor System
 T3E-1350: bis 1024 AlphaProzessoren (EV5.6) 675 MHz, 1
Prozessor pro Knoten
 3-D-Netzwerk mit Wrap-around
(Torus), schneller Zugriff auf
benachbarte Knoten
E-40
Beispielrechner: 1996: CRAY T3E
Figure 8. +X, +Y, and +Z Information Travel.
Dimension Order Routing.
Information travels in the X dimension first,
then thrugh the Y dimension, and finally through
the Z dimension the information arrives at the
destinat on node. Each transfer of information
over a communication link is hereafter referred to
as a hop.
Figure 9. -X, -Y, -Z Information Travel
E-41
CRAY T3E, Routing
E-42
CRAY T3E, Routing
Figure 10. Avoiding a Bad Communication Link in the Y Dimension.
Illiac-Netzwerk
E-43
Baumstruktur

Strukturvarianten, gegeben durch
 Verzweigungsgrad (Anzahl der Ports
nach unten/oben)
 Anzahl der Ebenen
 Anzahl der nicht angeschlossenen
Knoten
Binärbaum
Kommunikation erfolgt über den darüber
liegenden Knoten/Weg (möglicher Engpaß,
fehleranfällig)
X-Baum

zusätzliche Querverbindungen sind
denkbar, z.B. X-Baum, Pyramide

wichtiger Sonderfall: Sternnetz
Stern

E-44




Ziel: zwischen allen Knotenpaaren soll in
etwa die gleiche Übertragungskapazität zur
Verfügung gestellt werden.
Die Kapazität der Kanten nimmt mit der
Höhe der Ebene zu.
Die Komplexität eines Knotens nimmt mit
der Ebene zu.
Routing: auf direktem Weg über
niedrigsten gemeinsamen Vorfahren
Bild entnommen aus http://www.it.irf.uni-dortmund.de/IT/Resource/prs/PRS_Slides_2004.ppt
E-45
Fat Tree

n = 2k Knoten, k = Dimension
k=1

Knoten können durch eine
Dualzahl mit k Bits codiert
werden

verbunden sind die Knoten, die
sich bei dualer Codierung genau
an einer Bitposition
unterscheiden (HammingDistanz 1).

Es gibt k direkte Wege, die von
einem Knoten ausgehen bzw. in
ihm enden.
k=2
k=4
k=3
k=4
E-46
Modell CC: Cube Connected (Hyperwürfel),
Hypercube
Hypercube, im Kreis angeordnet
E-47
Hypercube
Mittlere Distanz D ist kleiner als
k, Berechnungsbeispiel:
k=2
k=3
k=4
k
Ports
Summe Wege
Durchmesser
Mittlere Distanz
Verkehrsdichte
Fehlertoleranz
2*1 + 1 * 2
= 4/3 = 1,5
3*1 + 3*2 + 1*3
= 12/7 =1.71
4*1 + 6*2 + 4*3 +1*4 = 32/15 = 2,133
D  k/2
n = 2k
R=k
W = k* 2k-1
Dmax = k = log n
D  k/2
DR  k2/2
V1
F = k-1
k=3



geeignet für eine Vielzahl von
Algorithmen (Hypercube-Alg.)
Erweiterbarkeit schlecht (Anzahl
der Ports erhöht sich,
Verdoppelung der Knoten)
gute Fehlertoleranz

E-48
 k-dimensionalen Hyperwürfel, bei
dem jeder Hyperknoten durch
einen Ring der Länge k ersetzt
wird.
 Jeder dieser k Ringknoten besitzt
neben den zwei Ringkanten eine
weitere Kante zu einem anderen
Hyperknoten
 Eigenschaften:
 logarithmischer Durchmesser
 konstanter Knotengrad (=3)
 Erweiterung nur in
Zweierpotenzen
E-49
CCC(k), Cube Connected Cycles
Barrel-Shifter
 n = 2k Knoten
 verbunden sind die Knoten mit den Abständen 1, 2, 4, ... 2k-1
(Schiebeschritte mit allen Zweierpotenzen)
 Beliebiger Shift wird aus Zweierpotenzen zusammengesetzt
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
E-50
Barrel Shifter (2)
Andere Darstellung
E-51
Vergleich
Hypercube
Ring
n=8
Hypercube
n=8, k=3
Anzahl der
Prozessoren
n
n = 2k
8
8
Ports R
2
k = log2 n
2
3
höherer
Aufwand
Summe Wege
W
n
k* 2k-1
= n/2 *
log2n
8
12
höherer
Aufwand
Durchmesser
Dmax
n/2
k = log2 n
4
3
kleiner
Mittlere Distanz
D
n/4
k/2 =
0.5 log2 n
2
1.5
kleiner
Normalisierte
Distanz DR
n/4
k2/2
2
4,5
ungünstiger
Verkehrsdichte
V
n/4
1
2
1
geringer
Fehlertoleranz
F
1
k-1
1
2
besser
Zum Vergleich sollten die Kosten der
Netze nach einer angenommenen
Kostenfunktion berechnet werden, z. B.
nach folgender Formel mit den
Koeffizienten a, b, c:
Eine mögliche Kostenfunktion
f = a *(W*V) + b*(n) + c*(n*R*V)
berücksichtigt
Wegekosten und
notwendige
Übertragungskapazität
berücksichtigt
die Kosten
der Ports
berücksichtigt
Grundkosten
eines Knoten
Ring
E-52
Vergleich für n = 64 Knoten
MC2Wrap
m gerade
Anzahl der
Prozessoren
n
n=m
Ports R
2
4
Summe Wege W
n
2m
Durchmesser Dmax
n/2
m
2
Hypercube
n=2
k
k
2
BarrelShifter
n=2
k
Ring
n=64
MC2Wrap
m=8
Hypercube
n=64
k=6
Barrelshifter
n=64
k=6
64
64
64
64
2k -1
k* 2
k-1
k
2
k-1
(2k-1)
k/2
2
4
6
64
128
192
32
8
6
11
Aufwand
352
3
kürzer
Mittlere Distanz D
n/4
~m
~k/2
Normalisierte
Distanz DR
n/2
~4m
~k /2
~ 2/3 * k
Verkehrsdichte V
n/4
~m/2
~1
Fehlertoleranz F
1
3
k-1
2
~k/3
16
2
8
3
2
16
32
18
24
~1/3
16
4
1
1/3
2(k-1)
1
3
5
10
niedriger
Ring
E-53
Schaltbares Verbindungsnetz
 Alle Knoten/Prozessoren werden über ein gemeinsames
Verbindungsnetz miteinander auf Anforderung dynamisch
verbunden.
 Häufig werden verwendet:
 Crossbar
 Bussysteme
 Mehrstufige Netze
E-54
Dynamische Verbindungsnetze
Crossbar-Switch, Kreuzschienenverteiler, Schaltermatrix








maximal n2 Bits
ohne Datenvereinigung n*log2(n+1)
(höchstens ein Punkt vertikal)
ohne Broadcasting noch geringer
(höchstens ein Punkt horizontal)
wegen der vielen Anschlüsse nur begrenzt als
Baustein herstellbar
schlecht erweiterbar
Bits zur Steuerung

blockierungsfrei: beliebiger Prozessorausgang
kann mit einem beliebigen Prozessoreingang
verbunden werden
maximal können gleichzeitig n Verbindungen
(bei n Prozessoren) aufgebaut werden
prinzipiell Permutationen, BroadcastVerbindungen, Datenvereinigungen möglich.
hoher Hardware-Aufwand (n2 Schalter)
Steuerbits
1 aus (n+1)  log2 (n+1)

E-55
1987: CRAY Y-MP
gemeinsame Register
8 CPUs
4
1. Stufe: 8 Crossbars (4 x 4)
2. Stufe: 4 Crossbars (8 x 8)
3. Stufe: 32 Mux/Demux(1 x 8)
3232
3232
32256
Mehrstufige
Crossbars
1
256 Speicherbänke
4 YMP über gemeinsamen Speicher
gekoppelt
 C90, T90
E-56
 Kompromiss zwischen
Einbussystem und Crossbar
 Kostengünstig: benötigen nur
eine begrenzte Anzahl von
Bussen und Schaltern
 kostengünstiger als ein großer
Crossbar
A
B
A
B
 Blockierend  Busarbitration
 gut erweiterbar
 Systemleistung sinkt mit der
Anzahl der Knoten
 Einbussystem: keine
Fehlertoleranz bei Busausfall
E-57
Mehrfachbussysteme
Permutationsnetze
 Ein Permutationsnetz
vertauscht die Ausgänge der
Prozessoren und verbindet sie
mit den Eingängen.
 Die Verbindungsfunktion
beschreibt die Verbindungen
zwischen den Prozessoren als
Funktion
 Jede beliebige Permutation läßt
sich direkt einstellen oder durch eine
mehrfache Anwendung der
Verbindungsfunktion realisieren.
 Die meisten Netzwerke sind nicht
universell, erlauben aber den
Transport eines Datums zwischen
beliebigen Prozessoren durch eine
Folge von Permutationen (Beispiel:
geschlossener gerichteter Ring).
1
2
3
4
5
6
Verbindungsfunktion: f(i) = (i+1) mod n
7
im Mittel
n/2 Schritte für einen
Datentransport
 Universelles Permutationsnetz
 Durch mehrfache Anwendung
der Verbindungsfunktion kann
eine Menge von
Permutationen Mi erzielt
werden.
0
E-58
Perfect-Shuffle

Perfektes Mischen
 n=2k Spielkarten werden in zwei gleich große
Hälften geteilt, dann werden abwechslend aus
den beiden Hälften die Karten für einen neuen
Stapel entnommen.
Abbildungsfunktion (Verbindungsfunktion):
 f(0)=0, f(n-1)=n-1
f(i) = 2i mod(n-1) für i=1 ...n-2
i: Quellknotennummer, 2i mod(n-1):
Zielknotennummer
 oder bei dualer Codierung
 Zielknotencodierung <zyklischerLinksshift(Quellknotencodierung)
n=23
i
nicht universell
Datentransport im Mittel in (log2 n)/2 Schritten, falls
überhaupt möglich (maximal log2 n Schritte); s.
nächste Folie
2i
mod 7
0=ooo
f(i)
0=ooo
1=ool
1
2
2=olo
2=olo
4
4
4=loo
3=oll
6
6
6=llo
4=loo
8
1
1=ool
5=lol
10
3
3=oll
6=llo
12
5
5=lol
7=lll


2i
7=lll

E-59
Perfect-Shuffle
PS-Netz, Räumliche Abwicklung, Verdrahtung.
Die Permutationen und erreichbaren Zielknoten
durch Hintereinanderschaltung der Verbindungsfunktion
1.
2.
3.
0
0
0
0
0
1
1
1
1
1
2
2
2
2
2
3
3
3
3
3
4
4
4
4
4
5
5
5
5
5
6
6
6
6
6
7
7
7
7
Quell- und
Zielknoten
7
Quellknoten
Beachte:
Nicht alle Zielknoten
sind von jedem
Startknoten aus
erreichbar!
Gruppen:
{{0},
{1,2,4},
{3,5,6}}
nur die Knoten
innerhalb einer
Gruppe sind
erreichbar
Zielknoten
Zielknoten werden
durch Sequentielle
Anwendung der
Verbindungsfunktion
(Shuffle-Wege) erreicht
E-60
Shuffle-Exchange-Verdrahtung
Durch zusätzlich Exchange-Wege können
alle Knoten erreicht werden
Quellknoten
Exchange-Schalter
Zielknoten
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
2
2
2
2
2
2
2
2
3
3
3
3
3
3
3
3
4
4
4
4
4
4
4
4
5
5
5
5
5
5
5
5
6
6
6
6
6
6
6
6
7
7
7
7
7
7
7
7
Bei der dualen Codierung der Knoten bedeutet Exchange die Invertierung der niedrigsten Bitstelle
Shuffle-Wege
+ Exchange-Wege
E-61
Schalter
b


c
Kleine Exchange-Schalter (z. B. 2x2) dienen
als Zellen, die in Stufen zu komplexen Netzen
verschaltet werden.
Elementare Schalterzustände:




Durchschaltung (a),
Kreuzschaltung (b),
obere (c) und
untere (d) Vervielfältigung
d
a
E-62
 Hintereinanderschaltung der Shuffle-Verdrahtung mit s ExchangeSchaltern
 Bei n = 2k Eingängen/Ausgängen werden k = log2 n Stufen benötigt.
 s = (k/2)* 2k = k *2k-1 Schalter (Hardware-Aufwand gering)
 nicht alle Permutationen 2k! können geschaltet werden, nur 2s ,
nicht universell
 z.B. dreistufiges Omega-Netz hat 8 Eingänge und 3*4=12 Schalter
 8! = 40.320 Permutationen, 212 = 4096 Schalterzustände
 Routing R
 von Source s nach Destination d
 duale Codierung: vergleiche s- und d-Bits von links nach rechts, wenn
ungleich dann Exchange(x) sonst Durchschalten(-)
s=22=l o l l o
d=27=l l o l l
R
- x x - x
E-63
Omega-Netz
(programmierbares Shuffle-Exchange-Netz)
Omega-Netz
Kollision, also diese beiden
Verbindungen sind nicht
gleichzeitig schaltbar!
0
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
Exchange-Schalter
s=0=000
d=0=000
R= - - -
s=4=1 0 0
d=3=0 1 1
R= x x x
E-64
 Das Omega-Netz kann auch in umgekehrter Richtung
betrieben werden
 dieses inverse Netz ist in analoger Weise eindeutig routbar, ebenfalls
nicht universell
 Bidelta-Eigenschaft: Netz in eindeutiger Weise in beiden Richtungen
routbar.
 Bidelta-Netze sind topologisch äquivalent






Omega
Banyan
Butterfly
Baseline
Flip
de-Bruijn
E-65
Bidelta-Netze
Banyan (gespiegelt ergibt:Binäres n-cube Netzwerk)
E-66
Butterfly
000
001
LSB
Mögliche
Implementierung:
Demultiplexer
mit Tri-State
010
011
100
101
110
oder Multiplexer
111
Zum Routing werden die Bits der Quelladresse und Zieladresse absteigend
verglichen (vom MSB (most significant bit) zum LSB (least signifcant Bit)) ,
falls gleich, wird die Information in direkter Richtung weiter geschickt,
ansonsten wird der andere Weg eingeschlagen
Butterfly-Wege
MSB 
E-67
Butterfly (2), Beispiel Routing
LSB
0
0
0
1
1
1
Quelladr. Zieladr.
2
2
0011
2
0111
1000
3
3
Kollision
nicht gleichzeitig
möglich
1101
3
Wege
MSB
E-68
Butterfly (3)
realisiert mit Exchange-Schaltern
0
0
0
0
1
1
1
1
2
2
3
3
2
3
2
3
E-69
3-dim. Benes Netzwerk
Reihen
000
001
(r-1) - dimensionales
Benes Netzwerk
010
011
100
101
(r-1) - dimensionales
Benes Netzwerk
110
Das Benes Netzwerk kann
sowohl die doppelte
Verwendung einer Kante als
auch die doppelte
Verwendung eines Knotens
vermeiden.  Universelles
Netz
Ein konzeptioneller Nachteil
bei Butterly Netzwerken ist
die Gefahr von Hot Spots.
Diese lassen sich jedoch mit
einem Benes Netzwerk
vermeiden. Das Benes
Netzwerk besteht aus 2
spiegelsymmetrischen Butterfly
Netzwerken und weist somit
fast die doppelte
Hardwarekomplexität im
Vergleich zu einem Butterfly
Netzwerk auf.
E-70
111
0
1
2
3
4
5
6
Stufen
realisierbar mit (n log2n –n/2 )Exchange-Schaltern, Stufenzahl=2log2n -1
http://www.it.irf.uni-dortmund.de/IT/Resource/prs/PRS_Slides_2004.ppt
CLOS-Netz
2. Stufe
m Crossbars (r x r)
3. Stufe
r Crossbars (m x n)
- von CLOS (1953)
vorgeschlagen
- benötigt weniger Schalter
als Crossbar (n x n)
- nichtblockierend, wenn m
genügend groß gewählt
wird.
1. Stufe
r Crossbars (n x m)
E-71
Crossbar
Bus
Bidelta
Netze
Gleichzeitige
Verbindungen
n
1
<n
Latenz
(Distanz)
1
1
log2 n
Logik
n2
n
TREIBER
n (log2 n)
MUX/DEMUX
oder
n/2 (log2 n)
SCHALTER
E-72
Vergleich Dynamische Netze
Bandbreiten und Latenz von schnellen
Verbindungsnetzen
theor.
Bandbreite
Gbit/s
effektive
Bandbreite
ca. MB/s
Latenz
us
Gigabit
Ethernet
1
85
80
SCI
(Scalable
Coherent
Interface)
1-8
82
3-15
Myrinet
2000
4
250-438
8-10
Inifiniband
2.5 * (1..12
Links)
SDR *1
DDR*2
QDR*4
25012 000
1-3
Myrinet
• Message Passing
• Switch-basiert
neuer Standard zur Kopplung von Knoten und Geräten
E-73
 SCI = Scalable Coherent Interface,
ANSI/IEEE 1596-1992.
 64-bit globaler Adressraum (16-bit node
ID, 48-bit local memory).
 Garantierter Datentransport durch
paketbasiertes Handshake Protokoll.
 Schnittstellen mit zwei unidirektionalen
Links die gleichzeitig arbeiten können.
 Unterstützt gemeinsamen Speicher und
Nachrichtenaustausch.
 Definiert Cache-Kohärenzprotokoll.
http://kbs.cs.tu-berlin.de/teaching/ws2002/cl/cc2.pdf
E-74
Scalable Coherent Interface
 Ergebnis zweier konkurrierender Systeme: Future I/O von
Compaq, IBM und Hewlett-Packard und Next Generation I/O
von Intel, Microsoft und Sun Microsystems
 De-facto Standard für Supercomputer Cluster
 bidirektionale serielle Links, 8B10B Codierung
 Síngle/Double/Quad-Data Rate, bis zu 12 Kanäle parallel, 2-96
GBit/s (250-12 000 MB/s) eff. Durchsatz
 Latenz: Chip (ca. 100-200 ns), über MPI (ca. 1 us)
 Operationen
 Send/Receive Messages between Queue Pairs
 RDMA = Remote Direct Memory Access
 RDMA Atomics (zur Synchronisation:Compare&Swap, Fetch&Add)
E-75
Infiniband
Switches
and Router
http://www.oreillynet.com/pub/a/netw
ork/2002/02/04/windows.html
An Introduction to the InfiniBand
Architecture by Odysseas
Pentakalos, coauthor of Windows
2000 Performance Guide
02/04/2002
HCA=Host Channel Adapter
TCA=Target Channel Adapter
E-76
Infiniband, Point-to-Point Verbindungen
a
b
c
d
a1
b1
c1
d1
A
B
C
D
Gegeben: Gerichtetes Ringnetz mit 4 Knoten. Jeder Knoten enthält zwei
Register.
Zwischen zwei benachbarten Knoten gibt es 4 alternative synchrone
Transporte: (z.B. von A nach B: ab oder ab1 oder a1b oder
a1b1).
Die Register a,b,c,d werden mit Werten vorbelegt (a=1, b=2, c=3, d=4).
Die Register a1, b1,c1, d1 dienen als Hilfsregister.
Gesucht: Steuerablauf als Verilog-Programm, der die Registerinhalte
(a,b) und (c,d) miteinander vertauscht. Wieviel Schritte werden benötigt?
E-77
Kleines Verilog Netz-Beispiel: Synchron-paralleler
Datenaustausch auf einem Ringnetz
Steuerablauf
B
C
a
b
c
Datenwerte entsprechen
verschiedenen Farben.
D
d
a1
b1
c1
d1
a
b
c
d
a1
b1
c1
d1
a
b
c
d
a1
b1
c1
d1
a
b
c
d
a1
b1
c1
d1
1.) nach rechts schieben
A
E-78
(Zwei Ergebnisse schon in B und D)
2. )a und c nach rechts unten schieben
3. ) b1 und d1 nach rechts oben schieben
(Ergebnisse in A, B, C, D:
Nachbarn sind vertauscht)
// Ring Netz: a,b,c,d. --- 7.10.03 rh
// vertauschen von a<->b und c<->d
module ring();
reg clock;
reg [7:0] a, b, c, d;
//knoten
reg [7:0] a1, b1, c1, d1; //hilfsregister in den knoten
reg [1:0] state;
reg stop;
always @(posedge clock)
begin
case(state)
0: begin
//stop=01
a <= 1; b <= 2; c <= 3; d <= 4;
//init
state<=1;
end
1: begin
// a = 1, b = 2, c = 3. d = 4;
b<=a; c<=b; d<=c; a<=d;
state<=2;
end
2: begin
b1<=a; d1<=c;
state<=3;
end
3: begin
a<=d1; c<=b1;
stop<=1;
state<=0;
end
endcase
end
// --- Hardware-Initialisierung
initial
begin
state=0; stop=0;
end
// ausgabe bei änderung von state
always @(state)
begin
$display(" --- state=%H",state);
$display("a =%H, b =%H, c =%H, d =%H",a,b,c,d);
$display("a1=%H, b1=%H, c1=%H,
d1=%H",a1,b1,c1,d1);
end
// --- Taktgenerator, Testumgebung --integer i;
initial
begin
#0
clock=0; i=0;
#5
while (i<20)
begin
#5 clock=!clock; i=i+1; //pos. flanke
#5 clock=!clock;
//neg. flanke
if (stop)
begin
#5 $finish;
end
end
end
endmodule
E-79
(Beispiel) Verilog-Programm
--- state=0
a =xx, b =xx, c =xx,
a1=xx, b1=xx, c1=xx,
d =xx
d1=xx
Initialisierung
--- state=1
a =01, b =02, c =03,
d =04
d1=xx
(a,b,c,d) zyklisch nach rechts
--- state=2
a =04, b =01, c =02,
d =03
d1=xx
ab1, cd1
--- state=3
a =04, b =01, c =02,
a1=xx, b1=04, c1=xx,
d =03
d1=02
d1a, b1c
--- state=0
a =02, b =01, c =04,
a1=xx, b1=04, c1=xx,
d =03
d1=02
E-80
(Beispiel) Ablauf, Verilog-Ausgabe
(Beispiel) Timing-Diagramm
E-81



Statische und Dynamische Netze
Leitungsvermittlung
Paketvermittlung







Nachrichten
Pakete
Phits
Store-and Forward- Routing
Wormhole Routing
Virtual-Cut-Through Routing
Netzmerkmale
 Ports, Durchmesser, mittl. Distanz,
Verkehrsdichte, Fehlertoleranz




Ring
MC: Mesh Connected (Gitter)
Illiac-Netz (Zeilen Wrap versetzt)
Baum, Fat-Tree




Modell CC: Hypercube,
Barrel Shifter
Crossbar
Permutationsnetze





Shuffle-Exchange
Omega
Butterfly
CLOS
Verilog-Beispiel
 Datentransport auf gerichtetem
Ringnetz
E-82
Zusammenfassung

elta mp 212

Transcrição

Documentos relacionados

Ad-hoc-Betreuung an der Waldspirale in Darmstadt

01 Einf hrung (VL03)

Angebote Herbst 2016 - Carl Hoffmann Landmaschinen GmbH

dr. jörg hoffmann - Isenbruck Bösl Hörschler LLP

Kinobesuch in Darmstadt

5 Jahre TKD DA2 - Traditional Taekwon

L iebfrauen - Pfarrei Liebfrauen Darmstadt

Darmstadt Card Flyer_2012.indd

Max Hoffmann ASC Marathon Friedberg erreichte in der Klasse M35