Descrierea problemei şi a metodelor de rezolvare utilizate

Algoritmii de planificare evoluează odată cu arhitecturile paralele şi distribuite. Desi pot fi folosite ca inspiraţie, aceste modele tradiţionale de planificare produc însă în practică planificări Grid nesatisfăcătoare. Motivele pot fi găsite în presupoziţiile care sunt de obicei asociate acestor sisteme tradiţionale: toate resursele se găsesc în cadrul unui singur domeniu administrativ, planificatorul controlează toate resursele, pool-ul de resurse este invariabil, calculele şi datele aferente se găsesc în acelaşi site. Din păcate, toate aceste ipoteze nu mai sunt valabile într-un mediu Grid. Aici, numeroase caracteristici unice determină dificultatea conceperii unor algoritmi de planificare, după cum este explicat în continuare.

Datorită eterogenitaţii resurselor şi diversităţii aplicaţiilor, descoperirea resurselor disponibile şi selectarea unei submulţimi a acestora adecvate aplicaţiei devin esenţiale pentru a obţine performanţa ridicată sau pentru a reduce costurile. Apoi, în cadrul fiecărei submulţimi, resursele sunt notate după dimensiunea memoriei şi puterea de calcul. În final, din listele sortate se selecteză un grup de resurse de dimensiunea dorită. Limita superioară pentru această procedură de căutare exhaustivă este dată şi pretinsă ca acceptabilă în circumstanţele unui Grid.

Optimizarea planificării taskurilor în sistemele distribuite se poate face prin utilizarea algoritmilor genetici.

Algoritmii genetici sunt o familie de modele de rezolvare a problemelor inspirate de teoria evoluţiei. Această clasă de algoritmi codifică soluţiile posibile ale unor probleme specifice într-o structură de date de tip cromozom şi aplică acestor structuri operatori de recombinare, pentru a păstra informaţia utilă. Un cromozom este alcătuit dintr-un set de gene. Valorile pe care le poate lua o genă sunt mulţimi finite de numere întregi, intervale de numere reale, sau chiar structuri complexe de date.

Date de intrare şi ieşire

Algoritmul de planificare bazat pe agloritmi genetici primeste ca date de intrare descrierea unui set de taskuri ce se doreşte a fi planificat în mediul Grid. Pe langă descrierea taskurilor, algoritmul de planificare mai foloseşte şi descrierea resurelor folosite pentru planificare. Descrierile acestor resurse sunt obţinute din serviciul de monitorizare MonALISA. Un exemplu de date de intrare care descrie starea resurselor este specificat în figura de mai sus. Formatul de descriere este XML.

Taskurile sunt descrise tot prin intermediul formatului XML. Un exemplu este dat în figura de mai jos. Un fişier XML de descriere poate conţine oricat de multe taskuri care vor forma un meta-task.

Rezultatul planificării este dat sub forma unor cereri de execuţie a unor taskuri de către resursele gestionate. Cererile de execuţie sunt adresate unui planificator local, care asigură managementul resursei respective. Taskurile sunt trimise spre execuţie prin lansarea unei comenzi care indică nodul căruia i-au fost asignate.

Implementarea în mediul Grid

Justificare

Componentele arhitecturii de planificare implementate pentru medii grid au ca rol descoperirea resurselor disponibile, rularea algoritmului de planificare, execuţia şi monitorizarea evoluţiei task-urilor în sistemul distribuit.

Algoritmul de planificare – partea centrala a întregului sistem – a fost dezvoltat pe baza modelelor de optimizare folosind algoritmi genetici. În construcţia modelului, sarcinile trebuie să respecte restricţii referitoare la timpii de execuţie, la cerinţele de viteză de procesare şi de memorie pentru sistemul pe care aceasta va rula, ţinandu-se totodată cont şi de ordonarea în timp a sarcinilor.

Pe langă componenta de planificare, componentele funcţionale ale sistemul, care interacţionează cu planificatorul sunt: Serviciul de Cereri, Serviciul de Monitorizare a Grid-ului, Serviciul de Execuţie, Serviciul de Look-up (descoperire). Descoperirea şi comunicarea dintre agenţi sunt elemente cheie în mediile Grid.

Procesele de decoperire sunt iniţiate de modulul de detecţie şi duc la obţinerea unui planificator distribuit prin creşterea numărului de host-uri implicate în rularea algoritmului genetic.

Soluţia de implementare

Tehnologia JINI a fost dezvoltată ca un set de componente software care furnizează infrastructura necesară pentru unirea serviciilor pe baza unor principii concludente.

În acest sens tehnologia propusă de Sun Microsystems reprezintă un model care suportă şi încurajează dezvoltarea de servicii distribuite cu un grad înalt de fiabilitate şi care pot fi incluse într-un sistem JINI pentru a oferi diverse funcţionalităţi către oricare membru al sistemului.

Arhitectura JINI [4] urmareşte două concepte de bază şi anume protocoale de descoperire-uniune-vizitare (Dicovery-Join-Lookup) şi specificaţii privind modalitatea de concepere a „dispozitivelor” ce urmează să fie înglobate în sistemul JINI.

Protocoalele Discovery-Join-Lookup sunt protocoale interne utilizate de sistemul JINI pentru a realiza înregistrarea şi utilizarea dispozitivelor JINI (de exemplu telefoane celulare) sau a aplicaţiilor software dezvoltate ca servicii JINI.

Procesul de descoperire al serviciilor reprezintă un proces ce urmareşte serviciile vizitate, iar protocolul de descoperire este utlizat atat la client, cât şi de partea serviciilor în sine.

Procesul de unire este un proces ce realizează înregistrarea unui nou serviciu JINI faţă de toate serviciile existente şi vizitate. În acest sens este utilizat ceea ce se numeşte un serviciu Proxy care se comportă ca o „semnătură” pentru serviciul ce urmează a fi adugat în grupul serviciilor deja existente [5].

Cerinţe privind infrastructura Grid

Soluţia nostră de planificare se orientează spre accelerarea convergenţei prin folosirea mai multor Workeri care să planifice acelaşi set de taskuri. Workerii pot să ruleze pe aceleaşi resurse computationale pe care sunt executate taskurile. Algoritmul genetic începe cu initializări diferite pe fiecare Worker şi este imbunătăţit periodic prin inter-schimbul celor mai buni indivizi găsiţi la fiecare generatie. Am eliminat întarzierile introduse de migraţia celor mai buni indivizi prin introducerea unui mecanism de stocare local pe fiecare dintre Workeri, în care sunt depuşi indivizii cei mai buni găsiţi la o generaţie. În acest fel, Workerii mai rapizi nu vor fi nevoiţi să aştepte pentru cei mai putin rapizi ca aceştia să îşi termine execuţia unui pas din algoritm, ci vor folosi indivizii depozitati în coadă la un moment anterior.

Interfaţa de utilizare

O prima varianta a interfeţei de utlizare a planificatorului este prezentată prin intermediul unui set de scripturi care trebuie pornite în linia de comanda. Prima fază este aceea a pornirii serviciului de descoperire. Acest serviciu trebuie să fie pornit la o adresa publică pentru Agenţi şi Brokeri. În a doua fază este pornit un server de HTTP. Server-ul se poate afla pe aceeaşi maşina cu serviciul de descoperire sau la o alta locaţie publica. Urmează pornirea Broker-lui şi aşteptarea setului de task-uri. La pornirea Broker-ului este pusă la dispoziţia utilizatorului o interfaţa grafică pentru selectarea fisierelor de descriere a aplicaţiilor şi pentru vizualizarea rezultatului. Broker-ul comunică cu serviciul de descoperire pentru a primi descrierea resurselor din Grid.

O a doua variantă de interfaţare a aplicaţiei de planificare cu utilizatorul se poate face prin intermediul paginii web unde se afla un demo şi de unde se poate accesa aplicaţia pentru trimiterea în execuţie a unui set de aplicaţii.

Avantaje

Influenta decentralizarii şi implementarii în Grid asupra performantei echilibrarii incarcarii ne-a condus la concluzia ca descentralizarea reprezinta un avantaj pentru problema de planificare. Au fost realizate experimente cu unu, doi, trei sau patru agenţi, luand în considerare media de-a lungul a 10 rulari în fiecare caz. Figura următoare arata rezultatele obţinute de-a lungul a 200 de generatii.

Cresterea numarului de agenţi da rezultatele cele mai bune în termenii accelerării convergentei atunci când rulam algoritmul genetic cu mai putine generatii, mai putin de 100 pe setul de sarcini utilizat. Ne asteptam la acest lucru deoarece GA este un algoritm stocastic, în care fiecare rulare este generata aleator.

Mai multi agenţi inseamna mai multe puncte de plecare pentru ca algoritmul genetic să gaseasca o solutie cât mai apropiata de optim. în timpul cresterii numarului de agenţi, rata de imbunatatire scade. în cazul nostru, beneficiul realizat de patru agenţi faţa de trei este aproape neglijabil deoarece convergenta este deja realizata la generatii mici, sub care sansele de a gasi indivizi optimi sunt foarte scazute, desi pozitive. La generatii mai mari, costul angajarii mai multor agenţi nu este justificat, deoarece algoritmul a convers deja către un optim.

Pragul α = 0.85 este folosit pentru a ilustra accelerarea pentru fiecare situatie. Experimentul cu un agent atinge acest prag la aproximativ 150 de generatii, în timp ce experimentul cu doi agenţi realizeaza o solutie la aceeasi calitatea la aproximativ 74 de generatii. Mai mult, trei agenţi realizeaza o solutie optimă egala la 38 de generatii, iar patru agenţi la 30 de generatii.

Potenţialul de utilizare

Descrierea rezultatelor

Am studiat cresterea performantei realizata prin acest algoritm prîntr-o serie de experimente. O abordare echilibrata este esentiala pentru a obtine timpi de execuţie scurti, acesta fiind unul dîntre obiectivele principale ale programarii. O buna echilibrare inseamna o incarcare aproximativ uniforma a procesoarelor, rezultand în valori apropiate ale timpilor de procesare.

Evaluarea impactului ştiinţific şi social

Din punct de vedere ştiinţific aplicaţia dezvoltată oferă o solutie de optimizare pentru planificatea task-urilor în sistemele distribuite. Impactul ştiinţific este evidenţiat prin dezvoltarea unui algoritm genetic pentru planficare şi a unei arhitecturi distribuite.

Modelul realizat oferă o scalabilitate ridicata, în care un nod de execuţie poate aparea sau poate disparea în orice moment de timp, fara ca acest fapt să afecteze functionalitatea planificatorului. Caracterul distribuit al sistemului realizat oferă, pe langa scalabilitate, şi atribute de performanta ridicata prin cresterea vitezei de execuţie a algoritmului genetic, precum şi o buna toleranta la defecte.