Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke...

Architektur paralleler Plattformen

Freie Universität Berlin

Fachbereich Informatik

Wintersemester 2012/2013

Proseminar Parallele Programmierung

Mirco Semper, Marco Gester

Datum: 31.10.12

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

I. ÜBERBLICK PROZESSORENTWICKLUNG

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

- 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

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

Parallelität durch Pipelining

- Aufteilung der Verarbeitung einer Instruktion in verschiedene Teile

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

Parallelität durch mehrere Funktionseinheiten

- Es werden mehrere ALUs, FPUs und andere verbaut

- Entwicklung sind Grenzen gesetzt, da hoher Scheduling Aufwand

Parallelität auf Prozess und Threadebene

- Echte Mehrkern Prozessoren

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

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

Superskalare Prozessoren

- mehrere Instruktionen pro Zyklus

- dynamisches Scheduling

- Sicherstellung, dass Instruktionen in der richtigen Reihenfolge fertig werden

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

SISD (single instruction single data)

- klassischer von Neumann-Rechner

MISD (multiple instruction single data)

SIMD (single instruction multiple data)

MIMD (multiple instruction multiple data)

IV. SPEICHERORGANISATION Architektur paralleler Plattformen

Speicherorganisation in Verteilten/Parallelen Systemen

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

Rechner mit physikalisch verteiltem Speicher(Multicomputersysteme)

-DMM(Distributed Memory Machine)

Prozessor

Speicher

Verbindungsnetzwerk

Knoten A

Prozessor

Speicher

Knoten B

Prozessor

Speicher

Knoten A

Prozessor

Speicher

Knoten B

Sendebefehl

Empfangs- befehl:

Prozessor- Zugriff Speicherort

Kommunikation

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

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

Architektur verteilter Speicher

-DMA(Direct Memory Access)

-Lange Kommunikationswege

mithilfe von Software

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

Architektur verteilter Speicher

-verbesserte Kommunikationszeit

-pro I/O Kanal maximal eine Nachricht

-Pipelining der Nachrichten

-Vermeidung von Deadlocks

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

Vor-/Nachteile verteilter Speicher

Vorteile: Nachteile:

-Skalierbarkeit -Latenz

-Kosteneffektivität -Lokalisierung der Daten

-kein Cache Kohärenz

Protokoll

Vertreter Multicomputer

-Cluster

-Supercomputer

-Verteilte Anwendungen übers Internet

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

Rechner mit physikalische gemeinsamem Speicher

- Globaler/gemeinsamer Speicher

- Load/Store

- Shared Variables

Gemeinsamer Adressraum

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

Symmetrische Multiprozessoren (SMP)

-Seit 1980

-Symmetrisch

-Zentraler Bus

-CPU Hopping

-virtual shared memory

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

Symmetrische Multiprozessoren (SMP)

- UMA (Uniform Memory Access)

- NUMA(Non Uniform Memory Access)

- CC –NUMA (Cache Coherent NUMA)

Vor-/Nachteile gemeinsamer Speicher

-Einfache Programmierung -Keine/schlechte Skalierbarkeit

-Kommunikation -Viele Cpu‘s sind schwierig

zu Implementieren

Reduktion von Speicherzugriffzeiten

-Prozessorentwicklung

-Speicherentwicklung

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

Caches

-Zwischen Hauptspeicher und CPU

-Probleme bei Parallelität

-l1,l2 und l3 Caches

Multithreading

-Virtuelle Prozessoren

-eigener PC und Registersatz pro virtuellem Kern

-Kontextwechsel

-Verzögerungszeit

Fine Grained Threading

-Threadwechsel bei jedem

Zyklus

-Nutzt nicht alle Resourcen

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

Coarse Grained Threading

-Wechselt nur bei

Verzögerung

-Keine Verlangsamung des

Threads

SMT/Hyperthreading

-“Lücken“ füllen

-Alle Threads

können alle Resourcen

nutzen

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

Hyperthreading (Intel)

-2 Logische Prozessoren

-Weniger als 5% der

gesamten Chipfläche

-replicated Resources

-partitioned Resources

-shared Resources

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

Ablauf:

1.Beide logische Prozessoren sind IDLE

2.Thread 1 starten

3. Thread 2 starten

4.Beide Threads werden beendet bevor neue geladen werden

Vor-/Nachteile Hyperthreading

-Chipfläche -Programmierung

-30% Leistungssteigerung -Verwaltungsaufwand der Kernel

V. VERBINDUNGSNETZWERKE Architektur paralleler Plattformen

-Kommunikation

-Topologie

-Statische Ver-

bindungsnetzwerke

-Dynamische Ver-

bindungsnetzwerke

-Routingtechnik

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

Bewertungskriterien für statische Netzwerke

-Durchmesser

-Bisektionsbandbreite

-Knoten- und Kantenkonnektivität

-Einbettung in andere Netzwerke

Durchmesser

Durchmesser Beispiel

δ= δ(u,v) = 4

Grad Beispiel:

g(G)=4

Bisektionsbandbreite

Bisektionsbandbreite Beispiel

B(G)= 4

Knotenkonnektivität

Knotenkonnektivität Beispiel

nc(G)=2

Kantenkonnektivität

Kantenkonnektivität Beispiel

Anforderungen:

-kleiner Durchmesser

-geringer Grad

-hohe Bisektionsbandbreite

-hohe Konnektivität

-Einbettung

-Skalierbarkeit

Vollständiger Graph

Grad: n-1

Durchmesser: 1

Kantenkonnektivität: n-1

Bisektionsbandbreite: (n/2)²S

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

Lineares Feld

Grad: 2

Durchmesser: n-1

Kantenkonnektivität: 1

Bisektionsbandbreite: 1

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

Grad: 2

Durchmesser:

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

d-dimensionaler Gitter

Grad: 2d

Durchmesser:

Kantenkonnektivität: d

Bisektionsbandbreite:

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

d-dimensionaler Torus

Grad: 2d

Durchmesser:

Kantenkonnektivität: 2d

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

k-dimensionaler Hyperwürfel

Grad: log n

Durchmesser: log n

Kantenkonnektivität: log n

Bisektionsbandbreite: n/2

Hamming Distanz

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

k-dimensionales CCC-Netzwerk

Grad: 3

Durchmesser:

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

Vollständiger binärer Baum

Grad: 3

Durchmesser:

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

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

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

K-Computer Video:

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

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

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

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.

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

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

- Verallgemeinerung der vorherigen Einbettung

- Bildung von zwei Gray-Codes

- Damit Erstellung einer Matrix

Dynamische Verbindungsnetzwerke

- Kompenenten sind an Eingangs-/Ausgansport des Netzwerkes angeschlossen

- keine direkten Punkt zu Punkt Verbindungen

- nach Bedarf werden von aktiven Komponenten Verbindungen hergestellt

Busnetzwerke

- in jedem Computer zu finden

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

- immer nur ein Datentransport gleichzeitig

Crossbar-Netzwerke

- Verbindungen durch Schalter

- sehr aufwendig

Quelle:

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

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

16x16 Omega Netzwerk 16x16 Butterfly Netzwerk

IBM RP3

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

16x16 Baseline Fattree für 16 Prozessoren

3 dimensionales Benes-Netzwerk

Vielen Dank!

Architektur paralleler Plattformen - Informatik · computer.pdf . V. Verbindungsnetzwerke...

Documents

Paradigmen der Programmierung Nebenläufigkeit Prof. Dr. Christian Kohls Informatik, Soziotechnische Systeme 3. Synchronisation sequentieller und paralleler

DOM und XPath 05 - · –Knoten im Baum, der einem Element entspricht. •Text-Knoten –entspricht dem Text in einem XML-Baum •Attribut-Knoten –repräsentiert ein Attribut 48

Teil 2 Knoten für Wirbel und Ösen - Angelmontagen · Einer der bekanntesten Knoten um Schnur an einem Öhr (Haken, Wirbel, Kunstköder etc.) zu binden, ist der Clinch-Knoten. Der

Teil 1 Schnurverbindungsknoten (Schnur an Schnur) · PDF fileAlbright-Knoten Der „Albright-Knoten“ ist einer der haltbarsten Knoten für die Verbindung unterschiedlich dicker Schnüre

14 Parallele Rechner 14.1 Parallele Rechner - Einführung 14.2 Leistung 14.3 Kommuniklationsarchitektur 14.4 Typen paralleler Architekturen

GENE Ein massiv paralleler Code zur Berechnung von turbulenten Str ömungen in Fusionsplasmen

Praxisbericht Knoten- und Kanten ModellH_Praxisbericht_KnotenKanten.pdf · Einleitung Anforderung, Projekt HL Knoten und Kanten Modell Straßennetz, Definitionen, Verwendung Projektbearbeitung

Leinen und Knoten Erstellt von: Billert Karsten1 Jugendfeuerwehr Homburg-Mitte Ausbildung Leinen und Knoten

REVITALISIERUNG DES EHEMALIGEN REICHSBAHN- …gku-gmbh.com/files/2010_Dresden_Revitalisierung_Zernsdorf.pdf · übersichtliche Struktur für die Integration paralleler Planungsabläufe

Umbau Knoten Riesa

2 Baum Wurzel Knoten ohne Vorgänger Knoten beinhalten Daten z.B. Zahlen Innerer Knoten Kein Blatt Blatt Knoten ohne Nachfolger Ast Kante

Löschgruppe Bernberg Ausbildung Warum Feuerwehrknoten? Eine Seilkonstruktion reißt immer zuerst im Knoten, weil im Knoten das Seil in seinem Querschnitt

„KNOTEN TABOR / POSTHOF“

Herz - univie.ac.atbiologische-physik.univie.ac.at/lva/bioelektrische... · Sunus-knoten Atrio-ventriku-lar-knoten Vorhofmyokard Kammermyokard Bioelektr5 2 Ruhepotential der Zellen

67 Grundkonzepte paralleler Programmierung => MPD (Multi-threaded Parallel Distributed) Andrews (Arizona University)

Knoten am Hals

Die wichtigsten Knoten - BLINKER · Die wichtigsten Knoten für Angler Knoten für Öhr- und Plättchenhaken, für Wirbel und Kunstköder, zum Verbinden zweier Schnüre, für Schlaufen,

Bestimmung der Verkehrsqualität bei Knoten - … · 2018-02-13 · Bestimmung Verkehrsqualität bei Knoten (Stauverdachtsstellen): Arbeitsanweisung Tiefbauamt Kanton Basel-Landschaft

Mai 2014 MIPA – Einbettung des Mobilitätsmanagements

SITOR - Sicherungseinsätze in paralleler Anordnung / SITOR ... · SITOR - Sicherungseinsätze in paralleler Anordnung SITOR - Fuse-links in a parallel adjustment Cartouches fusibles