High Performance Fortran Seminar Parallele Programmierung von Sebastian König und Stefan Seidel

High Performance Fortran

Seminar Parallele Programmierung

von

Sebastian König und Stefan Seidel

Seminar Parallele Programmierung (SS2003) – High Performance Fortran (Sebastian König, Stefan Seidel) 2 / 46

!HPF$ - Inhalt

• Einführung• Modell• Datenverteilung

– 2-Schichten-Mapping– Direktiven zur Datenverteilung

• Spracherweiterungen– Anweisungen zur parallelen Ausführung– Intrinsics / Library– Extrinsics

• Datenverteilung und Performance• Fallbeispiel: Gauss-Elimination• HPF im Vergleich• Fazit

EinführungModellDatenverteilungSpracherweiterungenPerformanceFallbeispielHPF im VergleichFazit


!HPF$ - Einführung

• Erweiterung von Fortran 90

– Direktiven

– Spracherweiterungen

– Neue Funktionen

• Datenparallele Sprache

• Einsatz vor allem im wissenschaftlich-, technischen Bereich



!HPF$ - Einführung

• The IBM Mathematical FORmula TRANslation System, FORTRAN

• Viele Dialekte viele Standards

• Fortran 66, 77, 90, 95, 2000

• High Performance Fortran Forum (HPFF)

• HPF 1.0 im Mai 1993

• HPF 1.1 im November 1994

• HPF 2.0 Ende 1996

Historie EinführungModellDatenverteilungSpracherweiterungenPerformanceFallbeispielHPF im VergleichFazit


!HPF$ - Modell

• Datenparallelität

– Mehrere Prozessoren führen dasselbe Programm aus

– Die einzelnen Prozessoren arbeiten nur auf einem Teil der Daten

Welcher Prozessor auf welchen Daten arbeitet wird mit sog. Direktiven festgelegt

Datenparallelität EinführungModellDatenverteilungSpracherweiterungenPerformanceFallbeispielHPF im VergleichFazit


!HPF$ - Modell

• SPMD (single program multiple data)

– Das Programm folgt einem Kontrollfluss

– Globaler Adressraum

– Kommunikation tritt auf, greift ein Prozessor auf Daten zu, die nicht in seinem lokalen Speicher liegen

Organisationsprinzip EinführungModellDatenverteilungSpracherweiterungenPerformanceFallbeispielHPF im VergleichFazit


!HPF$ - Modell

• Der HPF-Compiler erzeugt zielarchitekturspezifischen, ausführbaren Code

Codegenerierung

Fortran 90

HPF

RISC- Code VektorisierterVektorcode

Paralleler SIMDCode

MIMD- Code(Naachrichtenaus

tausch)

HPF Spracherweiterungen



!HPF$ - ModellProgrammaufbau

Konzeptionelle Prozessoranordnung

Verteilung der Daten auf Prozessoren

Ausführung von (parallelen)Operationen

auf den Daten



!HPF$ - Modell

• Verteilung der Daten: 2-Schichten-Mapping

2-Schichten-Mapping

Konzeptionelle Prozessoranordnung


Abbildung abstrakter aufphyisikalische Prozessoren

Abgleich der Verteilung vonDatenobjekten

2-Schichten-Mapping



!HPF$ - Datenverteilung

• Definition einer abstrakten Anordnung von Prozessoren

• Nicht notwendigerweise Bezug zu den tatsächlich vorhandenen physikalischen Prozessoren

• Spezifiziert werden

– Name

– Rang (Anzahl der Dimensionen)

– Größe der Dimensionen

• Alle Prozessoranordnungen in einem Programm haben die gleiche Anzahl von abstrakten Prozessoren

Direktiven zur Datenverteilung - PROCESSORS

KonzeptionelleProzessoranordnung

Abgleich der Verteilung von Datenobjekten


Abbildung abstrakter aufPhysikalische Prozessoren




Allgemein:

!HPF$ PROCESSORS anordnungName(anordnungDefinition)

Beispiele:

!HPF PROCESSORS Anordnung1(4)

!HPF PROCESSORS Anordnung2(2,2)

!HPF PROCESSORS Anordnung3(2,1,2)

!HPF PROCESSORS Anordnung4(NUMBER_OF_PROCESSORS())

!HPF$ PROCESSORS

Anordnung5(8,NUMBER_OF_PROCESSORS()/8)

Direktiven zur Datenverteilung - PROCESSORS EinführungModellDatenverteilungSpracherweiterungenPerformanceFallbeispielHPF im VergleichFazit







• Ausrichtung eines Objektes auf ein anderes Objekt

• Die Datenobjekte werden im Speicher desselben Prozessors abgelegt

• Dadurch effizienter Zugriff ohne zusätzlichen Kommunikationsaufwand möglich

• Beipiel:

REAL, DIMENSION(10) :: A,B,T

!HPF$ ALIGN (:) WITH T(:) :: A,B

• Anders ausgedrückt:

!HPF ALIGN A(:) WITH T(:)

!HPF ALIGN B(:) WITH T(:)

Direktiven zur Datenverteilung - ALIGN EinführungModellDatenverteilungSpracherweiterungenPerformanceFallbeispielHPF im VergleichFazit







• Beispiel:

• zwei Felder der Größe 16x16 und 14x14

• Die „inneren“ Elemente des 16x16-Feldes sollen mit den entsprechenden Elementen des 14x14-Feldes in Berechnungen verwendet werden

REAL X(16,16), Y(14,14)

!HPF$ ALIGN Y(I,J) WITH X(I+1,J+1)

Direktiven zur Datenverteilung - ALIGN EinführungModellDatenverteilungSpracherweiterungenPerformanceFallbeispielHPF im VergleichFazit







• Felder, die als DYNAMIC deklariert werden, können mit REALIGN neu verteilt werden

REAL X(16,16), Y(14,14)!HPF DYNAMIC X,Y

!HPF$ ALIGN Y(I,J) WITH X(I+1,J+1)

.

.

.

!HPF$ REALIGN Y(I,J) WITH X(I+2,J+2)

Direktiven zur Datenverteilung - REALIGN EinführungModellDatenverteilungSpracherweiterungenPerformanceFallbeispielHPF im VergleichFazit







• Definition von Vorlagen zur Datenverteilung

• Es muss kein einzelnes Feld deklariert werden, um den gesamten benötigten Bereich aufzuspannen

• Beispiel:

!HPF$ TEMPLATE, DISTRIBUTE(BLOCK, BLOCK) :: EARTH(N+1,N+1)

REAL, DIMENSION(N,N) :: NW, NE, SW, SE

!HPF$ ALIGN NW(I,J) WITH EARTH( I , J )

!HPF$ ALIGN NE(I,J) WITH EARTH( I ,J+1)

!HPF$ ALIGN SW(I,J) WITH EARTH(I+1, J )

!HPF$ ALIGN SE(I,J) WITH EARTH(I+1,J+1)

Direktiven zur Datenverteilung - TEMPLATE EinführungModellDatenverteilungSpracherweiterungenPerformanceFallbeispielHPF im VergleichFazit






• Verteilung der Daten auf eine Prozessoranordnung

• BLOCK-Distribution

– Aufteilung des Feldes in gleichgroße Blöcke

– Bei Verteilung von #A Elementen auf #P Prozessoren erhält jeder Prozessor maximal #A/#P Elemente

• CYCLIC-Distribution

– Arbeitet nach “Round Robin“-Prinzip

– Bei Verteilung von #A Elementen auf #P Prozessoren erhält jeder Prozessor maximal #A/#P Elemente

• Sowohl BLOCK-Distribution als auch CYCLIC-Distribution können mit einem Parameter für die Blockgröße aufgerufen werden

!HPF$ - DatenverteilungDirektiven zur Datenverteilung - DISTRIBUTE Einführung

ModellDatenverteilungSpracherweiterungenPerformanceFallbeispielHPF im VergleichFazit







• Beispiel:

REAL Kartenspiel(52)

!HPF$ PROCESSORS A(4)

!HPF$ DISTRIBUTE Kartenspiel(CYCLIC)ONTO A

Direktiven zur Datenverteilung - DISTRIBUTE

1

49

45

41

37

33

29

25

17

13

9

5

3

51

47

43

39

35

31

27

23

15

7

2

50

46

42

38

34

30

26

22

18

14

6

4

52

48

44

40

36

32

28

24

20

16

12

8

10 11

19

21

P1 P2 P3 P4








• Beispiel (fortgesetzt):



!HPF$ DISTRIBUTE Kartenspiel(CYCLIC(5))ONTO A


1

43

42

41

25

24

23

22

5

4

3

2

11

-

52

51

35

34

33

32

31

14

12

6

48

47

46

30

29

28

27

26

10

9

7

16

-

-

-

40

39

38

37

36

20

19

18

17

8 13

15

21

P1 P2 P3 P4

45

44

50

49 -

-

-

-








• Beispiel (fortgesetzt):



!HPF$ DISTRIBUTE Kartenspiel(BLOCK)


1

13

12

11

10

9

8

7

5

4

3

2

27

39

38

37

36

35

34

33

32

30

28

14

26

25

24

23

22

21

20

19

18

17

15

40

52

51

50

49

48

47

46

45

44

43

41

41

16 29

31

6

P1 P2 P3 P4








• Felder, die als DYNAMIC deklariert werden, können mit REDISTRIBUTE neu verteilt werden

• Felder, die auf das entsprechende Feld ausgerichtet sind, werden auch neu verteilt

Direktiven zur Datenverteilung - REDISTRIBUTE EinführungModellDatenverteilungSpracherweiterungenPerformanceFallbeispielHPF im VergleichFazit







• Nicht notwendigerweise direkter Zusammenhang zwischen abstrakter Anordnung und tatsächlich physikalisch vorhandenen Prozessoren

• Elemente die auf einem abstrakten Prozessor liegen, liegen auch auf einem physikalischen Prozessor

• Abbildung compilerabhängig







!HPF$ - Spracherweiterungen

• Keine automatische Erzeugung von Parallelität

• Alte Anweisungen (Fortran 90) weiterhin sequentiell

• Explizite Programmierung paralleler Ausführung

• Owner-computes-ruleje nach Compiler zur Optimierung umgangen

• Korrektheit durch Programmierer zu gewährleisten

Einführung EinführungModellDatenverteilungSpracherweiterungenPerformanceFallbeispielHPF im VergleichFazit



Startwert : Endwert : Schrittgröße

• Standardnotation zur Definition von Indexbereichen

• Funktionen erlaubtz.B. UBound()

Triplet-Notation EinführungModellDatenverteilungSpracherweiterungenPerformanceFallbeispielHPF im VergleichFazit



• Anweisung zur parallelen Feldzuweisung

• Indexbereich pro Dimension mit Triplet-Definition

Beispiel:

INTEGER, DIMENSION(4) :: A = (/-4,-1,2,4/)

FORALL (i=1:4, A(i) .LT. 0) A(i) = -A(i)

• Indexbereich: 1:4

• Maske A(i).LT.0 nur für A(i) kleiner („less than“) 0

Bei allen negativen Werten das Vorzeichen ändern

• FORALL-Block – Nicht pro Index alle Anweisungen, sondern pro Anweisung alle Indices

Anweisungen zur parallelen Ausführung - FORALL EinführungModellDatenverteilungSpracherweiterungenPerformanceFallbeispielHPF im VergleichFazit



• Zusicherung von Unabhängigkeit der in einer Schleife genutzten Variablen

• Erlaubt Parallelisierung von DO-Schleifen

• NEW-Variablen werden für jede Iteration neu initialisiert (lokal für Schleife)

!HPF$ INDEPENDENT, NEW (j)DO i = 1, n

!HPF$ INDEPENDENTDO j = 1, m

x = A(j)y = B(j)C(i,j) = x+y

END DOEND DO

Anweisungen zur parallelen Ausführung - INDEPENDENT EinführungModellDatenverteilungSpracherweiterungenPerformanceFallbeispielHPF im VergleichFazit



PURE [typ] FUNCTION name ([parameter])

• Zusicherung isolierter Ausführung einer Funktion gegenüber dem Compiler keine Veränderung globaler Daten, nur Rückgabe eines Wertes

• Verwendung in FORALL Anweisungen

• Nutzung für komplexere Berechnungen, bedingten Anweisung, Iterationen, lokale Variablen

Anweisungen zur parallelen Ausführung - PURE EinführungModellDatenverteilungSpracherweiterungenPerformanceFallbeispielHPF im VergleichFazit



• Funktionen zur Systemabfrage– NUMBER_OF_PROCESSORS()

Liefert Anzahl physikalischer Prozessoren– PROCESSOR_SHAPE()

Physikalische Anordnung der Prozessoren

• Funktionen zur Berechnung– ILEN

benötigte Bitzahl zur Speicherung eines Integer– MAXLOC

Indices des größten Wertes im angegebenen Bereich eines Arrays

– MINLOCIndices des kleinsten Wertes im angegebenen Bereich eines Arrays

Intrinsics EinführungModellDatenverteilungSpracherweiterungenPerformanceFallbeispielHPF im VergleichFazit



• Abfrage der Datenverteilung

• Bitinformationen über Integer-Daten

• Datenverdichtung

• Präfix- und Suffix-Berechnung

• Bitbasierte Operation mit Zuweisung

• Sortierung

Library EinführungModellDatenverteilungSpracherweiterungenPerformanceFallbeispielHPF im VergleichFazit



• Einbindung externer Programme

• Ausführung auf jedem Prozessor isoliert mit allen dort zur Verfügung stehenden Daten

• Maschinennahe Berechnungen

• Explizites Message Passing

• HPF_LOCAL

INTERFACEEXTRINSIC (C) SUBROUTINE prozedure1(par1, par2)

REAL :: par1INTEGER :: par2

END SUBROUTINEEND INTERFACE

EXTRINSICS EinführungModellDatenverteilungSpracherweiterungenPerformanceFallbeispielHPF im VergleichFazit


!HPF$ - Datenverteilung und Performance

• Einfaches Modell zur Bestimmung der Gesamtperformance:

Ein einfaches Modell

Ttotal= Tpar / Tactive + Tserial + Tcomm

Ttotal = gesamte Ausführungszeit

Tpar = Anteil der Arbeit, die parallel ausgeführt werden kann

Tactive = Anzahl aktiver, paralleler Prozessoren

Tserial = Anteil der Arbeit, der sequenziell ausgeführt werden muss

Tcomm = Zeit, die durch Kommunikation in Anspruch genommen wird




• Ein einfaches Beispielprogramm:

Ein Beispielprogramm

REAL, DIMENSION(8,8) :: A, B

FORALL (J=2:7, K=2:7)

A (J,K) = (B(J,K)+B(J-1,K))

END FORALL




• Ansatz 1: Aufteilung von B in Spalten gleicher Größe


PROCESSORS, DIMENSION(4) :: P

DISTRIBUTE B(BLOCK,*) ONTO P

(1,2)

(1,1)

(1,8)

(1,7)

(1,6)

(1,5)

(1,4)

(1,3)

(2,2)

(2,1)

(2,8)

(2,7)

(2,6)

(2,5)

(2,4)

(2,3)

(3,2)

(3,1)

(3,8)

(3,7)

(3,6)

(3,5)

(3,4)

(3,3)

(4,2)

(4,1)

(4,8)

(4,7)

(4,6)

(4,5)

(4,4)

(4,3)

(5,2)

(5,1)

(5,8)

(5,7)

(5,6)

(5,5)

(5,4)

(5,3)

(6,2)

(6,1)

(6,8)

(6,7)

(6,6)

(6,5)

(6,4)

(6,3)

(7,2)

(7,1)

(7,8)

(7,7)

(7,6)

(7,5)

(7,4)

(7,3)

(8,2)

(8,1)

(8,8)

(8,7)

(8,6)

(8,5)

(8,4)

(8,3)

P1 P2 P3 P4




• Ansatz 1: Aufteilung von B in Spalten gleicher Größe

– P1 und P4 führen je 7 Berechnungen aus


– Kommunikationsaufwand: 21 Elementaustausche

Ein Beispielprogramm EinführungModellDatenverteilungSpracherweiterungenPerformanceFallbeispielHPF im VergleichFazit



• Ansatz 2: Aufteilung von B in vier gleichgroße Blöcke


PROCESSORS, DIMENSION(2,2) :: Q

DISTRIBUTE B(BLOCK,BLOCK) ONTO Q

(4,8)(3,8)(2,8)(1,8)

(4,7)(3,7)(2,7)(1,7)

(4,6)(3,6)(2,6)(1,6)

(4,5)(3,5)(2,5)(1,5)

(4,4)(3,4)(2,4)(1,4)

(4,3)(3,3)(2,3)(1,3)

(4,2)(3,2)(2,2)(1,2)

(4,1)(3,1)(2,1)(1,1)

(8,4)(7,4)(6,4)(5,4)

(8,3)(7,3)(6,3)(5,3)

(8,2)(7,2)(6,2)(5,2)

(8,1)(7,1)(6,1)(5,1)

(8,8)(7,8)(6,8)(5,8)

(8,7)(7,7)(6,7)(5,7)

(8,6)(7,6)(6,6)(5,6)

(8,5)(7,5)(6,5)(5,5)

P1 P2

P3 P4




• Ansatz 2: Aufteilung von B in vier gleichgroße Blöcke



– Kommunikationsaufwand: 7 Elementaustausche

Ein Beispielprogramm EinführungModellDatenverteilungSpracherweiterungenPerformanceFallbeispielHPF im VergleichFazit


!HPF$ - Fallbeispiel: Gauss-Elimination

• Standardbenchmark für parallele Sprachen

• Gegeben: lineares GleichungssystemAx = b, wobeiA eine NxN Matrix,x der gesuchte Lösungsvektor undb ein gegebener Zielvektor ist Speicherung als A Nx(N+1) Matrix, wobei in Spalte N+1 b gespeichert wird

• Lösungsverfahren:

– Elimination: A in Dreiecksform bringen

– Rücksubstitution zur Ermittlung der Lösung

Ausgangsproblem EinführungModellDatenverteilungSpracherweiterungenPerformanceFallbeispielHPF im VergleichFazit

Subroutine gauss(n, A, x)

real A(n,n+1)

integer nreal X(n), Fac(n), Row(n+1)integer Indx(n), Itmp(1)integer i, j, k, max_indxreal maxvalIndx = 0


!HPF$ - Fallbeispiel: Gauss-EliminationElimination

Für i = 1 bis n-1

suche Pivotzeile (größter Wert in Spalte i)

Index der Pivotzeile broadcasten

Faktoren berechnen

Pivotzeile broadcasten

Restzeilen neu berechnen durch Addition des entsprechenden Vielfachen

Matrix auf Dreieckform bringen


DO i = 1,n

Itmp = MAXLOC(ABS(A(:,i)), MASK=Indx.EQ.0)

max_indx = Itmp(1)

Fac = A(:,i)/A(max_indx,i)

Row = A(max_indx)

FORALL (j=1:n, k=i:n+1, Indx(j).EQ.0) A(j,k) = A(j,k) + Fac(j) * Row(k)

END DO

FORALL (j=1:n) A(Indx(j),:) = A(j,:)



Für Zeilen (i) rückwärts

Lösung für X(i) ermitteln A(i, n+1) / A(i,i)

Werte in Spalte n+1 korrigieren Subtraktion des entsprechenden Vielfachen

Rücksubstitution EinführungModellDatenverteilungSpracherweiterungenPerformanceFallbeispielHPF im VergleichFazit

DO j = n, 1, -1

X(j) = A(j,n+1) / A(j,j)

A(1:j-1,n+1) = A(1:j-1, n+1) - A(1:j-1,j) * X(j)

END DO



Pro Iteration:

• Ermitteln der Pivotzeile

• Index broadcasten

• Faktoren zur Multiplikation berechnen

• Faktoren broadcasten

• Paralleles Ausrechnen der noch nicht fertigen Zeilen

Kommunikation und Rechenlastverteilung EinführungModellDatenverteilungSpracherweiterungenPerformanceFallbeispielHPF im VergleichFazit



• Bei Array-basierten Berechnungen häufig standardmäßig (BLOCK,*)-Verteilung

würde zu immer weniger genutzten Prozessoren führen (bei fortgeschrittenen Iterationen)

keinerlei Vorteil für Datenlokalität aufgrund der vorliegenden Kommunikation

• Empfehlenswert (CYCLIC, *)

deutlich bessere (gleichmäßigere) Auslastung der Prozessoren

keine Einbußen durch Kommunikation

Ergebnis und Datenverteilung EinführungModellDatenverteilungSpracherweiterungenPerformanceFallbeispielHPF im VergleichFazit


!HPF$ - HPF im Vergleich

• Vergleich auf IBM SP2 mit 8 Knoten – 1997

• Public-Domain-Implementationen: MPI-ch und PVM

• HPF-Compiler noch nicht ausgereift - Vergleich mit PD-Compilern lässt zukünftige Besserung vermuten



!HPF$ - HPF im Vergleich

• Kompakte und einfache Parallelisierung HPF Code häufig kürzer als Fortran Code

• Implizite Kommunikation und Synchronisation

• Komplexität gemessen an NCSS: 0,4 – 1,8andere Sprachen 1,2 – 16 (MPI, PVM)

Schnelle und einfache Implementierung, aber schlechtere Performance

NCSS – Non-Commented Source Code Statemens



!HPF$ - Fazit

Fragen ?



!HPF$ - HPF 2

• Neue Verteilungsmuster für DISTRIBUTE

– BLOCK_GEN

– INDIRECT

– SHADOW

• Datenverteilung

– PROCESSORS – Subsets

ZugabeDatenverteilung


!HPF$ - HPF 2

• ON HOMEDO i = 1, n !HPF$ ON HOME( ix(i) ) x(i) = y(ix(i)) - y(iy(i))END DO

• RESIDENT!HPF$ ALIGN (i) WITH x(i) :: ix, y, iy !HPF$ DISTRIBUTE x(BLOCK)!HPF$ INDEPENDENTDO i = 1, n !HPF$ ON HOME( ix(i) ), RESIDENT(y(iy(i))) x(i) = y(ix(i)) - y(iy(i))END DO

• TASK_REGION!HPF$ TASK_REGION !HPF$ ON HOME(p(1:8)) CALL procedure1(x,y) !HPF$ ON HOME(p(9:16)) CALL procedure2(z)!HPF$ END TASK_REGION

Ausführungssteuerung Zugabe


!HPF$ - HPF 2

• Erweiterung für INDEPENDENT

– REDUCTION

• Intrinsics

– ACTIVE_NUM_PROCS

– ACTIVE_PROCS_SHAPE

• asynchronous I/O

weitere Zugabe

Documents

High Performance Fortran Seminar Parallele Programmierung von Sebastian König und Stefan Seidel