Ábra 14. Adatpárhuzamos program elosztása
Párhuzamos programozást támogató nyelvi eszközök összehasonlítása: Nyelvek, eszközök: HPF
2.6
HPF
High Performance Fortran az adatpárhuzamosságot
támogató kiterjesztése a Fortran 77 nyelvnek.
2.6.1
Bevezetõ az eszközrõl
Az adatpárhuzamosságot támogató nyelvek a
vektor-mûveleteket támogató
nagyszámítógépek fordítóiból
fejlõdtek ki. Ezekben a nyelvekben a program szekvenciális
kódjában a hardware által támogatott vektor
mûveletek is szerepelhettek, ami nagy mértékben
gyorsította az egyszerû szekvenciális kód
futását. Az adat párhuzamosságot
támogató nyelvek tehát szekvenciális program
írására alkalmas nyelvek, amelyek sok
beépített elemet tartalmaznak nagy mennyiségû adat
párhuzamos kezelésére. A nagy méretû
tömbök, mátrixok elosztását a processzorok
memóriájában, és a velük végzett
mûveletek folyamatának szervezését automatikusan
elvégzik.
Leggyakrabban SIMD számítógépeken találhatóak meg, de egyre több MIMD architektúrájú gépre is készítenek ilyen fordítókat.
A Fortran 90 magában sok olyan lehetõséget tartalmaz amelyek lehetõvé teszik adat párhuzamos programok írását (pl. tömb mûveletek), de vannak hiányosságai, amik miatt nem biztos, hogy optimális kódot generál a fordító minden számítógépen.
Ezen hiányosságok kiküszöbölésére a Fortran 90 nyelvet többen is kiterjesztették fordítási direktívákkal és új nyelvi elemekkel. Ilyenek a CRAFT, a CM-Fortran (Connection Machine Fortran) és ezen törekvések egybefogására egy fórum által szabványosított (HPFF - High Performance Fortran Forum) HPF nyelv.
Az adatpárhuzamosságot más programozási nyelvekben is támogatják. A HPF-hez hasonlóan több hagyományos nyelvet is kiterjesztettek, és így született a C*, a *LISP és a MODULA-2* nyelv. Törekvések vannak a C++ kiterjesztésére is: pC++ és HPC++.
Ezek a kiterjesztések általában ugyanezeket az elveket követik - sõt sok változatuk egyenesen az HPF-bõl veszi a terminológiáját (pC++, HPC++ és MODULA-2*) -, ezért a HPF nyelv megismerése ezen nyelvek megtanulásában is nagy segítség lehet.
F77 F90 REAL a(64), b(64) REAL a(64), b(64) DO i = 1, 64 a(i) = 2.0 a = 2.0 b(i) = b(i) * a(i) b = b * a END DOF90 programban a tömböt szét lehet osztani a processzorok között - ha van elég, akkor akár minden tömbelemet más-más processzor kezelhet -, és a rajtuk végzett mûveleteket párhuzamosan lehet elvégezni. Implicit párhuzamosság kifejezésére az F77 program nem alkalmas, mert a fordító programnak a ciklus szemantikájának kifejtése túl nagy feladat lenne.
Az F90-ben a tömbökkel ugyanúgy lehet mûveleteket végezni, mint egyszerû változókkal, és ekkor az adott mûvelet minden tömbelemre lesz alkalmazva.
Egy adatpárhuzamosságot támogató nyelven írt program általában szekvenciálisan végrehajtható és párhuzamosítható részekre bontható. Ezen részeket általában más-más gépek hajtják végre.
A szekvenciális részeket egy nagy teljesítményû munkaállomás, a párhuzamosított részeket egyszerûbb - de nagyon sok (CM 200-nál akár 65536 darab) - kis processzor hajtja végre. A sok kis processzor koordinálását is a nagy munkaállomás végzi el.
Ábra 14. Adatpárhuzamos program elosztása
A felhasználói felület leírásában a HPF és a Fortran 90 párhuzamossággal kapcsolatos elemei találhatóak meg. Az itt található elemeket a HPF fordítóprogramok mind támogatják. Ha egy elem Fortran 90-ben is megvan, akkor azt kiemelem.
A HPF sok megoldását fordítási direktívákkal el lehet rejteni, így a HPF program egy helyes Fortran 90 program is lehet. Ez a megoldás megjegyzés sorokba írt utasításokkal érhetõ el:
!HPF$ PROCESSORS pr(3) INTEGER a(8) ...Ezeket a speciális (!HPF$) megjegyzéseket a HPF fordító figyelembe veszi.
Az F77-ben megszokott skalár mûveleteket a Fortran 90-ben már tömbökre is lehet alkalmazni. Az így leírt mûveleteket a fordító a kifejezésben szereplõ tömbök megfelelõ elemeire fogja alkalmazni. Az egyértelmû szemantika érdekében a mûveletekben szereplõ tömbök dimenzióinak és méreteinek meg kell egyezniük.
A következõ példában a B tömb megfelelõ elemeinek és c változónak az összege kerül bele A tömb megfelelõ elemeibe. A beépített függvények - mint a gyökvonás - is használhatóak.
integer A(10,10), B(10,10), c A = B + c A = A + 1.0 A = SQRT(A)
A tömbmûveleteknél a kifejezésekbe persze nem csak egész tömbök, hanem azok részei is behelyettesíthetõek. Résztömböt a megfelelõ koordináta helyére írt számhármassal lehet megadni: alsó-határ:felsõ-határ:lépéskö. A tömb lépésköznyi távolságra lévõ elemei az alsó határtól a felsõ határig lépkedve lesznek a résztömb elemei. Ilyen specifikációt hiányosan és több koordináta helyén is meg lehet adni.
integer A(4,8), B(4,8) A(2, :) ! A masodik sora A(2, 2:7) ! A masodik soranak kozepe A(2, 1:8:2) ! A masodik sorabol minden ! masodik elem ! B tomb eltolasa, es hozzaadasa A-hoz A(:, 1:7) = A(:, 1:7) + B(:, 2:8)
Vannak persze olyan mûveletek is, amelyek egész tömböket is érintenek. Ezek közül a következõek vannak definiálva:
Az összeg, szorzat, minimum és maximum mûveletek az egész tömbre értendõk, tekintet nélkül annak alakjára, dimenzióinak számára.
A maximum és minimum helyek keresésekor az eredményt az argumentum tömb dimenziószámának megfelelõ nagyságú tömbbe fogja beletenni az operátor:
integer A(10,10), B(20, 10), P(2), s ... P = MAXLOC(A) s = SUM(A) B(11:20, :) = MATMUL(A, B(1:10, :)Egyes mûveleteknél szükség lehet a szomszédos mátrix elemekre. Ilyen esetekben használható a CSHIFT mûvelet, mellyel a mátrixot valamelyik dimenzió irányában körkörösen el lehet forgatni:
result = CSHIFT(X, 2, -1) ! masodik dimenzioban egy ! elemmel visszaforgat
Ábra 15. CSHIFT(X, 2, -1)
result = CSHIFT(X, -1) ! elso dimenzional eleg ! egy parameter
Ábra 16. CSHIFT(X, -1)
A következõ átlagolási feladat az eltolást használva sokkal egyszerûbben leírható:
real X(0:99), B(0:99)
do i = 0,99
B(i) = ( X(mod(i+99,100) + X(mod(i+1,100)) )/2
enddo
F90-ben:
real X(100), B(100), L(100), R(100)
L = CSHIFT(X,+1)
R = CSHIFT(X,-1)
B = ( L + R )/2
,vagy még egyszerûbben:
real X(100), B(100)
B = ( CSHIFT(X,+1) + CSHIFT(X,-1) )/2
A HPF, illetve más párhuzamos Fortran kiterjesztések ezeken kívül még operátorok gazdag választékát nyújtják, például asszociatív mûveletek részeredményeit is kiszámoló eszközöket.
Igen költséges módszerekkel a program adatfolyamának feltérképezésével esetleg egy Fortran 90 fordítóprogram is képes lehet optimálisan elosztani nagy tömböket sok processzoron, viszont a HPF erre jobb megoldást kínál. A programozó fordítási direktívákkal tájékoztathatja a fordítót, hogy szerinte hogyan lehetne az adatokat optimálisan elosztani, hogy minél kevesebb legyen a kommunikáció a számítások végzése során.
Ábra 17. Tömbök elosztása HPF-ben
Az adatok elosztására szolgáló elemek csak direktívák, azaz a fordító figyelmen kívül is hagyhatja azokat, ha úgy ítéli meg, hogy csökkentik a futtatható program hatásfokát. Ezt nyugodtan megteheti, hiszen ezek csak a tömbök elosztását a folyamatok szervezését befolyásolhatják, de a program jelentését, szemantikáját nem. Elhagyásuk, vagy megtartásuk esetén ugyanazt a végeredményt kell produkálnia a kész programnak.
Az adatok elosztását három szinten lehet leírni:
!HPF$ PROCESSORS procik(10,3) !HPF$ PROCESSORS masleosztas(30)Mindkét esetben 30 virtuális processzor használható.
!HPF$ PROCESSORS p(4,8)
real D(1024), E(1024)
! D elosztasa sorokbol allo blokkokkal, a sorok folytonosak
!HPF$ DISTRIBUTE D(BLOCK, *)
! E elosztasa p virtualis processzormatrixon, az elosztas
! oszlopokbol allo blokkokra bontassal, es ezen oszlopok
! cirkularis szetosztasav tortenik meg
!HPF$ DISTRIBUTE E(CYCLIC, BLOCK) ONTO p
Igazítás legegyszerûbb formája, ha egy tömböt egy másikhoz van igazítva:
real A(10), B(10) !HPF$ ALIGN B WITH AEzzel a direktívával bonyolultabb kapcsolatokat is meg lehet határozni:
ALIGN A(I) WITH B(I+2) ! A(1)-et B(3)-hoz igazitja ALIGN A(I) WITH B(2*I) ! A(1)-et B(2)-hoz, A(2)-t B(4)-hez... ALIGN A(I/2) WITH B(I) ! A(1:2)-t B(1)-hez ALIGN D(I,J) WITH E(J,I) ! D-t E transzponaltjahoz ALIGN D(:,*) WITH A(:) ! D sorait A elemeihez
Adatok olvasása általában sokkal kevesebb idõt igényel, mint az adatok írása - különleges architektúráktól eltekintve - ezért érdemes lehet egy-egy gyakran használt vektort minden processzoron lemásolni, ha a mûveletek csak olvasnak belõle:
!HPF$ ALIGN A(*) WITH E(*, J)
A Cray T3D párhuzamos gépen ez az elv nem biztos, hogy megfelelõ, mert ott egy távoli processzor memóriájába rövidebb idõ alatt lehet beleírni, mint egy adatot kiolvasni. Ennek oka egyszerûen az, hogy az írásnál csak egy irányba kell kommunikálni.
Az igazításhoz nem feltétlenül kell igazi tömböket felhasználni, lehet mintákat is készíteni.
Az HPF által definiált adatelosztási módszert hatékonysága, jól definiáltsága és viszonylag egyszerû fogalmai miatt egyre több adatpárhuzamosságot támogató nyelv is átvette, pl. pC++ és HPC++.
WHERE
Tömbök minden egyes elemére végrehajtott mûveleteknél használható ez a konstrukció:
real A(1024), B(1024) ... WHERE (A .NE. 0) A = 1 / A B = A * 10 ELSE WHERE B = 1 END WHEREMinden A-beli elemre kiértékelõdik a feltétel, és ennek eredményétõl függõen végrehajtódik a két utasításblokk közül az egyik.
FORALL
Párhuzamosan végrehajtott ciklus a nyelvben a FORALL kulcsszóval írható le. Ebben az eszközben a cilusmagok példányai egyszerre indulnak el a különbözõ processzorokon.
A kulcsszó után index értelmezési tartományát lehet meghatározni érték-hármasokkal, illetve egy opcionális feltétellel:
! tombok inicializalasa FORALL(I = 1:1024) A(I) = I FORALL(I=1:32, J=1:32:2) X(I,J) = I+J ! felso haromszog matrix nullazasa FORALL(I=1:32, J=1:32, I<J) X(I,J) = 0.0
A mûveletekben nem történhet hivatkozás más lépésekben kiszámolt értékekre, hiszen ezek végrehajtási sorrendje definiálatlan. Ezeket az utasításokat a fordító megvizsgálhatja, de helyességük eldöntése néhány esetben csak futásidõben történhet meg:
FORALL(I=1:32) A(permut(I)) = B(I)
INDEPENDENT
Hagyományos ciklusok is párhuzamosíthatóak az INDEPENDENT direktívával:
!HPF$ INDEPENDENT DO I= 1, n A(I) = I ENDDO
Az így megírt ciklusból a fordító párhuzamosan is végrehajtható ciklusmagokat is generálhat. Ebben az esetben minden ciklusmagban szerepel a ciklusváltozó egy lokális másolata. Ezekben az utasításokban átmeneti - de globálisan deklarált - változókra is lehet hivatkozni, amely veszélyes lehet. Az ilyen gondok elkerülésére egyes változókból minden ciklusmag számára készülhet egy-egy lokális másolat:
!HPF$ INDEPENDENT, NEW(temp) DO I=1, n temp = A(I+1) + A(I-1) A(I) = temp/2 ENDDO
PURE
Egyszerre több példányban elinduló programrészek szemantikája meghatározhatatlan lenne, ha bármilyen függvényt meg lehetne belõlük hívni. Ilyen helyzetek miatt ezekben az esetekben csak PURE direktívával definiált függvények hívhatóak meg.
A PURE direktíva egyike a Fortran 90-ben bevezetett függvény attribútumait leíró direktíváknak. Azt határozza meg, hogy a függvényben nem lehet globális változóra hivatkozni, mutatót használni, és a paraméterek értékét nem lehet megváltoztatni. Az így definiált függvény helyességét a fordító ellenõrzi.
A PURE tulajdonsággal rendelkezõ függvényeknek tehát semmiféle mellékhatása nem lehet, így nyugodtan lehet õket használni párhuzamosan futó folyamatszálakban is.
F90-ben alprogram elején is lehet lokális tömböket deklarálni, melyek méretét akár a paraméterlista is befolyásolhatja:
subroutine valami(a, b, c, m, n) real dimension(n,n), intent(in) :: A ! csak olvashato real dimension(m,m) :: b,c intent(out) :: b ! kimenetre intent(inout) :: c real dimension(n,m) :: temp ! lokalis tomb ...Ezek az információk az alprogram törzsétõl külön is definiálhatóak, amik a hívások típusellenõrzését teszik lehetõvé.
Lokális tömbök definiálásakor hasznosak lehetnek az alábbi beépített függvények (pl.: A(2, -1:3, 10) :
Alprogramok hívásakor a fõprogramban lévõ tömb-elosztás nem biztos, hogy megfelel az alprogram algoritmusának. Ilyen esetekben az alprogram paramétereiben szereplõ tömböket újra szét kell osztani a REDISTRIBUTE és a REALIGN direktívák használatával.
Ezek a megoldások persze nagyon költségesek lehetnek, ezért ha az algoritmus egy lokális tömbjében egyszerûen egy paraméterét szeretné utánozni, akkor használhatja a INHERIT direktívát az elosztás leírására.
A programok írásánál persze az is jól jöhet, ha a fordításkor már ismert a célarchitektúra felépítése. Ezekrõl a helyi lehetõségekrõl a PROCESSORS_SHAPE és a NUMBER_OF_PROCESSORS függvények segítségével lehet érdeklõdni.
! Mandelbrot halmaz szamitasa (-2,-2)-(2,2)
PROGRAM mandel
IMPLICIT NONE
INTEGER, PARAMETER :: N=512, RESOLUTION=255
INTEGER :: i, j, start, stop
INTEGER, DIMENSION(N,N) :: colour
REAL, DIMENSION(N,N) :: zr, zi, cr, ci, zrs, zis
!HPF$ DISTRIBUTE (BLOCK,BLOCK) :: zr, zi, cr, ci, zrs, zis
!HPF$ DISTRIBUTE (BLOCK,BLOCK) :: colour
! A tombok inicializalasa a FORALL utasitas hasznalataval
!
FORALL (i=1:n, j=1:n) zr(i,j) = REAL(i-1)/REAL(n-1)
FORALL (i=1:n, j=1:n) zi(i,j) = REAL(j-1)/REAL(n-1)
! Segedtombok beallitasa
!
cr = zr
ci = zi
zrs = zr*zr
zis = zi*zi
colour = 0
! A fo szamitasi muvelet
!
DO i = 0, RESOLUTION
WHERE ((zrs + zis) .le. 4.0)
zrs = zr*zr
zis = zi*zi
zi = 2.0*zr*zi + ci
zr = zrs - zis + cr
colour = i
END WHERE
END DO
! A kep kiirasa PGM formatumban
!
OPEN(UNIT=10, FILE='mandel.pgm')
WRITE(10, FMT='(''P2'',/,i3,2x,i3,/,i3)') N, N, RESOLUTION
WRITE(10,*) colour
CLOSE(UNIT=10)
END
A Fortran 90 nyelvet persze ebben az irányban is ki lehet bõvíteni rutinkönyvtárakkal (pl. PVM, vagy MPI), illetve nyelvi elemekkel (pl. Fortran M csatornái).
2.6.4
Összefoglalás
A High Performance Fortran nyelvet a feladatok egy szûkebb
körének megoldására lehet használni, mint az
eddig ismertetett eszközöket. Fõleg matematikai
számítások, kiegyensúlyozott adatpárhuzamos
feladatok megoldására alkalmas, viszont ezek
leírására nagyon jó eszközöket
biztosít.
Az HPF nyelven megírt program szerkezete egy hagyományos program szerkezetének felel meg, ezért a hagyományos nyelvekben használt programtervezési, és helyességbizonyítási módszerek használhatóak benne.
A nyelv nem alkalmas - vagy sok nehézséget okoz - kiegyensúlyozatlan problémák kezelésére, MIMD stílusú párhuzamos programok írásárasa, tehát osztott operációs rendszer, vagy kliens/szerver modellre épülõ adatbázis-kezelõ nem írható benne.
A nyelv kifejezetten az adat-párhuzamosság támogatására készült, a szekvenciális kódból a fordítóprogram készít párhuzamos szerkezeteket. Az adatokra csak azok egészét érintõ mûveletek fogalmazhatóak meg, teljesen független utasítássorozatok nem.
Ezen megkötés alól a több példányban futó programszerkezetekbõl a függvények hívása kibúvót jelenthetne, de ez egyéb feltételek miatt nem jelent lényegi különbséget ( a PURE attribútummal rendelkezõ függvényekre vonatkozó megkötések miatt ugyanazt a feladatot lehet elvégezni velük, mintha a függvények kódját behelyettesítenénk a ciklusmagba).
A nyelv nem definiálja, hogy a program pontosan milyen programot eredményezzen egy adott párhuzamos architektúrán. Ezt a részt minden HPF fordító implementáció függõ módon írja le.
Ebben az esetben nem lehet beszélni folyamat modellekrõl sem, hiszen a program logikailag egyetlen folyamat a programozó számára, és az implementációtól függõen ez egyes pontokon több processzoron is végrehajtódó részeket tartalmazhat.
A párhuzamos programozást támogató programozási eszközök további vizsgálati szempontjai között szereplõ kommunikációs és szinkronizációs lehetõségeket is elfedi a nyelv, ezért ezekrõl elég keveset lehet mondani:
Kommunikáció szempontjából egy osztott memóriával rendelkezõ gépet modellez. Az összes párhuzamosítható szerkezet vége egy implicit szinkronizációs pontot jelent a programban létrejött párhuzamosan végrehajtott folyamatszálak számára.
A HPF és Fortran 90 nyelvek jellemzõi:
Tehát a HPF nyelv matematikai problémák kezelésére alkalmas, de ezen a téren kezelhetõségben messze megelõzi az összes többi eszközt.
| 
| 
| 
|