Dănut Moraru
Atunci când dorim să proiectăm o aplicatie mare consumatoare de resurse de calcul (ori să "paralelizăm" o aplicatie existentă) si nu avem o masină paralelă puternică, e bine să privim în jur. S-ar putea să descoperim că acele calculatoare din laborator, folosite până acum independent, ne pot oferi împreună puterea de calcul de care avem nevoie. Tot ce avem de făcut este să adaptăm algoritmii si să găsim implementarea potrivită pentru hardware-ul ce-l avem la îndemână.
Ideal pentru a dezvolta si rula o aplicatie distribuită este de a avea la îndemână o retea omogenă de calcul, deci cuprinzând noduri de procesare puternice, identice, împreună cu un mediu de dezvoltare dedicat arhitecturii respective (adică trusa de "scule" software pentru scrierea, testarea, depanarea si executia programelor rezultate, împreună cu biblioteci de rutine, manuale, exemple). Acestea însă costă mult, iar dacă avem bani putini si pretentii mai mici, cu un bun raport performantă/pret sunt accesibile arhitecturile cu transputere.
Retelele eterogene de calcul sunt însă mult mai răspândite. Unul din motive ar fi si faptul că reunesc masini din generatii diferite, cu arhitecturi diferite, cu sisteme de operare diferite, achizitionate de-a lungul timpului de la producători diferiti, prin eforturi investitionale esalonate. Un alt motiv ar fi si că fiecare componentă din retea a fost achizitionată cu un scop anume: o masină spre a fi utilizată ca file server, alta pentru capabilitătile grafice deosebite, o alta pentru interfetele incluse care ne convin de minune pentru achizitia noastră de date, etc. De foarte multe ori, notiunea de "retea" vine numai de la faptul că aceste masini sunt legate pe acelasi cablu, schimbând din când în când câte un fisier între ele, mai comod decât mutând discheta din unitatea unuia în a celuilalt. Poate că aceste calculatoare nu au fost puse niciodată să conlucreze în executia unei aplicatii.
Cum s-ar putea pune împreună la lucru aceste calculatoare, atât de diferite ca arhitecturi, sisteme de operare, având procesoare diferite ca performante? Platforma comună este posibilitatea de a comunica. Iar la acest capitol, din fericire, există numeroase standardizări, atât la nivel fizic - mediul de comunicatie, semnale electrice, timpi, cât si la nivel logic - de atribuire a anumitor semnificatii si de organizare a datelor interschimbate.
La sistemele omogene, comunicatia între noduri se bazează de obicei pe protocoale "interne" firmei care a proiectat si procesoarele (neaplicabile si altor arhitecturi), subsistemul ce se ocupă de comunicatii fiind inclus adeseori pe cipul procesor. Este cazul transputerelor, care comunică prin intermediul legăturilor seriale de mare viteză (5-20 MB/s). În schimb, în cazul sistemelor eterogene, tipul de retea folosită este "de largă răspândire", pentru care majoritatea firmelor produc cartele de interfatare cu masina proprie. Ca exemple, retelele de tip Ethernet sau Token Ring asigură debite de ordinul a 10 MB/s. Debitul maxim de informatie permis de retea reprezintă un factor important mai ales în sisteme puternic comunicante. În analiza oricărui algoritm, el trebuie corelat cu viteza procesoarelor de a executa instructiuni si de a face calcule. Necorelarea duce la scăderea globală a eficientei, datorată timpilor morti suplimentari din cauza aglomerării retelei.
Există actualmente o multime de protocoale de nivel înalt pe baza cărora se realizează comunicatiile. Totodată, sunt disponibile biblioteci de rutine apelabile din limbaje de programare de nivel înalt, care oferă servicii de transfer de date în retea, bazate pe protocoalele respective. Utilizatorul va folosi (prin intermediul bibliotecilor) acele protocoale implementate pe toate sistemele pe care îsi va rula aplicatia, care i se potrivesc aplicatiei sale si de ce nu - pe care le cunoaste mai bine.
Retelele locale sunt cunoscute sub denumirea de "retele cu comutare de pachete". Aceasta înseamnă că datele transferate prin retea sunt împărtite în pachete cu mărimi maxime tipic în gama 512 - 4096 octeti (MTU - Maximal Transfer Unit). Fiecare pachet este transferat independent de celelalte si poate urma o cale diferită de la emitător la receptor.
Caracteristicile pe care le vom urmări la serviciile de comunicatie în retea sunt:
Un serviciu orientat conexiune cere ca cele două aplicatii să stabilească între ele o conexiune logică înainte de a avea loc comunicatia si este folosită când mai mult de un mesaj urmează să fie schimbat între cele două entităti. Aplicatiilor care comunică li se stabileste un circuit virtual, chiar dacă fluxul de date are loc utilizând o retea cu comutare de pachete. Se foloseste atunci când aplicatiile anticipează un schimb îndelungat de date.
Un serviciu fără conexiune (orientat datagramă) constă în transmiterea mesajelor independent, fiecare trebuind să contină toate informatiile cerute pentru livrarea sa. Se utilizează acolo unde aplicatiile vor schimba date fără o planificare prealabilă.
- Sumă de control inclusă în fiecare pachet, spre a fi verificată de receptor.
- Achitare pozitivă: notificarea emitătorului că pachetul a ajuns corect sau eronat la destinatie. În caz de eroare, emitătorul retransmite pachetul în cauză. Confirmarea se poate face (la serviciile orientate conexiune) pe grup de pachete - mai eficientă decât confirmarea pentru fiecare pachet.
- Retransmitere după timeout: dacă după expirarea intervalului de timeout, nu s-a primit confirmarea de receptie (pachet pierdut), emitătorul retransmite pachetul în cauză.
Un aspect deloc de neglijat atunci când avem procesoare din familii diferite este reprezentarea datelor multioctet. Unele procesoare aranjează în memorie octetul cel mai semnificativ la adrese mici (formatul big-endian), iar altele la adrese mari (formatul little-endian). Din prima categorie fac parte procesoare ca Motorola 68000, RS6000, iar din a doua categorie Intel 80x86, VAX. Bibliotecile care oferă servicii de comunicare asigură si rutine de conversie (în ambele sensuri) între formatul standard definit de protocol si formatul procesorului local. Astfel, spre exemplu, protocoalele TCP/IP cer reprezentare tip big endian. Diferente există si în reprezentarea întregilor. Unele implementări de C "stiu" să reprezinte un întreg pe doi octeti, altele pe patru. Nepotriviri pot apărea si la reprezentarea numerelor flotante, desi există si aici standarde (exemplu: IEEE 754).
Ca solutie la problemele prezentate anterior, există biblioteci si servicii run-time care îl scutesc pe programator de grija conversiei corecte a datelor. Cu RPC (Remote Procedure Call) programatorul are senzatia că un serviciu cerut unui server la distantă se execută ca o procedură locală. Clientul va trebui însă să astepte inactiv returnarea din procedură.
Mai mult, există medii de programare si executie a aplicatiilor paralele, care permit unei retele eterogene de calculatoare să fie vazută ca o singură masină paralelă virtuală. Ca exemple: PVM (prezentat în acest număr) si P4. Acestea sunt deocamdată disponibile doar pe Unix.
Exemplul pe care îl prezint (calculul invariantilor Zernike pentru un set de imagini) face parte dintr-o aplicatie complexă de recunoastere de obiecte din imagini reale 2D, preluate cu videocamera sau scannerul (aduse la format bitmap), bazată pe retele neuronale artificiale. "Obiectele" pe care le-am încercat au fost piese electronice, litere de tipar etc.
În urma detectiei unui număr de obiecte într-o imagine, se pune problema de a găsi pentru fiecare obiect o reprezentare numerică de dimensiune redusă si constantă indiferent de dimensiunile, pozitia, unghiul de rotatie si factorul de scalare al obiectului în imagine, potrivită aplicării la intrarea unei retele neuronale. Una dintre solutiile la această problemă o constituie calcularea momentelor Zernike ale imaginii obiectului - un set de numere complexe cu proprietatea că modulele acestora au aceeasi valoare, indiferent de orientarea (unghiul de rotatie) obiectului în imagine. Invarianta la pozitia în imagine se asigură prin algoritmul de detectie si încadrare a fiecărui obiect în cercul de rază minimă si în dreptunghiul minim.
Practic, aplicatia a fost proiectată initial în C++ pentru Windows 3.1, rulând independent, iar ulterior a fost reproiectată si "distribuită" pe mai multe calculatoare. Modelul folosit pentru varianta distribuită este "ferma de procesoare".
O fermă de procesoare se compune dintr-un singur client (numit fermier sau stăpân) si mai multe servere (lucrători sau sclavi). Aceasta este oarecum invers situatiilor obisnuite, în care un singur server deserveste mai multi clienti. Fermierul (farmer) divide munca în mai multe sarcini si pentru început, trimite fiecărui lucrător (worker) câte una. De îndată ce un lucrător a terminat sarcina curentă si întoarce rezultatul muncii sale, va primi imediat o nouă sarcină. Procesul se încheie atunci când toate sarcinile s-au încheiat si au fost primite toate rezultatele. În cazul de fată, "fermierul" rulează pe un PC cu Windows 3.1 sau 3.11, iar "lucrătorii" pe PC-uri cu Windows si masini cu UNIX-uri ca Solaris, AIX, Linux.
Comunicatiile între masini se bazează pe TCP, care este orientat conexiune. A fost ales pentru compatibilitatea cu sistemele existente, dar si pentru facilitătile de control al erorilor, foatre bine putându-se folosi UDP - serviciu orientat datagramă, care nu oferă însă sigurantă. Pentru serviciile de retea, aplicatiile Windows 3.1 folosesc biblioteca winsock.dll (Windows 3.11 si Windows 95 au capabilitătile de TCP/IP încorporate), iar aplicatiile UNIX apelurile sistem pentru lucru cu socluri (sockets) - vezi bibliografia.
Pornind de la versiunea secventială a algoritmului pentru calcularea momentelor Zernike, părtile care pot fi executate în paralel trebuiesc identificate. O evaluare a timpului total cerut pentru calcule, comparativ cu timpul pentru comunicatie, poate fi decisivă pentru a alege o solutie de paralelizare sau alta.
În cele ce urmează, vor fi utilizate următoarele conventii:
ORDMAX = ordinul maxim pentru momentele Zernike calculate.
MOMMAX = numărul de momente Zernike corespunzător numărului dat ORDMAX.
Anm[MOMMAX] = vector complex continînd momentele Zernike calculate.
P(x,y) = valoarea pentru pixel (apartinînd obiectului) în coordonate (x,y) cu originea în centrul de greutate al obiectului.
O posibilă implementare a algoritmului este "Listing 1 "
După cum se observă, fiecare moment Zernike Anm[i] este calculat independent, deci este posibil să distribuim executia acestor bucle pentru diferite valori ale perechilor (n, m) (liniile 4 - 8) pe mai multe procesoare lucrînd separat. Acesta ar putea fi un avantaj, dacă reteaua are posibilitatea de "broadcasting", astfel încît valorile pixelilor apartinînd unui obiect vor fi tramsmiti de către fermier o dată pentru toti lucrătorii simultan. După aceea, fiecare lucrător va executa calculele pentru un număr de momente Zernike si va raporta rezultatele fermierului. Putem împărti egal volumul total de calcule tuturor lucrătorilor, astfel încît fiecare lucrător va executa aproximativ MOMMAX / N bucle. Este cerut dialogul initial dintre fermier si lucrători, astfel încît fiecare lucrător să obtină gama pentru valorile n si m pentru care va face calculele. Dezavantajul acestei tehnici de împărtire a buclelor (loop-splitting) este că în mediu eterogen, procesoarele lucrează la viteze diferite, iar cele mai rapide vor fi neocupate pînă ce cele mai lente îsi vor termina lucrul. În plus, buclele nu sunt egale ca volum de calcule, depinzînd de valorile pentru n si m. Pentru echilibrarea încărcării, fermierul ar trebui să cunoască "puterea" fiecărui lucrător si să le trimită acestora corespunzător dimensiuni neegale ale gamelor pentru n si m.
Pe de altă parte, dacă reteaua nu permite sau dacă calculatoarele nu apartin aceleiasi retele locale, (desi există protocoale care pot asigura "broadcasting" către calculatoare apatinînd mai multor retele locale), această metodă trebuie evitată, deoarece aceleasi date trebuie transmise fiecărui lucrător, care are nevoie de toti pixelii unui obiect.
Să considerăm o altă implementare (vezi "Listing 2 ").
De data aceasta, pentru fiecare pixel, se vor calcula contributiile la toate momentele Zernike, unul cîte unul. Fermierul trimite un întreg obiect unui singur lucrător si obtine momentele calculate. Pentru aceasta, se trimite mai întâi un header de dimensiune constantă, în care se specifică caracteristicile obiectului (dimensiuni etc.), apoi se trimit efectiv pixelii obiectului - mai exact interiorul dreptunghiului de încadrare. Două posibilităti au fost testate:
(a) Pixelii sunt copiati linie cu linie într-un buffer, apoi trimisi printr-un singur apel socket write. Dacă pachetul de date este prea lung, el va fi oricum împărtit în bucăti, nedepăsindu-se MTU.
(b) Fiecare linie se transmite printr-un apel separat socket write.
Pentru cresterea vitezei de calcul, se poate recurge la mici artificii. Termenii de forma
se pot pre-calcula. Pentru MOMMAX =12, este necesar un vector de 140 de elemente. Mai mult, la ultima implementare (adoptată pentru aplicatie), pentru fiecare pixel, puterile lui r pot fi precalculate una câte una, înlocuind exponentierea cu înmultire si memorând într-un vector cu MOMMAX+1 valori. Aceste două artificii măresc viteza de trei ori !
Experimentele s-au făcut cu ferma de procesoare constând dintr-un farmer si un număr variabil de workers (unul până la patru) de tipuri diferite, conectate prin retea Ethernet. Spre comparatie, se dau rezultatele (în prima coloană) pentru varianta de aplicatie mono-procesor (vezi tabelul).
F - farmer : PC486 DX2 cu Windows for Workgroups, 8MB RAM
r - worker: IBM RS 6000 cu AIX 3.2, 32MB RAM
s, g, a - workers: PC486 DX2 cu Linux., 16 MB RAM
Aceste masini nu au fost dedicate pentru această aplicatie. Timpul lor este partajat cu alte procese: a este gateway si server de domeniu, g este server de ftp si WWW, s este server de postă si r este server pentru lucrul studentilor.
Este important de notat că fiecare obiect are două dimensiuni importante:
Din acest motiv, pentru a efectua măsurătorile de timp, au fost folosite seturi de imagini, fiecare continând 100 de obiecte identice (de fapt, dreptunghiuri mai "pline" sau mai "goale", generate cu Paintbrush):
- trei seturi de obiecte cu aria de 25 pixeli, dar cu dreptunghiuri de încadrare diferite: 5*5, 10*10 si 20*20 pixeli.
- trei seturi de obiecte cu aria de 400 pixeli, cu dreptunghiurile de încadrare de 20*20, 40*40 si 80*80 pixeli.
- un set de obiecte cu dreptunghiul de încadrare de 80*80, dar cu aria de 2800 pixeli.
Astfel, mentinând aria constantă si modificând dreptunghiul de încadrare, variază timpul pentru comunicatii. Mentinând dreptunghiul de încadrare constant si variind aria obiectului, se modifică proportional timpul afectat calculelor.
Se observă din tabel, asa cum ne asteptam, că metoda (a) este mai bună decât (b) în toate situatiile. Pentru pachete mici, diferenta nu este atât de mare la PC-uri, dar este imensă la RS6000. Pe măsură ce dimensiunile obiectelor (deci si a pachetelor de date) cresc, diferentele dintre (a) si (b) scad. În schimb, RS6000 este net superior la viteza calculelor. Mai ciudat este că atunci când fermierul îsi rulează aplicatia mono-procesor (deci în absenta oricărei comunicatii), lucrurile merg mai prost decât în versiunea cu un worker. Aceasta mi-o explic personal prin diferenta de RAM, managementul memoriei si a mesajelor în Windows si faptul că Linux foloseste puterea pe 32 de biti (iar Windows 3.11 pe 16 biti) a procesorului 486. În concluzie, se poate afirma că schimbul de date prin LAN este eficient dacă pachetele sunt apropiate ca dimensiune de maximul admis (MTU). Linux manipulează mai bine pachetele de orice lungimi, dar RS6000 este mai rapid la calcule.