78
Architektur paralleler Plattformen Freie Universität Berlin Fachbereich Informatik Wintersemester 2012/2013 Proseminar Parallele Programmierung Mirco Semper, Marco Gester Datum: 31.10.12

Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

  • Upload
    haminh

  • View
    215

  • Download
    0

Embed Size (px)

Citation preview

Page 1: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

Architektur paralleler Plattformen

Freie Universität Berlin

Fachbereich Informatik

Wintersemester 2012/2013

Proseminar Parallele Programmierung

Mirco Semper, Marco Gester

Datum: 31.10.12

Page 2: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

Inhalt

I. Überblick über die Prozessorentwicklung

II. Parallelität innerhalb eines Prozessorkerns

III. Klassifizierung von Parallelrechnern

IV. Speicherorganisation

V. Verbindungsnetzwerke

Architektur paralleler Plattformen Teil 1 31.10.12

Page 3: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

I. ÜBERBLICK PROZESSORENTWICKLUNG

Architektur paralleler Plattformen

Architektur paralleler Plattformen Teil 1 31.10.12

Page 4: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

I. Überblick Prozessorentwicklung

- Zu Beginn Steigerung der Leistung primär über Taktrate

- Parallel dazu Verbesserung der Architektur und Steigerung der Transistorzahl

Quelle: http://njtechreviews.com/wp-content/uploads/2011/09/varian-moores-law-graph.gif

Architektur paralleler Plattformen Teil 1 31.10.12

Page 5: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

I. Überblick Prozessorentwicklung

- Ab 2005 Mehrkernprozessoren im privaten Bereich

Quelle: http://images.bit-tech.net/content_images/2011/01/intel-sandy-bridge-review/sandy-bridge-die-map.jpg

Architektur paralleler Plattformen Teil 1 31.10.12

Page 6: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

I. Überblick Prozessorentwicklung

Paralellität auf Bitebene

- Steigerung ab 1986 auf 32 bit, ab Mitte der 90er 64 bit

Gründe: genauere Floating Point Operationen möglich

größerer Ansprechbarer Adressraum

Architektur paralleler Plattformen Teil 1 31.10.12

Page 7: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

I. Überblick Prozessorentwicklung

Parallelität durch Pipelining

- Aufteilung der Verarbeitung einer Instruktion in verschiedene Teile

Quelle: Parallele Programmierung Rauber, Rünger ISBN 978-3-642-13603-0

Architektur paralleler Plattformen Teil 1 31.10.12

Page 8: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

I. Überblick Prozessorentwicklung

Parallelität durch mehrere Funktionseinheiten

- Es werden mehrere ALUs, FPUs und andere verbaut

- Entwicklung sind Grenzen gesetzt, da hoher Scheduling Aufwand

Quelle: Parallele Programmierung Rauber, Rünger ISBN 978-3-642-13603-0

Architektur paralleler Plattformen Teil 1 31.10.12

Page 9: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

I. Überblick Prozessorentwicklung

Parallelität auf Prozess und Threadebene

- Echte Mehrkern Prozessoren

Jeder Kern ist vollständige CPU und beinhaltet alle zuvor besprochenen Prinzipien

Architektur paralleler Plattformen Teil 1 31.10.12

Page 10: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

II. PARALLELITÄT INNERHALB EINES PROZESSORKERNS

Architektur paralleler Plattformen

Architektur paralleler Plattformen Teil 1 31.10.12

Page 11: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

II. Parallelität innerhalb eines Prozessorkerns

VLIW (very long instruction word) Prozessoren

- statisches Scheduling

- Programmablauf schon vom Compiler festgelegt

- wichtigstes Beispiel: IA64 Archtektur in Itanium Serverprozessoren

Quelle:

http://cdn.slashgear.com/wp-content/uploads/2012/01/intel_itanium_2.jpg

Architektur paralleler Plattformen Teil 1 31.10.12

Page 12: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

II. Parallelität innerhalb eines Prozessorkerns

Superskalare Prozessoren

- mehrere Instruktionen pro Zyklus

- dynamisches Scheduling

- Sicherstellung, dass Instruktionen in der richtigen Reihenfolge fertig werden

Architektur paralleler Plattformen Teil 1 31.10.12

Page 13: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

II. Parallelität innerhalb eines Prozessorkerns

Architektur paralleler Plattformen Teil 1 31.10.12

Quelle: Parallele Programmierung Rauber, Rünger ISBN 978-3-642-13603-0

Page 14: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

KLASSIFIZIERUNG VON PARALLELRECHNERN

Architektur paralleler Plattformen

Architektur paralleler Plattformen Teil 1 31.10.12

Page 15: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

III. Klassifizierung von Parallelrechnern

Allgemeine Definition:

Ein Parallelrechner ist eine Ansammlung von Berechnungseinheiten (Prozessoren), die durch koordinierte Zusammenarbeit große Probleme schnell lösen können

Eine Klassifizierung nach wichtigen Charakteristika:

Flynsche Klassifizierung

Architektur paralleler Plattformen Teil 1 31.10.12

Page 16: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

III. Klassifizierung von Parallelrechnern

SISD (single instruction single data)

- klassischer von Neumann-Rechner

Quelle: Parallele Programmierung Rauber, Rünger ISBN 978-3-642-13603-0

Architektur paralleler Plattformen Teil 1 31.10.12

Page 17: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

III. Klassifizierung von Parallelrechnern

MISD (multiple instruction single data)

Quelle: Parallele Programmierung Rauber, Rünger ISBN 978-3-642-13603-0

Architektur paralleler Plattformen Teil 1 31.10.12

Page 18: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

III. Klassifizierung von Parallelrechnern

SIMD (single instruction multiple data)

Quelle: Parallele Programmierung Rauber, Rünger ISBN 978-3-642-13603-0

Architektur paralleler Plattformen Teil 1 31.10.12

Page 19: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

III. Klassifizierung von Parallelrechnern

MIMD (multiple instruction multiple data)

Quelle: Parallele Programmierung Rauber, Rünger ISBN 978-3-642-13603-0

Architektur paralleler Plattformen Teil 1 31.10.12

Page 20: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

IV. SPEICHERORGANISATION Architektur paralleler Plattformen

Architektur paralleler Plattformen Teil 1 31.10.12

Page 21: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

IV. Speicherorganisation

Architektur paralleler Plattformen Teil 1 31.10.12

Speicherorganisation in Verteilten/Parallelen Systemen

Quelle: http://www.fbi.h-da.de/~a.schuette/Vorlesungen/VerteilteSysteme/Skript/1_Ueberblick/Ueberblick.pdf

Page 22: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

IV. Speicherorganisation

Rechner mit physikalisch verteiltem Speicher(Multicomputersysteme)

-DMM(Distributed Memory Machine)

Architektur paralleler Plattformen Teil 1 31.10.12

Prozessor

IO

Speicher

Verbindungsnetzwerk

Knoten A

Prozessor

IO

Speicher

Knoten B

Page 23: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

IV. Speicherorganisation

Architektur paralleler Plattformen Teil 1 31.10.12

Prozessor

IO

Speicher

Knoten A

Prozessor

IO

Speicher

Knoten B

Sendebefehl

Empfangs- befehl:

Prozessor- Zugriff Speicherort

Kommunikation

Page 24: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

IV. Speicherorganisation

Architektur paralleler Plattformen Teil 1 31.10.12

Architektur verteilter Speicher -Kommunikation Punkt-zu-Punkt Verbindung -Puffer

Quelle: Parallele Programmierung, s.22 Abb. 2.5b Autoren: T. Rauber & G.Rünger

Page 25: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

IV. Speicherorganisation

Architektur verteilter Speicher

-DMA(Direct Memory Access)

-Lange Kommunikationswege

mithilfe von Software

Architektur paralleler Plattformen Teil 1 31.10.12

Quelle: Parallele Programmierung, s.22 Abb. 2.5c Autoren: T. Rauber & G.Rünger

Page 26: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

IV. Speicherorganisation

Architektur verteilter Speicher

-verbesserte Kommunikationszeit

-pro I/O Kanal maximal eine Nachricht

-Pipelining der Nachrichten

-Vermeidung von Deadlocks

Architektur paralleler Plattformen Teil 1 31.10.12

Quelle: Parallele Programmierung, s.22 Abb. 2.5e Autoren: T. Rauber & G.Rünger

Page 27: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

IV. Speicherorganisation

Vor-/Nachteile verteilter Speicher

Vorteile: Nachteile:

-Skalierbarkeit -Latenz

-Kosteneffektivität -Lokalisierung der Daten

-kein Cache Kohärenz

Protokoll

Architektur paralleler Plattformen Teil 1 31.10.12

Page 28: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

IV. Speicherorganisation

Vertreter Multicomputer

-Cluster

-Supercomputer

-Verteilte Anwendungen übers Internet

Architektur paralleler Plattformen Teil 1 31.10.12

Quellen: Bild1: http://serverservice.sytes.net/?tag=mysql-cluster Bild2: http://farm4.static.flickr.com/3367/3615660625_6844933ea1_o.jpg

Page 29: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

IV. Speicherorganisation

Rechner mit physikalische gemeinsamem Speicher

- Globaler/gemeinsamer Speicher

- Load/Store

- Shared Variables

Architektur paralleler Plattformen Teil 1 31.10.12

Gemeinsamer Adressraum

Quelle: Parallele Programmierung, s.25 Abb. 2.6a und b Autoren: T. Rauber & G.Rünger

Page 30: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

IV. Speicherorganisation

Symmetrische Multiprozessoren (SMP)

-Seit 1980

-Symmetrisch

-Zentraler Bus

-CPU Hopping

-virtual shared memory

Architektur paralleler Plattformen Teil 1 31.10.12

Quelle: Parallele Programmierung, s.28 Abb. 2.7a Autoren: T. Rauber & G.Rünger

Page 31: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

IV. Speicherorganisation

Symmetrische Multiprozessoren (SMP)

- UMA (Uniform Memory Access)

- NUMA(Non Uniform Memory Access)

- CC –NUMA (Cache Coherent NUMA)

Architektur paralleler Plattformen Teil 1 31.10.12

Page 32: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

IV. Speicherorganisation

Vor-/Nachteile gemeinsamer Speicher

Vorteile: Nachteile:

-Einfache Programmierung -Keine/schlechte Skalierbarkeit

-Kommunikation -Viele Cpu‘s sind schwierig

zu Implementieren

Architektur paralleler Plattformen Teil 1 31.10.12

Page 33: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

IV. Speicherorganisation

Reduktion von Speicherzugriffzeiten

-Prozessorentwicklung

-Speicherentwicklung

Architektur paralleler Plattformen Teil 1 31.10.12

Quelle: http://www.kreissl.info/ra_04.php

Page 34: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

IV. Speicherorganisation

Caches

-Zwischen Hauptspeicher und CPU

-Probleme bei Parallelität

-l1,l2 und l3 Caches

Architektur paralleler Plattformen Teil 1 31.10.12

Page 35: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

IV. Speicherorganisation

Multithreading

-Virtuelle Prozessoren

-eigener PC und Registersatz pro virtuellem Kern

-Kontextwechsel

-Verzögerungszeit

Architektur paralleler Plattformen Teil 1 31.10.12

Page 36: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

IV. Speicherorganisation

Fine Grained Threading

-Threadwechsel bei jedem

Zyklus

-Nutzt nicht alle Resourcen

Architektur paralleler Plattformen Teil 1 31.10.12

Quelle: http://www.slcentral.com/articles/01/6/multithreading/page7.php

Page 37: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

IV. Speicherorganisation

Coarse Grained Threading

-Wechselt nur bei

Verzögerung

-Keine Verlangsamung des

Threads

Architektur paralleler Plattformen Teil 1 31.10.12

Quelle: http://www.slcentral.com/articles/01/6/multithreading/page6.php

Page 38: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

IV. Speicherorganisation

SMT/Hyperthreading

-“Lücken“ füllen

-Alle Threads

können alle Resourcen

nutzen

- Intel pentium 4 ht, i5-2400, i7 serie

Architektur paralleler Plattformen Teil 1 31.10.12

Quelle: http://www.slcentral.com/articles/01/6/multithreading/page8.php

Page 39: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

IV. Speicherorganisation

Hyperthreading (Intel)

-2 Logische Prozessoren

-Weniger als 5% der

gesamten Chipfläche

-replicated Resources

-partitioned Resources

-shared Resources

Architektur paralleler Plattformen Teil 1 31.10.12

Quelle: http://www.hartware.net/review_266_2.html

Page 40: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

IV. Speicherorganisation

Ablauf:

1.Beide logische Prozessoren sind IDLE

2.Thread 1 starten

3. Thread 2 starten

4.Beide Threads werden beendet bevor neue geladen werden

Architektur paralleler Plattformen Teil 1 31.10.12

Page 41: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

IV. Speicherorganisation

Vor-/Nachteile Hyperthreading

Vorteile: Nachteile:

-Chipfläche -Programmierung

-30% Leistungssteigerung -Verwaltungsaufwand der Kernel

Architektur paralleler Plattformen Teil 1 31.10.12

Page 42: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

V. VERBINDUNGSNETZWERKE Architektur paralleler Plattformen

Architektur paralleler Plattformen Teil 1 31.10.12

Page 43: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

V. Verbindungsnetzwerke

-Kommunikation

-Topologie

-Statische Ver-

bindungsnetzwerke

-Dynamische Ver-

bindungsnetzwerke

-Routingtechnik

Architektur paralleler Plattformen Teil 1 31.10.12

Quelle: http://www.ehrensenf.com/linktipps/schoener-kabelsalat

Page 44: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

V. Verbindungsnetzwerke

Bewertungskriterien für statische Netzwerke

-Durchmesser

-Grad

-Bisektionsbandbreite

-Knoten- und Kantenkonnektivität

-Einbettung in andere Netzwerke

Architektur paralleler Plattformen Teil 1 31.10.12

Page 45: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

V. Verbindungsnetzwerke

Durchmesser

Architektur paralleler Plattformen Teil 1 31.10.12

Page 46: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

V. Verbindungsnetzwerke

Durchmesser Beispiel

Architektur paralleler Plattformen Teil 1 31.10.12

1 2 3

4 5 6

7 8 9

δ= δ(u,v) = 4

Page 47: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

V. Verbindungsnetzwerke

Grad

Architektur paralleler Plattformen Teil 1 31.10.12

Page 48: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

V. Verbindungsnetzwerke

Grad Beispiel:

Architektur paralleler Plattformen Teil 1 31.10.12

1 2 3

4 5 6

7 8 9

g(G)=4

Page 49: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

V. Verbindungsnetzwerke

Bisektionsbandbreite

Architektur paralleler Plattformen Teil 1 31.10.12

Page 50: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

V. Verbindungsnetzwerke

Bisektionsbandbreite Beispiel

Architektur paralleler Plattformen Teil 1 31.10.12

1 2 3

4 5 6

7 8 9

1 2

3

4

5 6

7

8 9

B(G)= 4

Page 51: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

V. Verbindungsnetzwerke

Knotenkonnektivität

Architektur paralleler Plattformen Teil 1 31.10.12

Page 52: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

V. Verbindungsnetzwerke

Knotenkonnektivität Beispiel

Architektur paralleler Plattformen Teil 1 31.10.12

1 2 3

4 5 6

7 8 9

1 2 3

5 6

7 9

nc(G)=2

Page 53: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

V. Verbindungsnetzwerke

Kantenkonnektivität

Architektur paralleler Plattformen Teil 1 31.10.12

Page 54: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

Kantenkonnektivität Beispiel

Architektur paralleler Plattformen Teil 1 31.10.12

1 2 3

4 5 6

7 8 9

1 2 3

4 5 6

7 8 9

Page 55: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

V. Verbindungsnetzwerke

Anforderungen:

-kleiner Durchmesser

-geringer Grad

-hohe Bisektionsbandbreite

-hohe Konnektivität

-Einbettung

-Skalierbarkeit

Architektur paralleler Plattformen Teil 1 31.10.12

Page 56: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

V. Verbindungsnetzwerke

Vollständiger Graph

Grad: n-1

Durchmesser: 1

Kantenkonnektivität: n-1

Bisektionsbandbreite: (n/2)²S

Architektur paralleler Plattformen Teil 1 31.10.12

Quelle: Parallele Programmierung, s.38 Abb. 2.9a Autoren: T. Rauber & G.Rünger

Page 57: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

V. Verbindungsnetzwerke

Lineares Feld

Grad: 2

Durchmesser: n-1

Kantenkonnektivität: 1

Bisektionsbandbreite: 1

Architektur paralleler Plattformen Teil 1 31.10.12

Quelle: Parallele Programmierung, s.38 Abb. 2.9b Autoren: T. Rauber & G.Rünger

Page 58: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

V. Verbindungsnetzwerke

Ring

Grad: 2

Durchmesser:

Kantenkonnektivität: 2

Bisektionsbandbreite: 2

Architektur paralleler Plattformen Teil 1 31.10.12

Quelle: Parallele Programmierung, s.38 Abb. 2.9c Autoren: T. Rauber & G.Rünger

Page 59: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

V. Verbindungsnetzwerke

d-dimensionaler Gitter

Grad: 2d

Durchmesser:

Kantenkonnektivität: d

Bisektionsbandbreite:

Architektur paralleler Plattformen Teil 1 31.10.12

Quelle: Parallele Programmierung, s.38 Abb. 2.9d Autoren: T. Rauber & G.Rünger

Page 60: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

V. Verbindungsnetzwerke

d-dimensionaler Torus

Grad: 2d

Durchmesser:

Kantenkonnektivität: 2d

Bisektionsbandbreite:

Architektur paralleler Plattformen Teil 1 31.10.12

Quelle: Parallele Programmierung, s.38 Abb. 2.9e Autoren: T. Rauber & G.Rünger

Page 61: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

V. Verbindungsnetzwerke

k-dimensionaler Hyperwürfel

Grad: log n

Durchmesser: log n

Kantenkonnektivität: log n

Bisektionsbandbreite: n/2

Hamming Distanz

Architektur paralleler Plattformen Teil 1 31.10.12

Quelle: Parallele Programmierung, s.38 Abb. 2.9f Autoren: T. Rauber & G.Rünger

Page 62: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

V. Verbindungsnetzwerke

k-dimensionales CCC-Netzwerk

Grad: 3

Durchmesser:

Kantenkonnektivität: 3

Bisektionsbandbreite:

Architektur paralleler Plattformen Teil 1 31.10.12

Quelle: Parallele Programmierung, s.38 Abb. 2.9ag Autoren: T. Rauber & G.Rünger

Page 63: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

V. Verbindungsnetzwerke

Vollständiger binärer Baum

Grad: 3

Durchmesser:

Kantenkonnektivität: 1

Bisektionsbandbreite: 1

Architektur paralleler Plattformen Teil 1 31.10.12

Quelle: Parallele Programmierung, s.38 Abb. 2.9h Autoren: T. Rauber & G.Rünger

Page 64: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

V. Verbindungsnetzwerke

K-Computer

-Platz 2 Top 500(10,51 pf)

-88.162 Cpu in 672 Schränken

-Im November 2012 864

Schränke

-Zeichnet sich besonders duch sein 6D Mesh/Torus

Verbindungsnetzwerk aus

Architektur paralleler Plattformen Teil 1 31.10.12

Quelle: http://www.n-tv.de/technik/Japan-hat-schnellsten-Rechner-article3619016.html

Page 65: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

V. Verbindungsnetzwerke

K-Computer Video:

http://www.fujitsu.com/global/about/tech/k/whatis/network/

Architektur paralleler Plattformen Teil 1 31.10.12

Quelle: http://www.fujitsu.com/downloads/TC/sc10/interconnect-of-k-computer.pdf

Page 66: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

V. Verbindungsnetzwerke

Einbettung

- Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die Knoten eines Zielnetzwerkes mit einer anderen Topologie

- Ausdehnung (oder Streckungsgrad) ist ein Maß für die Güte der Einbettung

Ausdehnung 1 = perfekt

Architektur paralleler Plattformen Teil 1 31.10.12

Page 67: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

V. Verbindungsnetzwerke

Beispiel 1: Einbettung eines Rings in einen k-dimensionalen Würfel

- Methode:

Gespiegelter Gray-Code (RGC)

rekursive Definition:

Der k-bit Gray-Code wird aus dem (k-1)-Bit Gray-Code RGC(k-1) = (b1, …, bm) mit m= 2^k-1 konstruiert. Zur Konstruktion von RGC(k) wird RGC(k-1) dupliziert, vor jedes binäre Wort des Originals wird eine Null und vor jedes binäre Wort des Duplikats wird eine 1 gesetzt. Resultierende Folgen sind (0b1, …, 0bm) und (1b1, …, 1bm)

RGC(k) resultiert durch Umkehrung der zweiten Folge und Konkatenation.

Architektur paralleler Plattformen Teil 1 31.10.12

Page 68: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

V. Verbindungsnetzwerke

Beispiel 1: Einbettung eines Rings in einen k-dimensionalen Würfel

Architektur paralleler Plattformen Teil 1 31.10.12

Page 69: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

V. Verbindungsnetzwerke

Beispiel 2: 2-dimensionales Gitter in k-dimensionales Würfel

- Verallgemeinerung der vorherigen Einbettung

- Bildung von zwei Gray-Codes

- Damit Erstellung einer Matrix

Quelle: Parallele Programmierung Rauber, Rünger ISBN 978-3-642-13603-0

Architektur paralleler Plattformen Teil 1 31.10.12

Page 70: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

V. Verbindungsnetzwerke

Dynamische Verbindungsnetzwerke

- Kompenenten sind an Eingangs-/Ausgansport des Netzwerkes angeschlossen

- keine direkten Punkt zu Punkt Verbindungen

- nach Bedarf werden von aktiven Komponenten Verbindungen hergestellt

Architektur paralleler Plattformen Teil 1 31.10.12

Page 71: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

V. Verbindungsnetzwerke

Dynamische Verbindungsnetzwerke

Busnetzwerke

- in jedem Computer zu finden

- Bus besteht meistens aus sehr vielen Leitung um große Datenmengen zu transportieren

- immer nur ein Datentransport gleichzeitig

Quelle: Parallele Programmierung Rauber, Rünger ISBN 978-3-642-13603-0

Architektur paralleler Plattformen Teil 1 31.10.12

Page 72: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

V. Verbindungsnetzwerke

Dynamische Verbindungsnetzwerke

Crossbar-Netzwerke

- Verbindungen durch Schalter

- sehr aufwendig

Quelle:

http://en.wikipedia.org/wiki/File:Crossbar-hy1.jpg

Architektur paralleler Plattformen Teil 1 31.10.12

Page 73: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

V. Verbindungsnetzwerke

Dynamische Verbindungsnetzwerke

Mehrstufige Schaltnetzwerke

- aufgebaut aus mehreren Schichten aus Schaltern

- Ziel ist geringerer tatsächlicher Abstand zwischen Prozessoren als bei direkten Verbindungsnetzwerken

Quelle:Parallele

Programmierung Rauber,

Rünger ISBN 978-3-642-13603-0

Architektur paralleler Plattformen Teil 1 31.10.12

Page 74: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

V. Verbindungsnetzwerke

Dynamische Verbindungsnetzwerke

16x16 Omega Netzwerk 16x16 Butterfly Netzwerk

Quelle: Parallele Programmierung Rauber, Rünger ISBN 978-3-642-13603-0

Architektur paralleler Plattformen Teil 1 31.10.12

Page 75: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

V. Verbindungsnetzwerke

Dynamische Verbindungsnetzwerke

IBM RP3

Quelle: http://www.sciencephoto.com/image/349994/530wm/T4500119-IBM_scientist_stands_by_RP3_parallel_processor-SPL.jpg

Architektur paralleler Plattformen Teil 1 31.10.12

Page 76: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

V. Verbindungsnetzwerke

Dynamische Verbindungsnetzwerke

16x16 Baseline Fattree für 16 Prozessoren

Quelle: Parallele Programmierung Rauber, Rünger ISBN 978-3-642-13603-0

Architektur paralleler Plattformen Teil 1 31.10.12

Page 77: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

V. Verbindungsnetzwerke

Dynamische Verbindungsnetzwerke

3 dimensionales Benes-Netzwerk

Quelle: Parallele Programmierung Rauber, Rünger ISBN 978-3-642-13603-0

Architektur paralleler Plattformen Teil 1 31.10.12

Page 78: Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke Einbettung - Einbettung ist eine Abbildung der Knoten eines Verbindungsnetzwerkes auf die

Architektur paralleler Plattformen Teil 1 31.10.12

Vielen Dank!