Párhuzamos programozást támogató nyelvi eszközök összehasonlítása: Nyelvek, eszközök
2.
Nyelvek, eszközök
2.1
Osztályozási szempontok, jellemzôk
A különbözô programozási nyelvek és
eszközök osztályozását is két
oldalról lehet megközelíteni: az általuk
nyújtott lehetôségek, illetve a velük
megoldható feladatok oldaláról.
2.1.1
Feladatok osztályozása
A párhuzamos programozási eszközöket nagyon sokszor a
futásidô csökkentése érdekében
alkalmazzák. A problémamegoldás sikeressége nagy
mértékben függ a feladat fajtájától.
Ha van egy szekvenciális program, akkor azt többféle módon is fel lehet bontani kisebb részekre, amelyek már párhuzamosan is végrehajthatóak. A részekre bontás eredménye sok kis szekvenciális programrészlet lesz, amelyek között valamilyen eszközzel szinkronizálni, vagy kommunikálni kell. A szinkronizációs, illetve kommunikációs eszközök óhatatlanul valamilyen többletköltséggel járnak, amelyek korlátozzák a párhuzamosítási folyamatot abban, hogy minden határon túl gyorsítsa egy feladat megoldását.
A feladatok a részekre bontás szempontjából a következô kategóriákba eshetnek:
Ábra 5. Feladat szétbontása
A párhuzamosságot támogató eszközök másik nagy felhasználási területe a feladat típusa lapján történõ munkamegosztás támogatása.
Sok olyan feladat van, melyek nagyon jól kezelhetô, illetve definiálható részekre bonthatóak. Ezen feladatok megoldásában is érdemes ezeket a részeket megtartani, mert így sokkal rugalmasabban alakítható át a rendszer egy másik feladat megoldására. Ha ezeket a részfeladatokat különálló programokban, illetve rendszerekben valósítják meg, akkor meg kell oldani az ezek közötti kommunikációt, szinkronizációt.
Ilyen feladat lehet például egy kliens/szerver modellre épülô adatbázis-kezelô alkalmazás, melynél a kliens és a szerver közötti kommunikációt párhuzamosság támogatására létrehozott nyelvekkel, vagy eszközökkel lehet megszervezni.
Megbízható alkalmazások, illetve rendszerek igénye
általában a fenti feladatokkal együtt szokott jelentkezni,
de ezen a területen vannak olyan problémák, amelyek magukban
is szükségessé teszik párhuzamosságot
támogató eszközök használatát, pl.:
repülés irányító
számítógép mûködésének
tükrözése több gépen egy
repülôgépen, majd a kapott eredmények
összevetése.
2.1.2
Modellek, eszközök osztályai
A vizsgálat másik iránya a lehetôségek
felmérése, azaz milyen eszközöket biztosít az
adott környezet a programozó számára a fenti
feladatok megoldására.
Az eszközök vizsgálatánál az alábbi három szempont elsôdleges:
Az adat-párhuzamosságot támogató eszközök általában egy szekvenciális programnyelvre épülnek, melyet nagy mátrixokkal végzett mûveletek párhuzamosítására szolgáló elemekkel bôvítenek ki. Ezek párhuzamosító fordítók, ahol a programozónak a legegyszerûbb esetben semmi beleszólása sincs az elkészülô program processzorok közötti elosztásába.
A nyelveket általában kiegészítik olyan elemekkel is amelyekkel az adatok elosztása finomabban is szabályozható, de nem adnak eszközöket nem kiegyensúlyozott problémák megoldására. Általában nincs lehetôség arra sem, hogy teljesen független utasítássorozat hajtódjon végre a különbözõ adatelemeken.
Ilyen nyelvek a FORTRAN-ra épülô FORTRAN 90, illetve ennek variánsai, valamint a C++-ra épülô pC++ (parallel C++) nyelv.
A folyamat-párhuzamosságot támogató nyelvek - valamilyen szinten - egymással párhuzamosan futó folyamatokat valósítanak meg, melyek közötti kommunikációt és szinkronizációt a programozónak kell megszerveznie.
Ezek a nyelvek illetve eszközök párhuzamos algoritmusok megvalósítására használhatóak, nem kínálnak lehetôséget egy hagyományos szekvenciális program egyszerû párhuzamosítására.
Ebbe a csoportba sorolható lényegében az összes többi eszköz.
Vannak törekvések a két fajta módszer összeházsítására egyetlen nyelvben, illetve eszközben. Ilyen a FORTRAN 90-ben párhuzamosan indítható függvények lehetõsége, amelyek viszonylag független kódok futtatását teszik lehetôvé egyes adatelemeken. Ennek a törekvésnek a jegyében készül az HPC++ (High Performance C++) nyelv is a pC++ és a CC++ (Compositional C++) nyelvek kombinácójából.
A folyamatok párhuzamosságánál meg lehet vizsgálni, hogy milyen folyamat-modelleket támogatnak:
A folyamat-modellek vizsgálatakor nem csak az indulás, hanem a megállás problémájával is lehet foglalkozni:
Egy program folyamatainak leképezése a meglévô erôforrásokra a nyelvek illetve eszközök egy másik fontos tulajdonsága.
A statikus és félig-statikus modellekben ez a feladat könnyebben megoldható, hiszen a program indítása elõtt megbecsülhetô, hogy egy-egy folyamata mennyi erôforrást fog felhasználni, és ennek megfelelôen statikusan is elosztható a feladat.
A dinamikus modellben szintén megadhatóak statikus elvek az erôforrások elosztására, azonban ezek a legritkább esetben vezetnek jó eredményre. Ezek a modellek dinamikus erôforrás elosztást, a feladat pillanatnyi helyzetéhez illeszkedô leképezést igényelnek.
Ennek legegyszerûbb módja az, hogy a program futása közben megvizsgálja a lehetôségeit, és a rendszernek ettôl függôen jelzi erôforrás igényét (pl. megmondja, hogy melyik processzoron kell a következô folyamatot elindítani).
Ez a folyamat egyszerûsíthetô azzal, hogy a program csak azt definiálja, hogy milyen igényei vannak és a rendszer keres ehhez megfelelô lehetôségeket. Ennek egyik formája a folyamatok indításakor a PVM könyvtárban figyelhetô meg.
Ábra 6. Virtuális processzorok
Magasabb absztrakciós szinten is leírhatóak egy algoritmus erôforrás igényei virtuális processzorok és virtuális topológiák használatával. Virtuális processzorokon szorosan összetartozó - közös részfeladaton, adatterületen dolgozó, sok kommunikációt igénylô - folyamatokat lehet elindítani, amellyel a rendszer számára információt adhatunk át, hogy ezeket lehetôleg ugyanazon, vagy minél közelebb lévô valódi processzorokon helyezze el. A virtuális topológiák a kommunikácó absztrakt leírására használhatóak. Segítségükkel megadható, hogy a program folyamatai egy logikai gyûrûben, vagy fában kommunikálnak. Ezzel az információval lehetôséget adnak a rendszernek, hogy a folyamatokat a topológia által definiált szomszédsági viszonyoknak megfelelôen helyezze el. Ez az eszköz a programozó munkáját is megkönnyítheti az egyszerûbb jelölésmód miatt. Ilyen lehetôségek vannak a PARIX operációs rendszer és az MPI rutinkönyvtárában.
Futás közbeni dinamikus erôforrás elosztás egy érdekes eszköze lehetne még a folyamatok átvitele a processzorok között, de ezt a problémát még nem oldották meg hatékonyan.
A párhuzamosság szintjét egyes nyelvek, illetve eszközök különbözô helyeken húzhatják meg:
Osztott memória használata programok fejlesztésénél nagyon nagy elôny, mert a szekvenciális algoritmusok általában könnyedén párhuzamosíthatóak íly módon. Az osztott memóriának persze vannak nagy hátrányai is:
Az üzenetküldés folyamán egy küldô folyamat egy adat csomagot megcímez és valamilyen úton eljuttat egy vevô folyamathoz.
Ez a módszer nehezebben használható szekvenciális programok párhuzamosításakor, viszont minden más esetben nagyon jól illeszkedhet az kifejezetten párhuzamos algoritmusokhoz. Ez a kommunikációs forma osztott memóriát használó gépeken is nagyon könnyen megvalósítható, ezért az így elkészített algoritmusok minden párhuzamos architektúrán implementálhatóak. Az üzenetküldés hátránya - a szûk kapcsolat a folyamatok között - egy program nyomkövetése, vagy helyességének bizonyítása során nagy elônyt jelent.
Az üzenetküldés több szempontból is vizsgálható:
A kommunikációs eszközök közül - a párhuzamosság támogatásához hasonlóan - egy rendszerben több is elõfordulhat, és ezeket kombinálva is lehet használni.
A szinkronizálással kapcsolatos problémákra sok megoldás született, az egészen egyszerû - gépi kódú utasítás szintjén lévõ megoldástól - a magas absztrakciós szinten lévõ megoldásokig.
A legegyszerûbb eszköz a szemafor, melyet Dijkstra vezetett be 1965-ben.
A szemafor egy atomi módon - egyszerre csak egy folyamat számára - hozzáférhetõ tároló egység. Ha egy folyamat nem tud hozzáférni a szemaforhoz, akkor általában egy várakozási sorba kerül, amelybõl a szemafor állapotának megváltozása hozhatja ki.
Szemaforokat fõleg közösen használt erõforrásoknál - lemez, memória, stb. - a kölcsönös kizárás megvalósítására használnak.
Legegyszerûbb változata a bináris szemafor, melyben csak 1, illetve 0 értéket lehet eltárolni. A tárolás P (probern) mûvelete lényegében az erõforrás lefoglalását, a felszabadítás V (verhogen) mûvelete, pedig annak felszabadítását jelenti ebben az esetben. Ezen kívül vannak több értékû szemaforok, sõt szemafor családok is, melyeket egy mûvelettel lehet kezelni.
Nagy elõnye, hogy mûködése nagyon egyszerû, és nagyon egyszerûen implementálható, de inkább csak osztott memóriát használó rendszerekben lehet velük találkozni. A szemaforok hátránya és veszélye az egyszerûségükben rejlik, mivel így nem egyszerû velük bonyolult kizárásos problémák - például az író-olvasó probléma - megoldása.
Ennél magasabb absztrakciós szinten áll a monitor, melyet Brinch-Hansen, illetve Hoare használt elõször a hetvenes évek közepén.
Ez az eszköz adatok és a rajtuk végezhetõ mûveletek összefogására szolgál - így az objektum orientált törekvések elõdjének is tekinthetõ -, de a megoldható feladatok szempontjából nem bonyolultabb a szemafornál. A monitorban lévõ adatokat csak a monitor mûveletein keresztül lehet elérni, melyekre az kölcsönös kizárást biztosít, azaz közülük egyszerre csak egy lehet aktív. Foglalt monitort meghívó folyamatok - a szemaforokhoz hasonlóan - egy várakozási sorba kerülnek.
A monitor egyszerû szerkezete miatt alapvetõen osztott adattípusok, illetve egyszerû erõforrás szinkronizációs módszerek leírására használható.
Monitorokat például a konkurens Pascalban implementáltak.
A következõ eszközökben a szinkronizáció és a kommunikáció eléggé összekeveredik. Ez a szétválaszthatatlanság bonyolultabb esetekben elkerülhetetlen, hiszen a szinkronizáció maga is valamilyen módon egy információ átadását jelenti, másrészt bármilyen kommunikáció használható szinkronizálási problémák megoldására.
A szinkronizálás és a kommunikáció legegyszerûbb esete a szinkron üzenetküldés - ami persze két aszinkron üzenetküldéssel is szimulálható , melyben két folyamat egy pontnál megvárja egymást, és az egyik valamilyen információt juttat el a másikhoz. Itt a szinkronizáció a kommunikációban implicit benne van, nem választható el attól.
A szinkron üzenetküldés módszerével egyszerû problémák oldhatóak meg. Egy osztott adattípus megvalósításához egy ilyen egyszerû hívás nem elegendõ, ilyen kommunikációkból egy bonyolultabb kapcsolatot kell felépíteni.
Ennek egyik formája a távoli eljáráshívás, melyben lényegében két szinkron kommunikáció történik. Távoli eljáráshívás esetén - a monitorhoz hasonlóan - a hívó folyamat a fogadónak adja a vezérlés, és mindaddig várakozni fog, amíg az végre nem hajtja a mûveletet, és vissza nem adja a vezérlést.
A távoli eljáráshívásnál a monitorhoz viszonyított különbséget az osztott adattípus hiánya jelenti. Ennél az eszköznél a fogadó oldalon nincs beburkolt adatrész, a fogadó oldal mûködése lényegében tetszõleges lehet.
A másik nagy különbséget a kölcsönös kizárás implementációfüggõ megvalósítása jelenti. Ez azt takarja, hogy ennek az eszköznek az adott implementációjától függ, hogy az eljárások hívói valamilyen módon kölcsönösen kizárhatják-e egymást. A legtöbb esetben a távoli eljáráshívások reentránsak, azaz a monitor mûveleteitõl eltérõen egyszerre több pédányban is futhatnak.
A szinkron üzenetküldés és az egymást kölcsönösen kizáró távoli eljáráshívások kombinációjának tekinthetõ az Ada randevú fogalma. Az Ada-ban két folyamat szinkronizálásának, illetve kommunikációjának eszköze (az osztott változóktól eltekintve) a randevú.
Az Ada randevújában is egy kliens-kiszolgáló kapcsolat alakul ki - a monitorhoz hasonlóan -, de itt a kiszolgáló egység egy önálló folyamat, nem csak egy adathalmaz mûveleteit implementáló kód.
A nagy különbséget - a monitorhoz képest - a randevúpontokhoz kapcsolódó elkülönített várakozási sorok, és a kiszolgálásra adható bonyolultabb feltételek jelentik. A fogadó folyamat minden randevúponthoz a belsõ állapotától függõ plusz feltételeket is köthet, amivel sokkal finamabban tudja szabályozni az adatrészeihez való hozzáférést.
Mivel a kiszolgáló rész is egy folyamat, ezért sokkal bonyolultabb mûveletek írhatóak le ezzel az eszközzel, mint egy egyszerû osztott változóval.
Az Ada randevú eszközének a hátránya, hogy csak kliens-kiszolgáló kapcsolatok kezelhetõek vele, ami egymás mellé rendelt folyamatok szinkronizációjára nem igazán jó módszer.
Az osztott erõforrások kezelésének következõ (számítástudomány történetében megelõzõ, de az Ada nyelv történetében következõ) lépését az osztott adattípusok egy általánosabb formája jelenti.
Egy osztott adattípuson végezhetõ mûvelethalmaz végrehajtási sorrendjét azokra vonatkozó feltételekkel, útkifejezésekkel, vagy eseményorientált leírásokkal lehet megadni. Ezek a leírási módszerek általában nagyon bonyolult hozzáférési módok (prioritásos többszörös hozzáférésû író-olvasó probléma) leírására is alkalmasak, implementálásuk viszont nem minden esetben oldható meg egyszerûen.
Az Ada95 nyelv osztott adattípusa az ilyen útkifejezésekkel leírható szinkronizálási problémák egy részét tudja kezelni (monitorral kezelhetõ problémáknál bõvebb halmazt), egy új folyamat létrehozásának költsége nélkül. Az osztott adattípushoz lehet definiálni mûveleteket, amelyek a monitoroknak megfelelõen mûködnek - azaz kölcsönös kizárás van köztük -, lehet megadni olyanokat is amelyek akár egyszerre is végrehajtódhatnak, valamint megadhatóak az osztott adattípus belsõ állapotából kiszámolható feltétellel õrzött belépési pontok is.
Általánosabb szinkronizálási problémák megoldására osztott adattípusok esetében még nem születtek széles körben elterjedt megoldások.
Az osztott adattípusok kliens/szerver modelljén kívül még elõfordulnak egymás mellé rendelt folyamatok között is szinkronizálási problémák.
Egyik ilyen probléma, ha több folyamatot egyetlen pontnál szinkronizálni kell. Ekkor az összes folyamatnak meg kell várni az összes többit, anélkül, hogy egy külön kiszolgáló folyamat összehangolná tevékenységüket.
Az ilyen feladatok megoldására biztosít eszkzöket a PVM és az MPI rendszerek.
2.1.3
Jellemzôk
Az egyes programozási eszközöket a fenti szempontokon
kívül a hagyományos programozási nyelvekbõl
merített elvek alapján is lehet értékelni:
Az egyes eszközök értékelése a fentiekben felsorolt modellek, osztályok és jellemzõk alapján a fejezet hátralévõ részének anyaga az MPI, PVM, CC++, Ada95 és FORTRAN 90 nyelvek vizsgálata.
Szekvenciális megoldására a következõ C nyelvi program adhat példát:
/*
* Mandelbrot halmaz szamitasa (-2,-2)-(2,2)
*/
#include <stdio.h>
int main(int argc, char *argv[])
{
int N = 512; /* kepmeret */
char *pix; /* a kep */
int ix, iy; /* pixel koord. */
double x, y; /* re, im koord. */
register double ar, ai;
register double a1, a2;
register int ite; /* iteracioszam */
double x1,y1,x2,y2; /* sarkok */
FILE *f; /* az eredmeny */
x1 = -2; y1 = -2; x2 = 2; y2 = 2;
pix = (char*)malloc(N * N);
/*
* A fo szamitasi ciklus
*/
x2 -= x1;
y2 -= y1;
for (iy = N; iy-- > 0; )
{
y = (iy * y2) / N + y1;
for (ix = N; ix-- > 0; )
{
x = (ix * x2) / N + x1;
ar = x;
ai = y;
for (ite = 0; ite < 255; ite++)
{
a1 = (ar * ar);
a2 = (ai * ai);
if (a1 + a2 > 4.0)
break;
ai = 2 * ai * ar + y;
ar = a1 - a2 + x;
}
pix[iy * N + ix] = ~ite;
}
}
/*
* az eredmeny kiirasa
*/
f = fopen("mandel.pgm", "wb");
fprintf(f, "P5\n# Mandelbrot set\n");
fprintf(f, "%3d %3d\n%3d\n", N, N, 255);
fwrite(pix, 1, N * N, f);
fclose(f);
return(0);
}
A feladat megvalósításainál az eszközök matematikai problémák kezelésére nyújtott lehetõségeit, illetve a kivételes esetek kezelésére nyújtott lehetõségeket lehet megvizsgálni.
A programok eredménye 8 bites PGM formátumú kép file lesz, melyet bármilyen képfeldolgozó/nézegetõ eszközzel meg lehet nézni.
A végeredmény a következõ képre kell hogy hasonlítson:
Ábra 7. Mandelbrot halmaz
Van egy korlátozott méretû tároló, mely termelõ és fogyasztó folyamatok között biztosítja az adatok átvitelét. Ebbe a tárolóba egy, vagy több termelõ folyamat rakhat bele adatokat, és egy vagy több folyamat vehet ki belõle elemeket, amelyek ezek után eltûnnek belõle.
A tároló mérete korlátos, tehát elõfordulhat olyan eset, amikor valamelyik termelõ folyamat várakozni kényszerül, mert tele van.
A tároló persze ki is ürülhet, ezért elõfordulhat olyan eset is, amikor egy fogyasztó folyamat kényszerül várakozásra.
Ábra 8. Termelõ-fogyasztó probléma
A feladat alkalmas arra, hogy egy adott eszköz rugalmasságát, kliens/szerver problémák kezelésére nyújtott lehetõségeit meg lehessen vizsgálni.
| 
| 
| 
|