eSkel – edinburgh Skeleton libraryParallele Programmierung mit Skeletten

SeminararbeitIngo DyrbuschMai 2007

2

Skelett-Programmierung

Inhalt Grundlagen

Was ist ein Skelett? Ziele von eSkel Daten- vs. Funktionale Parallelität

Basiselemente von eSkel Prozesse & Aktivitäten Datenmodell

eSkel - Skelette Task-Farm Pipeline Divide & Conquer Skelett - Topologien

Neuerungen in eSkel 2 Zusammenfassung und Ausblick

3

Was ist ein Skelett?

Grafik: [Co04]

Von der unstrukturierten zur strukturierten Programmierung

Beispiel „load-balancing“ (Task-Farm):

4

eSkel: Konzeption & ZieleAnforderungen Ansprechend für MPI Programmierer Schnelle Einarbeitung Auszahlung in kurzer Zeit

Folgerungen Bibliothek Basis: C/MPI.

5

Paralleles Arbeiten

Reihenfolgebeziehung

Aufgabe

TeammitgliedZu bearbeitendes Gebiet

Security System ausschaltenAllan

Rasen mähen Wege säubern Unkraut jätenAllan:

NordparkBernice: Südpark

Charlene: Ostpark Dominic:

Westpark

Ed: Nord- u. Ostpark

Francis: Süd- u.

Westpark

Georgia:Vorgarten Francis:

Hauptgarten

Rasenspränkler checkenAllan

Security System einschaltenAllan

Grafik: [Qu04, S. 11]

Daten- und Funktionale Parallelität

6

Basiselemente von eSkelProzesse und Aktivitäten

Reihenfolgebeziehung

Aufgabe

TeammitgliedZu bearbeitendes Gebiet

Security System ausschaltenAllan

Rasen mähen Wege säubern Unkraut jätenAllan:

NordparkBernice: Südpark

Charlene: Ostpark Dominic:

Westpark

Ed: Nord- u. Ostpark

Francis: Süd- u.

Westpark

Georgia:Vorgarten Francis:

Hauptgarten

Rasenspränkler checkenAllan

Security System einschaltenAllan

Grafik: [Qu04, S. 11]

Aktivitäten

Prozesse

7

Basiselemente von eSkel eDM - Atom

Tripel: Zeiger, Länge, Typ (vgl. MPI) Spread (= Ausdehnung)

eDM - Collection Bündelung von eDM - Atomen.

Datenmodell

8

eSkel - SkeletteSkelett-Familie „Task-Farm“

Ein Ergebnis pro Atom

Expliziter Informationsaustausch

Impliziter Farmer Farm1for1 Farm

Expliziter Farmer SimpleFarm1for1 SimpleFarm

Farmer

Worker Worker Worker

Interaktion

Aktivität

Grafik vgl: [PK05, S. 3]

9

eSkel - Skelett: Farm1for1

void Farm1for1(int nw, eSkel atom t * worker (eSkel atom t *), int col, void *in, int inlen, int inmul, spread t inspr, MPI Datatype inty, void *out, int outlen, int *outmul, spread t outspr, MPI Datatype outty, int outbuffsz, MPI Comm comm);

void Farm1for1 ( int nw,eSkel_atom_t * worker (eSkel_atom_t *),int col,void *in, int inlen, int inmul,spread_t inspr, MPI_Datatype inty,void *out, int outlen, int *outmul, spread_t

outspr,MPI_Datatype outty, int outbuffsz,MPI_Comm comm)

Anzahl der WorkerWorker-Aktivität (Zeiger auf C-Funktion)Zuordnung von Prozessen zu AktivitätenInput eDM-Collection & TypinformationenOutput eDM-Collection, Typinformationen & Output-BufferCommunicator (Kontext)»

Ein Ergebnis pro Atom; impliziter Farmer

10

eSkel - Skelett: Farmvoid Farm ( int nw,

void worker (void),int col,void *in, int inlen, int inmul,spread_t inspr, MPI_Datatype inty,void *out, int outlen, int *outmul, spread_t

outspr,MPI_Datatype outty, int outbuffsz,MPI_Comm comm)

Farmer

Worker Worker Worker

Interaktion

Aktivität

Grafik vgl: [PK05, S. 3]

Expliziter Informationsaustausch; impliziter Farmer

11

void SimpleFarm( int nw,void worker (void),int col,void *in, int inlen, int inmul,spread_t inspr, MPI_Datatype inty,void *out, int outlen, int *outmul, spread_t

outspr,MPI_Datatype outty, int outbuffsz,MPI_Comm comm)

eSkel - Skelett: SimpleFarmExpliziter Informationsaustausch; expliziter Farmer

12

eSkel - Skelett: Pipeline

Arbeitsschritt 1 Arbeitsschritt 2 Arbeitsschritt 3 Arbeitsschritt 4

Interaktion

Aktivität

void Pipeline ( int ns,void (*stages[])(void),int col,spread_t spr[], MPI_Datatype ty[],void *in, int inlen, int inmul,void *out, int outlen, int *outmul, int outbuffsz,MPI_Comm comm)

Grafik vgl: [Tut02, S. 3]

Expliziter Informationsaustausch

13

Pipeline & Parallelität

Arbeitsschritt 1 Arbeitsschritt 2 Arbeitsschritt 3 Arbeitsschritt 4Fertige Autos

Grafik: [Qu04, S. 13]

14

eSkel - Skelett: ButterflyFür Divide & Conquer Algorithmen mit folgenden

Eigenschaften:

Alle Aktivitäten in der Teilungsphase Anzahl der Prozesse zu Anfang Potenz von 2 und halbiert

sich von Level zu Level Interaktionen zwischen Prozessoren treten paarweise

auf – in der Form, dass die Dimensionen eines Hypercubes heruntergebrochen werden.

Ein Divide & Conquer Skelett

15

eSkel - Skelett: Butterfly

Grafik: [Co04]

16

eSkel - Skelett: Butterfly

Grafik: [Co04]

17

eSkel - Skelett: Butterfly

Grafik: [Co04]

18

eSkel - Skelett: Butterfly

void Butterfly ( int nd,void level(void),MPI_Datatype ty,MPI_Comm comm)

19

Skelett - Topologien

Farmer

WorkerWorker ...

Farm

AufgabenAufgaben

ErgebnisseErgebnisse

Arbeitsschritt 1 Farmer Arbeitsschritt 3

WorkerWorker ...

Farm

Aufgaben Ergebnisse

AufgabenAufgaben

ErgebnisseErgebnisse

Pipeline

Grafik vgl: [PK05, S. 3]

20

Neuerungen in eSkel 2 Skelette

Pipeline, Deal, (Farm, HaloSwap, Butterfly)

...

Grafik vgl: [BCGH205, S. 2]

Deal:

21

Neuerungen in eSkel 2 Datenmodell

Neu: eDM-Molekül Interaktionsart explizit: Interaction mode

IMPL, EXPL, DEV Verschachtelungsart explizit: Data mode

BUF, STR.

22

Neuerungen in eSkel 2void Pipeline ( int ns,

Imode_t imode[],eSkel_molecule_t * (*stages[])(eSkel_molecule_t

*), int col,Dmode_t dmode,spread_t spr[], MPI_Datatype ty[],void *in, int inlen, int inmul,void *out, int outlen, int *outmul, int outbuffsz,MPI_Comm comm)

Molekül, Interaktions- und Verschachtelungsart am Beispiel der Pipeline-Signatur

23

Zusammenfassung Skelette als sinnvolle Grundlage für die parallele

Programmierung Grundlegende Forschungsergebnisse: Verschachtelungs-

& Interaktionsmodi Einarbeitungszeit ~ 1h.

24

Ausblick Effizienz der Implementierungen leidet

nachgewiesenermaßen nur wenig eSkel leider noch im Stadium eines Prototyps In Planung:

Mehr Demo-Anwendungen Interne Optimierungen Ausweitung des Skelett-Angebots Vereinfachte API (evtl. neue Basis: JAVA-MPI?!).

25

26

Quellennachweis[BCGH205] A. Benoit, M. Cole, S. Gilmore, J. Hillston: Using eSkel to

implement the multiple baseline stereo application, Proceedings of ParCo, Malaga, 2005.

[Co04] M. Cole: Presentation, School of informatics, Edinburgh, 2004.

[PK05] M. Poldner, H. Kuchen: On Implementing The Farm Skeleton, Proceedings of HLPP, Werwick, 2005.

[Qu04] M. Quinn: Parallel Programming in C with MPI and OpenMP, McGraw-Hill, 2004.

[Tut02] M. Cole: The edinburgh Skeleon library - Tutorial introduction, 2002, URL: http://homepages.inf.ed.ac.uk/abenoit1/eSkel/, Abrufdatum: 24. April 2007.

27

„Spread“

Prozess 1 Prozess 2 Prozess 3

Lokaler „Spread“: 3 einzelne Datenelemente

Globaler „Spread“: 1 verteiltes DatenelementODER

Datenelement

Prozess

Quelle: [Co04, S. 395]