Algorithmen für synchrone Rechnernetze

Titel: Algorithmen für synchrone Rechnernetze
Organisation: UNI PADERBORN
Seitenzahl: 90

Skript herunterladen (PDF)

Inhalt

Skript zur Vorlesung Algorithmen fur synchrone Rechnernetze
Abbildung Prozessornetzwerk und seine Darstellung als Graph
Parallelisierung von Algorithmen am Beispiel der Matrizenmultiplikation
e e e e
Inhalt der Vorlesung
Literaturangaben und Lehrbucher
Die Parallele Random Access Maschine
Von der RAM zur PRAM
KAPITEL DIE PARALLELE RANDOM ACCESS MASCHINE
Die verschiedenen PRAM Modelle
Netzwerke der HypercubeFamilie
KAPITEL NETZWERKE DER HYPERCUBEFAMILIE
Abbildung Der Hypercube der Dimension und
Abbildung Der rekursive Aufbau des Q
Abbildung Der Doppelwurzelbaum der Hhe k o
Abbildung Einbettung des DWB in Q
Abbildung Einbettung des DWBk in Qk
Abbildung DWBk Teilgraph im Qk
Abbildung Das dimensionale Gitter M
Mn nd ist Teilgraph des Q
log ni logn nd
KAPITEL NETZWERKE DER HYPERCUBEFAMILIE f i j
d k el I I
Satz besagt daß Q
Abbildung Das CubeConnectedCycles Netzwerk der Dimension
Das Buttery und das CubeConnectedCycles Netzwerk
Abbildung Das Buttery Netzwerk der Dimension
Es gilt f i u f i ui
Abbildung Das DeBruijn Netzwerk der Dimension
Abbildung Der Faktorgraph GCCC
Algorithmen fur synchrone Rechnernetze
KAPITEL ALGORITHMEN FUR SYNCHRONE RECHNERNETZE
Abbildung Bestimmung des Minimums auf Q
ASCENDDESCEND Algorithmen fur den Hypercube
Abbildung Bestimmung des Minimums auf CCC
Procedure ASCEND procedure OPER var k dim k
nach Austausch in Dimension
Abbildung Vertauschungen in Q zum Routen von Rev
Bitones Sortieren auf der Hypercube
A B Vor der ersten ComparisonExchangeOperation gilt id
Es folgt D und E Fall A
Vertauschungen des Aufrufs r Vertauschungen des Aufrufs r
Vertauschungen des Aufrufs r
Abbildung Vertauschungen beim bitonen Sortieren auf Q
ASCENDDESCEND Algorithmen auf anderen Netzen der HypercubeFamilie
ASCENDDESCEND auf SEk
Kommunikation in Dimension
Abbildung Simulation eines ASCEND Laufs auf dem SE
ASCENDDESCEND auf CCCk
kdim Ok On
u nach Drehung
Abbildung Simulation eines ASCEND Laufs auf dem CCC
ij i n xj n
i nin uin n vin uin n vin
in uin n vin
i yi ui n vi
i yin ui n vi
Abbildung Basisoperation des FFTAlgorithmus
Broadcasting und Gossiping
Abbildung Optimale BroadcastBume a
i m ICliquen ist
Abbildung GossipGraph Gos
Ax x n j aij n i xi
i i j ui uj
i ui i ui n x x
At a br n
Bisektionsweite und Partitionierung
Untere Schranken fur die Bisektionsweite
Verfahren von Leighton
KAPITEL BISEKTIONSWEITE UND PARTITIONIERUNG
Abbildung Bisektion des Qk mit k Kanten
Spektrale untere Schranke
und deshalb gilt
xi xj xi xj xi xj xi xj
vi vj ExtV V
Obere Schranken fur die Bisektionsweite
n Zu zeigen extV V O log n
V V B C C C B
V V B D B B B
Abbildung Graph mit Knoten und Bisektionsweite

Vorschau

Skript zur Vorlesung Algorithmen fur synchrone ¨ Rechnernetze

Version 1.34

0000 1000 0100 0010 0001

1001 1100 1010 0110 0101 0011

1101 1110 1111

1011 0111

Prof. Dr. Burkhard Monien, Sven Grothklags, Henning Meyerhenke Universit¨t Paderborn a Fakultat fur Elektrotechnik, Informatik und Mathematik ¨ ¨ D-33102 Paderborn

Inhaltsverzeichnis

1 Einleitung 1.1 Parallelrechnerarchitekturen . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Parallelisierung von Algorithmen am Beispiel der Matrizenmultiplikation 1.3 Inhalt der Vorlesung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4 Literaturangaben und Lehrb¨ cher . . . . . . . . . . . . . . . . . . . . . u 2 2 4 5 6 7 7 9 11 13 23 27

. . . .

2 Die Parallele Random Access Maschine 2.1 Von der RAM zur PRAM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Die verschiedenen PRAM Modelle . . . . . . . . . . . . . . . . . . . . . . . . 3 Netzwerke der Hypercube-Familie 3.1 Der Hypercube . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Das Butterﬂy und das Cube-Connected-Cycles Netzwerk . . . . . . . . . . . . 3.3 Das DeBruijn und das Shuﬄe-Exchange Netzwerk . . . . . . . . . . . . . . .

4 Algorithmen fur synchrone Rechnernetze 34 ¨ 4.1 ASCEND/DESCEND Algorithmen f¨ r den Hypercube . . . . . . . . . . . . . u 36 4.2 Bitones Sortieren auf der Hypercube . . . . . . . . . . . . . . . . . . . . . . . 38 4.3 ASCEND/DESCEND Algorithmen auf anderen Netzen der Hypercube-Familie 43 4.3.1 ASCEND/DESCEND auf SE(k) . . . . . . . . . . . . . . . . . . . . . 43 4.3.2 ASCEND/DESCEND auf CCC(k) . . . . . . . . . . . . . . . . . . . . 46 4.4 Fast-Fourier-Transformation (FFT) . . . . . . . . . . . . . . . . . . . . . . . . 50 4.5 Broadcasting und Gossiping . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 4.5.1 Broadcasting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 4.5.2 Gossiping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 5 Bisektionsweite und Partitionierung 5.1 Untere Schranken f¨ r die Bisektionsweite u 5.1.1 Verfahren von Leighton . . . . . . 5.1.2 Spektrale untere Schranke . . . . . 5.2 Obere Schranken f¨ r die Bisektionsweite . u Literatur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 69 69 71 73 87

1 Kapitel 1

Einleitung

In den letzten Jahren ist der Bedarf an Rechenleistung so stark angestiegen, daß er von sequentiellen Computern nicht mehr erf¨ llt werden kann. Ein elektrischer Impuls kann sich u in Silizium mit einer Geschwindigkeit von 30.000 Kilometern pro Sekunde fortbewegen. Betrachtet man einen Chip mit 3 cm Durchmesser, der zur Verarbeitung einer Operation nur ein Signal ben¨tigt, so kann selbst dieser idealisierte Chip pro Sekunde h¨chstens 109 Operationen o o verarbeiten. Dies entspricht einer Leistung von einem Giga-Flop. F¨ r die L¨sung vieler praxisu o relevanter Probleme ben¨tigt man jedoch eine Rechenleistung von einigen hundert Giga-Flops o bis zu mehreren Tera-Flops. Beispielsweise muß f¨ r die Str¨mungssimulation in einem Flugzeugtriebwerk zu jedem Simuu o lationszeitpunkt ein Gleichungssystem mit mehreren 100.000 Unbekannten gel¨st werden. In o der Wirtschaft ben¨tigt man solch hohe Rechenleistungen, um die Optimierung von kompleo xen Produktionsprozessen voranzutreiben, und im Bereich der virtuellen Realit¨t m¨ ssen zur a u Echtzeit ganze R¨ume mit darin enthaltenen 3-dimensionalen Objekten bewegt werden. Die a Aufz¨hlung ließe sich beliebig fortsetzen und zeigt den immensen Bedarf an Rechenleistung a in allen Anwendungsbereichen der Informatik. Diese Rechenleistung kann nur erreicht werden, wenn mehrere Prozessoren gleichzeitig an der Probleml¨sung arbeiten. Die Erforschung o von Algorithmen f¨ r solche Parallelrechner nimmt daher eine Schl¨ sselposition innerhalb der u u Informatik ein. Diese Vorlesung f¨ hrt in konkrete Parallelrechnertopologien und ihre Algorithmik ein. Sie soll u damit neben Parallele Algorithmen I einen weiteren Einblick in die Welt der Parallelverarbeitung geben, welche eine der großen ukunftstechnologien darstellt. In dem ersten Abschnitt der Einleitung werden die verschiedenen Parallelrechnerarchitekturen kurz vorgestellt und untereinander abgegrenzt. Danach wird anhand der Matrizenmultiplikation gezeigt, wie ein sequentieller Algorithmus in einen parallelen Algorithmus uberf¨ hrt u ¨ ¨ werden kann. Abschnitt 1.3 gibt einen kurzen Uberblick uber die Inhalte der Vorlesung. Am ¨ Schluß der Einleitung ﬁndet man eine Liste von Lehrb¨ chern, die den Stoﬀ der Vorlesung u erg¨nzen. a

1.1 Parallelrechnerarchitekturen

In einem Parallelrechner arbeiten mehrere Prozessoren gleichzeitig an der L¨sung eines Proo blems. Daher muß ein Mechanismus bereitgestellt werden, mit dessen Hilfe die Prozessoren o untereinander kommunizieren k¨nnen. Je nachdem, wie dieser Mechanismus realisiert ist, un2