Upload
alke-mylin
View
109
Download
0
Embed Size (px)
Citation preview
Christoph Kessler, IDA, Linköpings universitet, 2006.
Feb. 2006
Sprachentwurf und Compiler-Techniken zur explizit-parallelen Programmierung
nach dem BSP-Modell
Motivation Aktuelle Projekte BSP-Modell und NestStep Übersetzung, Laufzeitsystem Optimierung der Array-Kommunikation
Motivation Aktuelle Projekte BSP-Modell und NestStep Übersetzung, Laufzeitsystem Optimierung der Array-Kommunikation
Christoph Kessler
Universität Linköping, Schweden
2 Feb. 2006C. Kessler, IDA, Linköpings universitet.
Motivation (1)
Moore’s ”Gesetz” seit 1965:
Verdopplung #Transistoren per Chipfläche alle 2 Jahre
Bis ca. 2003 auch Verdopplung der Taktrate alle 2 Jahre, dann
Latenz, Stromverbrauch, Abwärme ...
Weiterer Durchsatz-Anstieg nur durch Parallelität möglich
SMT, Multi-Core, CMP, NoC, PIM, SIMD, GPU, Cluster ...
1
10
100
1000
10000
1978 1980 1982 1984 1986 1988 1990 1992 1994 1996 1998 2000 2002 2004 2006
Per
form
ance
(vs
. VA
X-1
1/78
0)
25%/year
52%/year
20%/year
Quelle: David Patterson
Leistung per Einzelprozessor
Single-processor Performance Scaling
0.0
2.0
4.0
6.0
8.0
10.0
12.0
14.0
16.0
Log
2 S
peed
up
Limit: Taktrate
Limit: RISC ILP
Durchsatzanstieg 55%/Jahr
65 nm45 nm 32nm 22nm90 nm
Pipelining
RISC/CISC CPI
Schaltgeschwindigkeit
Parallelität
Annahme: Anstieg17%/Jahr möglich
Quelle: Doug Burger, UT Austin, 2005
2006
3 Feb. 2006C. Kessler, IDA, Linköpings universitet.
Motivation (2)
50+ Jahre von-Neumann-Programmierung ...
Sequentieller Instruktionsstrom
Immer komplexere und anspruchsvollere Anwendungen
Seit 80’er J.: Von-Neumann-Modell auf paralleler Architektur emuliert
Pipelining
Superskalartechnologie
Codeerzeugung für VLIW / EPIC / MMX / DSP / ...
Spekulative Ausführung
Flaschenhals für Systemleistung
Komplexität, Energieverbrauch, Speicherzugriffslatenz,
Kontrollfluss, begrenzte Parallelität auf Anweisungsebene
... vor dem Paradigmenwechsel hin zu expliziter Parallelität
4 Feb. 2006C. Kessler, IDA, Linköpings universitet.
Parallele Programmierung – aber wie?
Gut entwickelte Theorie
Berechnungsmodelle: CSP, PRAM, BSP, LogP, systolische Arrays
Sprachen: implizit: funktional / single-assignment / dataflow, explizit: strukturierter Parallelismus (skeletons), Fork, ...
Algorithmen, Datenstrukturen, Routing, Scheduling, Lastbalancierung ...
Automatische Parallelisierung
In der Praxis ... ?
Supercomputing:
Modelle: message passing, threads
Sprachen: Fortran, C / C++ mit MPI, OpenMP, pthreads, parallele Bibliotheken
Spezialprozessoren: DSP, rekonfigurierbar/FPGA, MPSoC
Modelle/Sprachen: C / asm; proprietär; diverse Hardware-C
Desktop / Server: nebenläufige, meist sequentielle Prozesse
5 Feb. 2006C. Kessler, IDA, Linköpings universitet.
Aktuelle Projekte
Parallelität auf drei Ebenen...
Parallelität auf Anweisungsebene
OPTIMIST – Integrierte Codeerzeugung für VLIW und DSP
Software Pipelining
Parallelisierungsmethoden
Komposition paralleler Programme
Invasive interaktive Parallelisierung mit AOP
Entwurf und Implementierung paralleler Programmiersprachen
NestStep
TI C6201
6 Feb. 2006C. Kessler, IDA, Linköpings universitet.
NestStep: BSP-Modell + ...
BSP-Modell (Bulk-Synchronous Parallelism) [Valiant 1990]
BSP-Rechner: abstrakter MIMD-Parallelrechner (p, L, g) Gruppe von p Prozessoren / threads (SPMD) Nachrichtenaustausch (message passing) Barrierensynchronisation, Overhead: L Kommunikations-Datenrate: g
BSP-Programm: Folge von Superschritten t (prog) = step t (step)
Superschritt: Max. Berechnungszeit per Prozessor: w Max. Kommunikationsvolumen per Prozessor: h t (step) = w + h g + L
w
7 Feb. 2006C. Kessler, IDA, Linköpings universitet.
NestStep: step statement
Gemeinsame (shared) Variablen in NestStep: sh int x;
...step { ... = ... x ... ... x = ...}
Invarianten: Superstep-Synchronität:
Alle Prozessoren einer (aktiven) Gruppe befinden sich zur selben Zeit im selben Superschritt.
Superstep-Speicherkonsistenz: Bei Eintritt und nach Austritt aus einem Superschritt haben Kopien
gemeinsamer Variablen auf allen Prozessoren den gleichen Wert. Innerhalb eines Superschritts ist nur der lokale Wert sichtbar.
8 Feb. 2006C. Kessler, IDA, Linköpings universitet.
Programmierbares ”Konsistent-machen”
Concurrent-Write Konfliktlösungs-Strategie mitdeklarieren, z.B.:
sh<0> type x;
sh<=> type x;
sh<?> type x; // default
sh<+> aritype x; // globale Summe etc.
sh<foo> type x; // benutzerdefinierte Strategie
sh<+:k> aritype sum; // Präfixsumme etc. als Seiteneffekt
oder lokal bestimmen:sh double maxerr;...step { ... maxerr = local_error(...);} combine ( maxerr<max> );... = ... maxerr ...;
9 Feb. 2006C. Kessler, IDA, Linköpings universitet.
Spannbaum über alle Prozessoren der Gruppe
2 Phasen: ”combine” – Kommunikation aufwärts ”commit” – Kommunikation abwärts
Barrierensynchronisation inklusive Binomialbäume besser als d-när-Bäume [Sohl’06]
Implementierung im Laufzeitsystem
10 Feb. 2006C. Kessler, IDA, Linköpings universitet.
prefixi = j=0 aj
for i = 0,...,N-1
Beispiel: Parallele Präfixsummen
i-1
Beispiel: a = { 1, 3, 1, 4 }
prefix = { 0, 1, 4, 5 }, sum = 9
// Sequentiell in Linearzeit:
sum = 0;
for i = 0, N-1 {
prefix[i] = sum;
sum += a[i];
}
11 Feb. 2006C. Kessler, IDA, Linköpings universitet.
prefixi = j=0 aj
for i = 0,...,N-1
Beispiel: Parallele Präfixsummen
void parprefix( sh int a[]</> ){ int *pre; // private prefix array
int myoffset; // prefix offset for this processor
sh int sum=0; // constant initializer
int i, j = 0;
step {
pre = new_Array( localsizeof(a), Type_int );
forall ( i, a ) { // locally counts upward
pre[j++] = sum;
sum += a[i]; }
} combine( sum<+:myoffset> );
j = 0; step
forall ( i, a )
a[i] = pre[j++] + myoffset;}
i-1
a:
P0 P1
P0: sum: P1: sum:
P0: pre P1: pre
a:
myoffset: myoffset:
sum: sum:
12 Feb. 2006C. Kessler, IDA, Linköpings universitet.
Parallele Präfixsummen
Xeon cluster Monolith, NSC Linköping
13 Feb. 2006C. Kessler, IDA, Linköpings universitet.
Mehrstufiger Parallelismus
Eriksson, K., Chalabine: Lokale Lastbalancierung in irregulären parallelen Divide-and-Conquer-Berechnungen. PASA-2006
Parallelität-erzeugende Konstrukte können verschachtelt sein:
Statisch: z.B. parallele Schleifen
Dynamisch: Parallele Divide-and-Conquer-Berechnungen
erzeugen massive Parallelität
In NestStep: Gruppe teilen(= forke parallelen Prozess)
neststep( 2, @=... ) {
..... if (@==0) foo(); else bar(); .....}
15 Feb. 2006C. Kessler, IDA, Linköpings universitet.
GridNestStep
Grid-Programmierung
Bislang nur für sehr einfache Parallelisierungsstrategien
Grid-Middleware: Nur einfachster Nachrichtenaustausch
BSP-Modell!
Nutze Unabhängigkeitder Berechnungen innerhalb einesSuperschritts
Scheduling
FehlertoleranzMattsson, K.: Towards a Bulk-Synchronous Distributed Shared Memory Programming Environment for Grids. Proc. PARA’04, 2005.
16 Feb. 2006C. Kessler, IDA, Linköpings universitet.
Verteilte gemeinsame Arrays
Datenaufteilung über deklarierende Prozessorgruppeist Bestandteil des Array-Typs
sh int a[4]; // repliziert über Gruppe
sh int b[7]</>; // blockweise aufgeteilt
sh int c[7]<%>; // zyklisch aufgeteilt
sh int d[5][4]<%>[7]; // aufgeteilt in 2 Dim.
21 30 21 30
21 30 654
42 60 531
localsize(c)
P0 P1
17 Feb. 2006C. Kessler, IDA, Linköpings universitet.
Optimierung von Array-Zugriffen
Kommunikationslatenz viele Einzelzugriffe ineffizient
Prefetching von Array-Bereichen bei Superstep-Beginn
Schreiben von Array-Bereichen bei Superstep-Ende
Problem: Irreguläre Anwendungen – zugegriffene Array-Bereiche nicht statisch bekannt
Berechne Kommunikations-Schedule zur Laufzeit
nutze combine/commit-Mechanismus für replizierte gemeinsame Variablen
Zweiseitige Kommunikation genügt
K., Managing distributed shared arrays in a BSP environment. In Concurrency and Computation: Practice and Experience, 2004.
18 Feb. 2006C. Kessler, IDA, Linköpings universitet.
Gauss-Elimination
Xeon cluster Monolith, NSC Linköping
Matrix 4000x4000 doubles,spaltenweise zyklisch verteilt.
19 Feb. 2006C. Kessler, IDA, Linköpings universitet.
Zusammenfassung
Kommender Paradigmenwechsel hin zu expliziter Parallelität
Erleichtert durch einfache Programmiermodelle, z.B. BSP
NestStep Gemeinsamer Adressraum Klare Synchronisationsstruktur Einfaches Speicherkonsistenzmodell Determinismus Flexibilität durch Gruppenkonzept Erweiterung existierender Programmiersprachen
z.B. Java, C Stand der Implementierung:
Laufzeitsystem (C/MPI, v.2) fertig [Sohl’06] Frontend: noch in Arbeit...
20 Feb. 2006C. Kessler, IDA, Linköpings universitet.
Ausblick
Weitere Zielplattformen: CMP, Constellation, Grid
Entwurfsmuster für die BSP-Programmierung
BSP-Komponentensysteme
Parallele Schnittstellen
Metadaten z.B. Parameter w, h; P, g, L
Modellierung von BSP-Programmen
UML-Erweiterung für BSP-Programme
Plattformunabhängigkeit (z.B. Basissprache)
Modellgetriebene Entwicklung z.B. plattformspezifische Optimierungen
Komposition von BSP-Programmen
Einweben von Parallelisierungs-Aspekten in seq. Code