19
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 Christoph Kessler Universität Linköping, Schweden

Christoph Kessler, IDA, Linköpings universitet, 2006. Feb. 2006 Sprachentwurf und Compiler-Techniken zur explizit-parallelen Programmierung nach dem BSP-Modell

Embed Size (px)

Citation preview

Page 1: Christoph Kessler, IDA, Linköpings universitet, 2006. Feb. 2006 Sprachentwurf und Compiler-Techniken zur explizit-parallelen Programmierung nach dem BSP-Modell

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

Page 2: Christoph Kessler, IDA, Linköpings universitet, 2006. Feb. 2006 Sprachentwurf und Compiler-Techniken zur explizit-parallelen Programmierung nach dem BSP-Modell

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

Page 3: Christoph Kessler, IDA, Linköpings universitet, 2006. Feb. 2006 Sprachentwurf und Compiler-Techniken zur explizit-parallelen Programmierung nach dem BSP-Modell

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

Page 4: Christoph Kessler, IDA, Linköpings universitet, 2006. Feb. 2006 Sprachentwurf und Compiler-Techniken zur explizit-parallelen Programmierung nach dem BSP-Modell

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

Page 5: Christoph Kessler, IDA, Linköpings universitet, 2006. Feb. 2006 Sprachentwurf und Compiler-Techniken zur explizit-parallelen Programmierung nach dem BSP-Modell

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

Page 6: Christoph Kessler, IDA, Linköpings universitet, 2006. Feb. 2006 Sprachentwurf und Compiler-Techniken zur explizit-parallelen Programmierung nach dem BSP-Modell

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

Page 7: Christoph Kessler, IDA, Linköpings universitet, 2006. Feb. 2006 Sprachentwurf und Compiler-Techniken zur explizit-parallelen Programmierung nach dem BSP-Modell

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.

Page 8: Christoph Kessler, IDA, Linköpings universitet, 2006. Feb. 2006 Sprachentwurf und Compiler-Techniken zur explizit-parallelen Programmierung nach dem BSP-Modell

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 ...;

Page 9: Christoph Kessler, IDA, Linköpings universitet, 2006. Feb. 2006 Sprachentwurf und Compiler-Techniken zur explizit-parallelen Programmierung nach dem BSP-Modell

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

Page 10: Christoph Kessler, IDA, Linköpings universitet, 2006. Feb. 2006 Sprachentwurf und Compiler-Techniken zur explizit-parallelen Programmierung nach dem BSP-Modell

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];

}

Page 11: Christoph Kessler, IDA, Linköpings universitet, 2006. Feb. 2006 Sprachentwurf und Compiler-Techniken zur explizit-parallelen Programmierung nach dem BSP-Modell

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:

Page 12: Christoph Kessler, IDA, Linköpings universitet, 2006. Feb. 2006 Sprachentwurf und Compiler-Techniken zur explizit-parallelen Programmierung nach dem BSP-Modell

12 Feb. 2006C. Kessler, IDA, Linköpings universitet.

Parallele Präfixsummen

Xeon cluster Monolith, NSC Linköping

Page 13: Christoph Kessler, IDA, Linköpings universitet, 2006. Feb. 2006 Sprachentwurf und Compiler-Techniken zur explizit-parallelen Programmierung nach dem BSP-Modell

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(); .....}

Page 14: Christoph Kessler, IDA, Linköpings universitet, 2006. Feb. 2006 Sprachentwurf und Compiler-Techniken zur explizit-parallelen Programmierung nach dem BSP-Modell

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.

Page 15: Christoph Kessler, IDA, Linköpings universitet, 2006. Feb. 2006 Sprachentwurf und Compiler-Techniken zur explizit-parallelen Programmierung nach dem BSP-Modell

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

Page 16: Christoph Kessler, IDA, Linköpings universitet, 2006. Feb. 2006 Sprachentwurf und Compiler-Techniken zur explizit-parallelen Programmierung nach dem BSP-Modell

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.

Page 17: Christoph Kessler, IDA, Linköpings universitet, 2006. Feb. 2006 Sprachentwurf und Compiler-Techniken zur explizit-parallelen Programmierung nach dem BSP-Modell

18 Feb. 2006C. Kessler, IDA, Linköpings universitet.

Gauss-Elimination

Xeon cluster Monolith, NSC Linköping

Matrix 4000x4000 doubles,spaltenweise zyklisch verteilt.

Page 18: Christoph Kessler, IDA, Linköpings universitet, 2006. Feb. 2006 Sprachentwurf und Compiler-Techniken zur explizit-parallelen Programmierung nach dem BSP-Modell

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...

Page 19: Christoph Kessler, IDA, Linköpings universitet, 2006. Feb. 2006 Sprachentwurf und Compiler-Techniken zur explizit-parallelen Programmierung nach dem BSP-Modell

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