Hesham El-Rewini & Ted G. Lewis: Distributed and Parallel
Computing
Chapter 9: Parallel Virtual Machine (PVM)
- PVM environment and application structure
- Task creation
- Task groups
- Communication among tasks
- Task synchronization
- Reduction operations
- Work assignment
PVM
- bolo pôvodne vyvinuté v ORNL (Oak Ridge National Laboratory) a v
Univerzite v Tennessee
- v r.1989 (PVM 2.x 1991 a PVM 3.x 1993 s novým API)
- je určené na písanie message-passing programov
pre heterogénne prostredie
- cieľom je poskytnúť výkonné funkcie na riadenie procesov
a pre dynamickú správu prostriedkov (resources)
- nie je jazyk, je daemon a knižnica
- pre C-jazyk aj FORTRAN
- heterogénna interoperabilita
PVM prostredie a štruktúra aplikácií
- prostredím je virtuálny stroj = dynamická sieť uzlov, zložená z
heterogénnych počítačových systémov, ale spravovaná ako jeden paralelný počítač
- uzlom môže byť jedno- aj viac-procesorový systém, 1 uzol = 1 daemon
- pred spustením aplikácie musí užívateľ najprv spustiť PVM a skonfigurovať
virtuálny stroj
- PVM konzola (aplikačný proces) umožňuje riadiť chod virtuálneho stroja
- aplikácia je zložená z množstva sekvenčných programov, z ktorých
každý korešponduje s jedným alebo aj s viacerými procesmi paralelného programu
- sekvenčné programy sú skompilované individuálne pre každý uzol (host)
- kódy sú umiestnené tak, aby boli dostupné pre ten-ktorý uzol (NFS)
- SPMD aj MPMD/MPSD (napr. input-processing-output)
- rôzne možné štruktúry aplikácie:
- do hviezdy, t.j. supervisor/workers, resp. master/slaves model
- strom, t.j. hierarchia
Štruktúra supervisor/workers
- jeden supervisor (master) proces, ktorý slúži aj ako iniciátor
(je spustený manuálne), komunikuje s užívateľom, prideľuje prácu a zbiera
výsledky
- viac worker (slave) procesov, môžu byť nezávislé
(s.292), alebo môžu navzájom
komunikovať (napr. pri zoraďovaní poľa údajov: zlučovanie vykoná sám
supervisor, alebo sú niektoré uzly poverené vykonať čiastočné zlučovanie s
vopred vybraným iným uzlom a iba tie potom odovzdajú výsledky procesu
supervisor, ktorému tak uľahčia prácu, s.294)
Hierarchická Štruktúra
- tu je umožnené aj procesom worker vytvárať ďalšiu úroveň procesov
(worker, aj opakovane viac úrovní)
- úloha, ktorá vytvára ďalšiu úlohu sa nazýva rodič (parent)
- tak sa môže vytvoriť viacúrovňový strom (aplikácia typu
rozdeľ a panuj, divide-and-conquer)
- príklad s triedením poľa údajov: proces vytvorí dvojicu nezávislých
procesov a dá im každému polovicu údajov na prácu, potom zlúči výsledky a
pošle 'hore' (delenie sa zastaví pri rozumnej veľkosti poľa na triedenie,
s.295)
Vytváranie úloh
- úloha môže byť spustená manuálne (shell command in terminal) alebo
vytvorená (spawned) iným PVM procesom (úlohou, dynamicky)
- úloha, ktorá vykonala pvm_spawn(), sa nazýva rodič a novovytvorené
úlohy sa nazývajú deti
- programátor musí určiť stroj, vykonateľný súbor, počet kópií a pole
argumentov pre procesy detí
- každá PVM úloha má pridelený svoj jedinečný identifikátor (integer
TID), ktorý sa používa pri komunikácii na určenie adresáta
Získanie identifikátora úlohy
- svoj (mytid=pvm_mytid()),
dieťaťa (pvm_spawn(...&tid)),
rodičov (ptid=pvm_parent())
a ostatných úloh (pvm_tasks())
- PvmNoParent je vrátená
hodnota v prípade, ak volajúci proces nemá rodiča (supervisor/master)
- identifikátor démona (daemon_tid=pvm_tidtohost(id))
umožní zistiť, na ktorom uzle beží proces
Dynamická tvorba úloh
-
num=pvm_spawn(Child,Args,Flag,Where,HowMany,&Tids)
- vráti počet úspešne vytvorených úloh z vykonateľného súboru Child s command-line
parametrami Args
- Flag určuje význam nasledovného Where
0=PvmTaskDefault...kdekoľvek
1=PvmTaskHost......Where=meno uzla
('.', 'arrakis', 'arrakis.dcs.elf.stuba.sk', ...)
2=PvmTaskArch......Where=meno OS
('SUN4SOL2', 'NETBSDSPARC', 'FREEBSD', 'NETBSDPMAX')
4=PvmTaskDebug (bitový OR)
8=PvmTaskTrace (-//-)
16=PvmMppFront (-//-)
32=PvmHostCompl...Where=na ktorom nie
(doplnok)
- binárny súbor musí byť dostupný pre uzol, kde je proces vytváraný (NFS)
- HowMany určuje počet kópií
- &Tids je smerník na pole, kam sa uložia identifikátory (tid)
vytvorených procesov (alebo chybové kódy)
- príklad: int n1, tids[2];
n1=pvm_spawn("/home/ja/worker.exe",0,1,"arrakis",2, &tids);
Skupiny úloh
- bežiaca PVM úloha (proces) môže patriť do nejakej/nejakých
skupiny/skupín, ktoré môžu byť dynamicky menené (join, leave)
- vhodné pre vykonanie kolektívnej operácie (broadcast, ...)
- úloha môže kedykoľvek opustiť/pripojiť skupinu nezávisle od ostatných
jej členov bez toho, aby ich o tom informovala (nie ako v MPI)
- i=pvm_joingroup(meno)
vráti poradové číslo v skupine (nemusia však byť súvislé)
- skupina vznikne pripojením prvého procesu, ktorý dostane i=0
- info=pvm_lvgroup(meno)
ak vráti záporné číslo, tak je to číslo chyby
- znovupripojením môže úloha dostať iné poradové číslo
- s=pvm_gsize(meno)
vráti počet členov aj nečlenovi, podobne aj
s=pvm_gettid(meno,poradie)
aj
s=pvm_getinst(meno,tid)
- group manager daemon (implementačný detail)
- príklad:
| úloha 0 (tid0=200) |
úloha 1 (tid1=100) |
úloha 2 (tid2=300) |
úloha 3 (tid3=400) |
stav |
| i1=pvm_joingroup("s") | | | | i1=0 |
| | i2=pvm_joingroup("s") | | | i2=1 |
| | | i3=pvm_joingroup("s") | | i3=2 |
| | inf=pvm_lvgroup("s") | | n=pvm_gsize("s") | n=3 |
| | | n=pvm_gsize("s") | | n=2 |
| | | | i4=pvm_joingroup("s") | i4=1 |
| | i2=pvm_joingroup("s") | | | i2=3 |
| t=pvm_gettid("s",1) | | | | t=400 |
| | | i=pvm_getinst("s",100) | | i=3 |
Komunikácia medzi úlohami
- asynchrónnym prenosom správ pomocou démona a knižničných funkcií
- blokujúci a neblokujúci príjem správy
Obr.1. Komunikácia v PVM
Čísla znamenajú tok riadenia.
V bode 6 sa pri blokujúcom príjme počká na príchod správy.
- vyslanie údajov jednému alebo viacerým príjemcom pozostáva z 3 krokov:
- inicializácia vysielacej vyrovnávacej pamäte (send buffer)
- spakovanie (uloženie) dát do tejto pamäte
- poslanie správy
- podobne, prijatie údajov pozostáva z 2 krokov:
- prijatie správy
- rozpakovanie (vybratie) dát z prijímacej vyrovnávacej pamäte (receive buffer)
Vyrovnávacie pamäte správ
- poskladanie dát do vyrovnávacej pamäte (spakovanie dát), aby na druhej
strane dáta správne interpretovali
- bufid=pvm_initsend(voľba_kódovania) a
bufid=pvm_mkbuf(voľba_kódovania)
- voľba_kódovania môže byť:
- PvmDataDefault XDR (externá dátová reprezentácia) - heterogénny systém
- PvmDataRaw no encoding (stroje 'si rozumejú')
- PvmDataInPlace data left in place (len smerníky a dáta nesmú byť menené, kým sa neodvysielajú)
- iba jeden bafer (vyrovnávacia pamäť) pre vysielanie a jeden pre príjem správ je aktívny
- pvm_initsend ho nuluje
- pvm_mkbuf vytvorí neaktívny
(ďalší) bafer
- old=pvm_setsbuf(bufid) a
old=pvm_setrbuf(bufid) zmenia aktívny bafer
- buf=pvm_getsbuf() a
buf=pvm_getrbuf()
vrátia identifikátor práve aktívneho bafra
Spakovanie dát
- viac funkcií
status=pvm_pk*(*p, count, stride)
pre polia p jednotlivých údajových typov s veľkosťou count
a obkrokom stride (byte, int, float, double, complex, double
complex, long int, short int, string)
- s premenlivým počtom parametrov
pvm_packf(printf_like...)
- ľubovoľne sa môžu za sebou opakovať pri plnení bafra
- ale rovnako sa musia na druhej strane dáta rozpakovávať
(programátor zodpovedá za to)
Poslanie správy
- asynchrónne bez čakania na druhú stranu; čaká sa iba na odpoveď démona,
že či sú parametre v poriadku
- bafer je naplnený a treba len určiť príjemcu/-ov (tid) a zvoliť značku
(návestie, tag)
- jednému: info=pvm_send(tid, tag)
- info aj tag sú celé čísla, info<0 znamená chybu
- viacerým: info=pvm_mcast(tids, n, tag),
kde tids je pole identifikátorov, n je počet príjemcov
- poznámka: aj keby bol tid úlohy, ktorá posiela, v zozname, nepošle si sám
sebe správu
- skupine: info=pvm_bcast(meno, tag),
nemusí byť pritom členom, interne sa zistí zoznam tid a vykoná mcast
- môže prísť k nezrovnalosti v dôsledku dynamického charakteru skupiny
(riešiť to 'ručnou' synchronizáciou)
- spakovanie a poslanie v jednom kroku:
info=pvm_psend(tid, tag, my_array, n, data_type)
Prijatie správy
- 3 typy: blokujúce, neblokujúce a s časovou lehotou (timeout)
- blokujúci príjem: bufid=pvm_recv(tid, tag)
(ak tid=-1 od hocikoho, ak tag=-1 hocičo)
- neblokujúci príjem: bufid=pvm_nrecv(tid, tag)
(ak želaná správa nebola k dispozícii, vráti bufid=0)
- príjem s časovou lehotou: bufid=pvm_trecv(tid, tag, timeout)
(timeout je štruktúra dvoch čísiel tv_sec a tv_usec; ak obe=0, ide o nrecv; ak smerník=NULL, ide o recv)
- blokujúci príjem a rozpakovanie v jednom kroku:
info=pvm_precv(tid, tag, my_array, n, data_type,
&src, &atag, &alen)
n určuje povolenú veľkosť poľa my_array na zápis a vráti info o prijatej
správe (od koho, s akým tag, v akej dĺžke) a=actual
Obr.2.Tri typy operácie príjmu
Rozpakovanie dát
- treba urobiť presne v takom istom poradí ako pri spakovaní pred odoslaním
status=pvm_upk*(*p, count, stride)
...
Synchronizácia úloh
- slúži na zabezpečenie želaného poradia vykonávaných prác
(údajová závislosť, data dependence)
- pri odchode zo skupiny (dynamicky meniacej svoju veľkosť)
- pomocou blokujúceho príjmu alebo bariérou
Precedenčná synchronizácia
- zabezpečí požadované poradie vykonávania funkcií medzi úlohami
- pomocou poslania správy a blokujúcim príjmom
Obr.3.Precedenčná synchronizácia
realizovaná poslaním správy. Je zaručné ukončenie funkcie f pred začiatkom
vykonávania funkcie g.
Bariéry
- sú to synchronizačné body
- Žiadna úloha nebude pokračovať, pokiaľ všetky úlohy nedospejú k
tejto bariére
- členovia skupiny vykonajú
info=pvm_barrier(group_name, ntasks)
- počkajú na daný (totožný) počet úloh (typicky veľkosť skupiny, t.j.
všetci)
- počet musí byť zadaný kvôli dynamickosti (join/leave)
Obr.4.Tri úlohy skupiny slave
čakajú na bariére.
Operácia redukcie
- vektor hodnôt je spracovaný na jednu hodnotu: max, min, sum, prod, user.
- info=pvm_reduce(func, data, n, datatype, tag,
group_name, root)
- kde root=príjemca výsledku (poradové číslo v skupine)
- funkcia je vykonaná na príslušných elementoch z dátového poľa príslušným
členom skupiny
- dátové pole bude u člena root prepísané výsledkom, u ostatných
členov môže byť tiež zmenené (nedefinovaným spôsobom)
- príklad: skupina slave má 3 členov: T0, T1 a T2. Všetci vykonajú
rovnakú funkciu:
info = pvm_reduce(PvmSum, data_array, 5, PVM_INT, tag, "slave",
root)
Obr.5. Operácia redukcie vykonaná
členmi skupiny slave.
Prideľovanie práce
- paralelná úloha môže byť vykonávaná rovnakým programom (SPMD) alebo
rôznymi programami (pri odlišných funkciách)
Pomocou odlišných programov
- supervízor aktivuje procesy worker cez pvm_spawn()
- vie s nimi komunikovať, keďže pozná ich TID
- worker si zistí TID supervízora cez pvm_parent()
Pomocou rovnakého programu
- ak by sme vopred vedeli aké budú mať pridelené TID, stačilo by:
switch (my_id) {
case 1:
/* praca pridelena pracovnikovi ktoreho ID je 1 */
break;
case 2:
/* praca pridelena pracovnikovi ktoreho ID je 2 */
break;
.........
case n-1:
/* praca pridelena pracovnikovi ktoreho ID je n-1 */
break;
default:;} /* end switch */
- ale ako TID sú prideľované rôzne čísla, takže sa to dá riešiť napríklad
pomocou poľa ID alebo pomocou skupiny
- pomocou poľa
- supervízor pošle všetkým procesom worker také pole, kde vložil všetky TID
(svoje na nultú pozíciu, s.311)
- každý (worker) si vyhľadá polohu svojho TID a tak vie svoje poradové číslo
- pomocou skupiny úloh
- supervízor sa prvý prihlási do skupiny (pvm_join) a dostane poradové
číslo 0
- procesy worker sa prihlasujú potom a prácu si rozdeľujú podľa poradových
čísiel, ktoré dostanú
Pomocou poľa
Supervisor code
/* ******************** Supervisor ****************** */
.....
int tid[n]; /* array to keep track of TIDs */
mytid = pvm_mytid(); /* get supervisor's tid */
tid[0] = mytid;
pvm_spawn(..., ..., ..., n-1, tid+1); /* start up element of the array */
/* Now send the array tid to all the workers */
/* Do the initialization and buffer packing here */
..............
pvm_mcast(tid, n, 1); /* sam sebe aj tak neposle, mohlo byt tid+1, n-1 */
..............
/* Now do any work that needs to be done in the parent - supervisor */
..............
Worker code
/* ******************** Worker ********************** */
.....
int tid[n]; /* array to keep track of TIDs */
worker_id = pvm_mytid(); /* get the tid of this worker */
supervisor_id = pvm_parent(); /* get the tid of the supervisor */
pvm_recv(supervisor_id,1); /* receive a message from the supervisor */
/* do some unpacking to get the array tid here */
/* search the array tid */
for(i = 0; i < n && tid[i] != worker_id; i++);
my_id = i;
/* my_id for each worker is a unique integer between 1 and n-1 */
/* The switch statement should be inserted here */
...............
Pomocou skupiny úloh
Supervisor code
/* ******************** Supervisor ****************** */
.....
int tid[n]; /* memory for return value of pvm_spawn (TIDs) */
mytid = pvm_mytid(); /* get supervisor's tid */
my_id = pvm_joingroup("everybody"); /* join a group */
pvm_spawn(..., ..., ..., n-1, ...); /* start up the children */
pvm_barrier("everybody",n); /*wait for everyone to join the group */
/* Now do any work that needs to be done in the parent - supervisor */
..............
Worker code
/* ******************** Worker ********************** */
.....
worker_id = pvm_mytid(); /* get the tid of this worker */
my_id = pvm_joingroup("everybody"); /* join a group */
/* my_id for each worker is a unique integer between 1 and n-1 */
pvm_barrier("everybody",n); /*wait for everyone to join the group */
/* The switch statement should be inserted here */
...............