Domeniul c alculul ui paralel este un domeniu în care multe calcule sunt efectuate [602052]

ABSTRACT

Domeniul c alculul ui paralel este un domeniu în care multe calcule sunt efectuate
simultan, care funcționează pe principiul că problemele mari pot fi adesea împărțite în probleme
mai mici, care sunt apoi rezolvate în același timp. Pentru probleme le de calcul care pot fi
împărțit e într-un număr de sub sarcini, dependențele de date di ntre aceste sub sarcini sunt de
obicei descrise prin intermediul unui graf orientat aciclic (DAG – Directed Aciclic Graph) . Un
graf de acest gen se numește graf de sarcin i (taskuri) și se reprezintă printr -o mulțime de noduri
(taskuri) ponderate, interconectate prin muchii de legătură etichetate cu costuri de transfer.
Problema implică de asemenea și un set de resurse, de procesoare, care reprezintă mediul în
care se plani fică, respectiv pe aceste procesoare taskurile vor fi atribuite în funcție de
constrângerile existente. Prin taskuri ponderate înțelegem noduri care au aferente costuri de
execuție în funcție de fiecare resursă.
Pentru a rezolva o astfel de problemă este n ecesar un algoritm de planificare eficient, cu
o performanță optimă definită de modul în care sarcinile sunt distribuite la resursele adecvate.
Un program este declarat a fi cel mai bun în cazul în care oferă o soluție care face uz de resursele
disponibile în mod eficient. Unii algoritmi de planificare îmbunătățesc makespan -ul (timpul
total de execuție), dar provoacă un dezechilibru sever între procesoare.
Domeniile de a plicabilitate ale acestor algoritmi variază de la bioinformatică până la
economie. Aceșt i algoritmi sunt utilizați cu succes în rezolvarea sistemelor de ecuații liniare, a
inversiunilor de matrice, în inginerie, în rezolvarea problemelor de analiză a circuitelor, pentru
procesarea semnalelor audio și a imaginilor, pentru analiza si manipulare a datelor digitale și
discrete, în aplicații din domenii precum muzic a electro -acustică, în convoluția liniară și
reducerea zgomotului non -liniară, imagistica medicală, recunoașterea formelor, chimie
computațională, codurile de rectificare a erorilor , în simulări, în reconstrucția seismică.
Algoritm ii de planificare eficienți sunt importanți pentru obținerea de performanțe înalte
în sisteme le de calcul eterogene. Problema planificării a fost studiat ă intensiv și d iverși
algoritmi au fost propuși în literatu ra de specialitate , în principal pentru sistemele cu proces oare
omogene. Deși există câțiva algoritmi în literatura de specialitate p entru procesoare eterogene,
acești a necesită, de obicei, costuri semnificativ de ridicate de p lanificare și nu pot furniza
programe de bună calitate, cu costuri mai mici.
În această lucrare sunt prezenta ți și implementați trei algoritmi de planificare noi pentru
un număr mărginit de procesoare eterogene, cu obiectivul de a satisface simultan de cererile de
înaltă performanță și de timp de planificare redus, care sunt numiți Algoritmul Heterogeneous
Earliest -Finish -Time (HEFT), Algoritmul Critical -Path-on-a-Processor (CPOP) și Algoritmul
Hybrid Heuristic . Algoritmul HEFT selectează sarcina cu cea mai mare valoare a valorii ran k-
ului upward la fiecare pas și atribuie sarcina selectată la procesor ul care minimizează cel mai
devreme timp de încheiere a execuției , cu o abordare bazată pe inserție. Pe de altă parte,
algoritmul CPOP folosește însumarea valorilor rank-urilor upward și downward pentru
prioritizarea sarcinilor . Algoritmul Hybrid setează priorități nodurilor DAG -ului și utilizează
acest clasament pentru crea grupuri de sarcini care pot fi ulterior programate independent .

Capitolul 1 Introducere

1.1 Motivație

Calcul ul paralel este o formă de calcul în care multe calcule sunt efectuate simultan,
care funcționează pe principiul că problemele mari pot fi adesea împărțite în probleme mai mici,
care sunt apoi rezolvate în același timp. Este folosit pentru a rezolva probleme pe scară largă și
probleme complicate .
Planificare a sarcinilor în rețea este o problemă NP – complet ă, care este folosit ă pentru
a programa o sarcină pe un nod de rețea corespunzător . Unul dintre punctele cheie pentru a
îmbunătăți performanța algoritmului este modul în care sarcinile sunt distribuite la resursele
adecvate. Se necesită o atenție mai mare în cazul în care sarcinile sunt dependente. Un program
este declarat a fi cel mai bun în cazul în care oferă o soluție car e face uz de resursele disponibile
în mod eficient. Unii algoritm i de planificare îmbunătățesc makespan -ul (timpul total de
execuție), dar p rovoacă un dezechilibru sever între procesoare . Algoritm ii de planificare
eficienți sunt importanți pentru obținerea de performanțe înalte în sisteme le de calcul eterogene.
Problema planificării a fost studiat ă intensiv și d iverși algoritmi au fost propuși în literatura de
specialitate , în principal pentru sistemele cu proces oare omogene. Deși există câțiva algoritmi
în literatura de specialitate p entru p rocesoare eterogene, acești a necesită, de obicei, costuri
semnificativ de ridicate de p lanificare și nu pot furniza programe de bună calitate, cu costuri
mai mici.
În cazul în care o problemă de calcul poate fi împărțit ă într-un număr de subac tivități,
dependențele de date di ntre aceste subactivități sunt de obicei descrise prin intermediul unui
graf orientat aciclic (DAG – Directed Aciclic Graph) numit graf de sarcini . Acestea au fost
utilizate pe scară largă în planificarea workflow -urilor pe sisteme dis tribuite . În general, un
workflow științific are o formă unică a grafului datorită designului său, care este realizat special
pentru a îndeplini o sarcină complexă prin paralelismul taskurilor . În scopul de a modela
executarea unu i graf de sarcini pe un si stem de calcul etero gen, sunt atribuit e ponderi nodurilor
și muchiil or. În timp ce ponderile nodurilor denotă efortul de calcul a l unei sub -sarcini,
ponderile muchiilor corespund timpului pentru transferul rezultatelor intermediare prin rețeaua
dintre două resurse . Acest timp este suportat numai dacă sarcinile conectate sunt p lanificate pe
procesoare diferite . Altfel ponderea muchiei este considerat ă a fi zero. Obiectivul planificării
este de a minimiza timpul total de calcul (de asemenea, numit lungime a planificării ). Pentru a
atinge acest obiectiv, un algoritm de planificare trebuie să atribuie sarcinile la resursel e
disponibile și să determine timpii de start a execuției corespunzători . Se urmărește în cazul unui
astfel de pr obleme atribuirea taskurilor ( nodurilor) astfel încât să fie respectate toate
constrângerile solicitate.
În această lucrare sunt implementați doi algoritmi de planificare noi pentru un număr
mărginit de procesoare eterogene, cu obiec tivul de a satisface simultan cererile de înaltă
performanță și de timp de planificare redus, care sunt numiți Algoritmul Heterogeneous

Earliest -Finish -Time (HEFT) ș i Algoritmul Critical -Path-on-a-Processor (CPOP) . Algoritmul
HEFT selectează sarcina cu cea mai mare valoare a valorii rank -ului upward la fieca re pas și
atribuie sarcina selectată la procesor ul care minimizează cel mai devreme timp de încheiere a
execuției , cu o abordare bazată pe inserție. Pe de altă parte, algoritmul CPOP folosește
însumarea valorilor rank-urilor upward și downward pentru prior itizarea sarcinilor. O altă
diferență este în etapa de selecție a procesor ului, care p lanifică sarcini le critice pe procesorul
care minimizează timpul total de execuție a l sarcinilor critice.
Motivația pentru alegerea acestei teme este dorința de a aprofun da domeniul calculului
paralel, de a înțelege mai bine modul de organizare și de funcționare a unei astfel de probleme
având în vedere faptul că este un domeniu larg răspândit în zilele noastre, cu numeroase și
diverse aplicații în lumea reală, însă totoda tă un domeniu în care mai sunt multe aspecte de
parcurs, de înțeles, de fundamentat.
Am ales acești algoritmi deoarece sunt cei mai uzuali folosiți la comparare atunci când
se propune o nouă strategie de planificare , dar și datorită faptului că cei mai mu lți algoritmi
existenți în literatura de specialitate sunt propuși pentru sistemele cu procesoare omogene . Deși
există câțiva algoritmi în literatura de specialitate p entru procesoare eterogene, acești a necesită,
de obicei, costuri semnificativ de ridicate de planificare și nu pot furniza programe de bună
calitate, cu costuri mai mici. Una dintre diferențe le di ntre procesoarele omogene și cele
eterogene este faptul că cele eterogene sunt conec tate prin rate de transfer. Scopul principal al
acestor doi algor itmi este de a oferi o bună calitate a planificării la costuri reduse.

1.2 Structura tezei
Lucrarea est e structurată în cinci capitole. În capitolul întâi , Introducere, am descris
succint domeniul din care face parte problema studiată pe parcursul lucrării și motivația alegerii
acestei teme.
În capitolul al doilea, care trasează principalele obiective ale planificării taskurilor, este
descrisă pe larg problema abordată, domeniul din care face parte și tipul de date cu care
operează, respectiv grafuri aciclice direcționate (DAG). Tot acest capitol sunt prezentate
caracteristicile datelor, tipurile de taskuri, planificarea acestora, modul de reprezentare al DAG –
urilor. Apoi este explicată generarea acestora, parametrii de care se ține cont, tipurile cele mai
semn ificative de grafuri generate, evaluarea acestor grafuri generate. În continuare sunt
subliniate o parte din problemele care apar atunci când se alege un algoritm și analizați câțiva
dintre cei mai uzuali algoritmi de planificare bazați pe liste de planifi care.
În capitolul trei sunt descriși algoritmii implementați în cadrul lucrării : Hybrid
Heuristic, BMCT, HEFT și CPOP, precum și alte versiuni ale acestor algoritmi care oferă
rezultate mai avantajoase sau nu, după caz.
Capitolul patru prezintă structura aplicației, respectiv cla sele, datele de test , o schiță a
unei posibile planificări și rezultatele obținute în urma testelor pentru fiecare algoritm, testat
pentru fiecare graf în parte .
Capitolul cinci, cel final, conține concluziile constatate în urma i mplementării și testării
algoritmilor, alături de câteva direcții viitoare, posibile îmbunătățiri și revizuiri ale aplicației.

Capitolul 2 – Planificarea taskurilor

Problema de planificare a taskurilor presupune alocarea unor taskuri la resurse
(procesoa re) astfel încât taskurile să fie executate într -o ordine stabilită pe acele resurse.
Problema planificării este una dintre etapele de bază pentru exploatarea eficientă a capacităților
sistemelor de calcul distribuite și este o problemă NP -completă. Proble ma de planificare a
taskurilor este o problemă NP -completă deoarece este greu de găsit o soluție optimă într -un
timp polinomial, ceea ce sugerează folosirea euristicilor pentru rezolvarea unei astfel de
probleme.

2.1 Problema de planificare este o problemă NP -completă

Există diferite tipuri de probleme de calcul, dar din punct de vedere al teoriei
complexității computaționale, este mai ușor să ne concentrăm asupra problemelor de decizie,
adică problemele în care răspunsul este fie DA, fie NU. Există și alte t ipuri de probleme de
calcul, dar cele mai comune dintre întrebările referitoare ele pot fi reduse la întrebări similare
cu privire la problemele de decizie. Problemele de decizie sunt foarte simple.
Putem identifica o problemă de decizie prin subsetul de intrări, care au ca răspuns DA.
Acest lucru simplifică notația și ne permite să scriem x ∈Q în loc de Q (x) = DA și x ∉Q în
loc de Q (x) = NU. Ne referim la răspunsul DA dintr -o ipoteză de intrare ca la acceptarea
ipotezei și la răspunsul NU ca la respin gerea ipotezei.
Uneori nu știm nici un fel de metodă eficientă de a găsi răspunsul la o problemă de
decizie, însă dacă cineva ne spune răspunsul și ne oferă o dovadă (proof/certificate/witness)
putem verifica în mod eficient dacă răspunsul este corect prin verificarea dovezii pentru a vedea
dacă acesta este o dovadă validă. Aceasta este ideea definitorie a clasei NP (Nondeterministic
polynomial time) de complexitate.
Cu alte cuvinte, NP este clasa de probleme care au verificatori eficienți, și anume, există
un algoritm de timp polinomial care poate verifica dacă o soluție dată este corectă.
Dacă dovada este prea lungă, nu este foarte utilă, deoarece poate dura prea mult doar
pentru a citi dovada darămite pentru a verifica dacă aceasta este validă. Vrem ca ti mpul necesar
pentru verificare să fie rezonabil în comparație cu dimensiunea ipotezelor inițiale, nu cu
dimensiunea dovezii date. Aceasta înseamnă că ceea ce ne dorim cu adevărat nu sunt dovezi
lungi arbitrare, ci dovezi scurte. Timpul de funcționare al ve rificatorului este polinomial
depinzând de mărimea ipotezelor de intrare inițială, și atunci se poate citi doar o parte
polinomială a dovezii. Deci, prin dovezi scurte (short proofs) ne referim la dimensiuni
polinomiale [7].
Problemele NP -complete sunt ace lea care sunt în același timp și NP și NP -grele (NP –
hardness se referă la o clasă de probleme despre care afirmăm că sunt „dificile”). În urma
analogiei noastre, problemele NP -complete sunt în același timp "ușoare precum problemele cu
mai multe posibilităț i de alegere a soluției" cât și "cele mai grele dintre toate ca problemele de
cuvinte".

Din cauza spațiului mare de căutare problema nu poate fi mereu rezolvată folosind
abordări complete și este adecvată pentru folosirea euristicilor, care obțin rezultate suboptimale,
dar într -un timp mai scurt.
Pe scurt, problemele NP:
 sunt probleme care se pot verifica rapid
 includ probleme de căutare.
Dacă privim problema de planificare ca o problemă de căutare atunci calitatea soluției
oferite de un algoritm de planifi care poate fi măsurată prin makespan (lungimea planificării),
numărul de apariții a celei mai bune planificări, timpul de execuție al algoritmului, etc.
Prin planificare taskurilor dintr -un workflow înțelegem distribuirea sarcinilor unui graf,
pe procesoar e într -un mod cât mai adecvat principiului de minimizare a makespan -ului. Ce se
urmărește în cazul unui astfel de probleme este atribuirea acestora astfel încât să fie respectate
toate constrângerile solicitate.
Măsurile utilizate pentru evaluarea unei pla nificări sunt următoarele:
 makespan (timp total de execuție a tuturor sarcinilor de pe toate procesoarele)
 valoarea medie (notată cu M -Mean Value) este bazată pe media calculului fiecărui timp
de execuție pe fiecare procesor (pentru a asigna o valoare fie cărui nod) și pe media
costului de comunicație dintre două taskuri (pentru a asigna o valoare fiecărei muchii)
 valoarea mediană (notată cu ME -Median Value) este bazată pe valoarea mediană
respectivă
 cea mai rea valoare (notată cu W -Worst Value) este bazată pe cea mai rea valoare a unui
cost de execuție, care este de fapt valoarea maximă a timpului de execuție a unui nod,
pentru a atribui fiecărui nod o valoare respectivă. În cazul muchiilor, ponderea unei
muchii este reprezentată de costul comunicării ce co respunde acelor procesoare pe care
fiecare dintre noduri are timpul de execuție maxim
 cea mai bună valoare (notată cu B -Best Value) este bazată pe cea mai bună valoare a
costului de execuție, care este valoare minimă a costului de execuție, în timp ce valo area
unei muchii este reprezentată de costul comunicării ce corespunde acelor procesoare pe
care fiecare dintre noduri are timpul de execuție minim
 SW-Simple Worst Value este bazată pe cea mai rea valoare atât pentru costul de calcul
cât și pentru costul d e comunicare (respectiv, costul maxim de execuție și costul maxim
de comunicare)
 SB-Simple Best Value este bazată pe cea mai bună valoare atât pentru costul de calcul
cât și pentru costul de comunicare (respectiv, costul minim de execuție și costul minim
de comunicare).
Având în vedere că planificarea generală a DAG -urilor este NP -completă, există multe
eforturi de cercetare care au propus euristici pentru problema de planificare a activității. O mare
varietate de abordări este utilizată pentru a rezolva pr oblema de planificare a DAG -urilor; cele
mai multe dintre ele vizează numai procesoarele omogene.
Diverse seturi de resurse interconectate de o rețea de mare viteză oferă o nouă platformă
de planificare, numită platforma sistemelor heterogene, care suportă executarea aplicațiilor

distribuite și paralele. Un sistem eterogen poate fi definit ca o serie de diferite resurse de sistem,
care pot fi locale sau distribuite geografic, utilizate pentru a executa aplicații intensive de calcul.
Eficacitatea executării aplicațiilor paralele pe sisteme eterogene depinde în mod critic
de metodele utilizate pentru a programa task -urile unei aplicații paralele. Obiectivul este de a
minimiza timpul de finalizare globală sau așa numitul makespan.
Problema de planificare a sar cinilor pe sisteme eterogene este mai complexă decât cea
pentru sistemele de calcul omogene, din cauza diferitelor rate de execuție între procesoare și,
eventual, a diferitelor rate de comunicare dintre diferite procesoare.
O reprezentare populară a unei a plicații este graful aciclic direcționat (Directed Aciclic
Graph -DAG), care include caracteristicile unui program de aplicație, cum ar fi timpul de
execuție a sarcinilor, dimensiunea de date pentru a comunica între sarcini și dependențele dintre
sarcini.
Obiectivul de planificare este de a atribui sarcinile pe procesoare și ordonarea executării
lor, astfel încât cerințele de precedență ale sarcinilor să fie satisfăcute și lungimea programării
rezultată (sau makespan) să fie minimă.
2.1.1. Tipuri de taskuri
Taskur ile de planificare pot fi independente sau interdependente. În cadrul acestei
lucrări am ales să tratăm problema planificării taskurilor interdependente.
Taskuri independente
Taskurile independente sunt taskuri care nu depind unele de altele, între care nu există
date transferate și dependențe de date, iar preempțiunea nu este permisă; cu alte cuvinte,
sarcinile nu își pot schimba resursa căreia i -au fost atribuite. Un exemplu de astfel de taskuri
este planificarea unui orar.
Taskuri interdependente
Taskuri le dependente sunt taskuri care depind de execuția unor altor taskuri părinte.
Astfel de taskuri se regăsesc în workflow -uri.
Caracteristicile unui task din punct de vedere al problemei de planificare sunt:
 timp de execuție: timpul necesar executării nodul ui respectiv pe fiecare dintre resursele
existente
 cost mediu de execuție: media timpilor de execuție ai fiecărui nod pe toate resursele
 date de transfer: între noduri sunt precizate anumite costuri ale datelor transferate
 memorie
 EFT (Earliest Finish Tim e): cel devreme timp de încheiere a execuției al fiecărui nod pe
fiecare procesor; așadar, fiecărui nod îi corespunde un set de valori pentru toate resursele
 EST (Earliest Start Time): cel mai devreme timp de execuție de pornire; analog, fiecărui
nod îi co respunde un set de valori pentru toate resursele
 pred(n i): setul care cuprinde predecesorii imediați ai nodului ni într-un graf dat. Un nod
fără predecesori este numit nod de intrare , n-entry. Dacă un DAG are mai multe noduri

de intrare, grafului i se va a dăuga un nod de intrare fals, care are ponderea 0 și este
conectat de restul nodurilor de intrare prin muchii al căror cost de comunicare este 0.
 succ(n i): setul care cuprinde succesorii imediați ai nodului ni. Un nod fără succesori este
numit nod de ieșir e, n-exit. Asemenea nodului de intrare, dacă un DAG are mai multe
noduri de ieșire, grafului i se va adăuga un nod de ieșire fals, care are ponderea 0 și este
conectat de restul nodurilor de ieșire existente prin muchii al căror cost de comunicare
este 0.

Caracteristici planificării unui astfel de graf de tip DAG sunt:

 makespan: reprezintă timpul final la care își încheie execuția nodul de ieșire din cadrul
grafului planificat și este definit astfel:
makespan = AFT(n -exit)
unde AFT(nexit) este Timpul Ac tual de Terminare (Actual Finish Time) a execuției
nodului de ieșire.
 Critical Path(CP): drumul critic al unui DAG este cel mai lung drum din graf pornind
de la nodul de intrare (n -entry) și ajungând la nodul de ieșire (n -exit). Lungimea acestui
drum, |CP| , este egală cu suma timpilor de execuție ale nodurilor aflate pe acest drum și
a costurilor de comunicare dintre taskurile drumului critic. Valoarea lungimii drumului
critic, |CP|, reprezintă limita inferioară a makespan -ului.

2.2 Reprezentare
Un model de si stem de planificare constă dintr -o aplicație, un mediu țintă de planificare
și de un criteriu performant de planificare.
Aplicația este reprezentată de un graf aciclic direcționat, G=(V,E) , unde V este setul de
noduri, iar E setul de muchii dintre noduri.
Mediul țintă de planificare se referă la o mulțime P={ p 1, p2, … ,p n } de procesoare
heterogene/diferite.
DAG -urile (Directed Aciclic Graph) sunt grafuri în care nodurile de intrare și de ieșire
nu coincid, iar sensul arcelor/muchiilor este unic și prestab ilit. Acestea au fost utilizate pe scară
largă în planificarea workflow -urilor pe sisteme distribuite. Cu alte cuvinte, în cazul în care o
problemă de calcul poate fi împărțită într -un număr de subactivități, dependențele de date dintre
aceste subactivităț i sunt de obicei descrise prin intermediul unui graf orientat aciclic (DAG)
numit și graf de sarcini/taskuri.
Model de reprezentare a DAG -urilor:
DAG -urile sunt adesea folosite pentru a modela tipuri diferite de structuri din
informatică și matematică. În tr-un DAG, relația accesibilității dintre sarcini formează o ordine
parțială, precum și orice ordine parțială finită poate fi reprezentată ca un DAG prin utilizarea
accesibilității. DAG -urile sunt adesea folosite pentru a modela procesele în care informați ile
fluctuează într -o direcție coerentă prin intermediul unei rețele de procesoare.

În cadrul unui graf de tip DAG, taskurile pot fi independente (independența a două
taskuri înseamnă obținerea aceluiași rezultat indiferent dacă cele două taskuri sunt exec utate
secvențial în orice ordine sau în paralel; pe lângă restricțiile legate de ordinea de execuție,
conflictele de acces la resursele partajate limitează independența între două sau mai multe
taskuri) sau interdependente. În cadrul lucrării ne vom axa do ar pe studiul și planificarea
taskurilor interdependente.
Modelul definiției pe care îl vom folosi în această analiză este prezentat mai jos:
Un DAG – G = (V,E,w,c) – reprezintă aplicația care urmează să fie planificată
 V = {v i : i = 1,…,N} – reprezint ă setul de noduri (taskuri)
 E = {e ij : dependențele de date dintre nodul n i și nodul n j }
 w(n i) – reprezintă costul folosit în calcul al nodului n i, adică media timpilor săi de
execuție aferenți resurselor folosite
 (eij) – reprezintă costul comunicării muchiei dintre nodul n i și nodul n j.
Relațiile dintre sarcinile grafului sunt exprimate ca și constrângeri de precedență.
Constrângerile de precedență impun ordinea de execuție a nodurilor conform dependențelor lor
(grupate în muchii de comunicare eticheta te cu (e ij) – costul transferului de date dintre noduri).
Un nod poate începe să se execute numai după ce toți predecesorii săi și -au terminat execuția.
Generarea unui DAG :
Când se genereză modele de DAG -uri se iau în considerare o serie de caracteristici ale
grafului cum ar fi numărul de noduri, raportul comunicare/calcul (CCR – Comunication
Computation Ratio – definit ca un raport dintre media costului muchiei și media costului
nodului), numărul de sarcini per nivel. Pe lângă acestea trebuie luate în con siderare și cele
specifice problemei curente, după caz.
Majoritatea programelor care generează grafuri aleatoare folosesc diferiți parametrii
pentru a descrie caracteristicile grafului. Parametrii care definesc forma DAG -ului sunt:
• n: numărul de noduri d e calcul în DAG (sarcinile aplicației);
• fat: acest parametru afectează înălțimea și lățimea DAG -ului. Lățimea în fiecare nivel
este definită printr -o distribuție uniformă, cu o medie egală cu fat.√𝑛. Înălțimea, sau numărul
de niveluri, este creată pân ă când n sarcini sunt definite în DAG. Lățimea este numărul maxim
de sarcini care pot fi executate simultan. O valoare mică va duce la un DAG subțire (de
exemplu, chain – lanțul), cu un paralelism scăzut, în timp ce o valoare mare induce un DAG mai
complex (de exemplu, fork -join), cu un grad ridicat de paralelism;
• densitate : determină numărul de muchii dintre două niveluri ale DAG -ului, cu o
valoare scăzută conducând la câteva muchii și o mare valoare la mai multe muchii;
• regularitate : regularitatea dete rmină uniformitatea numărului de sarcini în fiecare
nivel. O valoare scăzută indică faptul că nivelurile conțin numere diferite de sarcini, în timp ce
o valoare mare indică faptul că toate nivelurile conțin un număr similar de sarcini;
• salt: indică faptu l că o muchie poate ajunge de la nivelul l la nivelul l + salt. Un salt
de 1 este o conexiune obișnuită între două nivele consecutive [8].

Pentru generarea de grafuri aleatoare există diferiți algoritmi: Descompunerea LU,
rezolvatorul de ecuație Laplace, A lgoritmul Stencil și Transformarea Fast Fourier. Câteva
modele de grafuri sunt următoarele:
 Grafuri aleatoare. Sunt generate folosind următorii parametri:
 numărul de noduri
 raportul comunicare/procesare (CCR)
 intervalul din cadrul căruia valorile costurilo r de comunicare și procesare
sunt selectate aleatoriu
Cu toate acestea, pentru performanța obținută de algoritmii de planificare pe grafurile
sintetice aleatoare se acordă mai puțină importanță, datorită formei grafului și tipului de sarcini
care îl formea ză. În general, un workflow științific are o formă unică a grafului datorită
designului său, care este realizat special pentru a îndeplini o sarcină complexă prin paralelismul
taskurilor. DAG -urile multor aplicații din lumea reală sunt bine echilibrate, ia r paralelismul
ajunge la un nivel ridicat. Mai mult decât atât, în cadrul acestor aplicații poate fi observat un
număr mic de operații unice.
 Grafuri echilibrate. Generarea grafurilor complet echilibrate a fost realizată luând în
considerare observațiile c onstatate la grafurile generate aleator. Pentru aceasta, sunt adăugați
doi parametri noi: numărul de secțiuni paralele, pentru care numărul de sarcini concurente este
selectat aleator ținând cont de numărul rămas de sarcini din totalul acestora și numărul minim
de nivele.

 Grafuri cu nivele de o complexitate maximă preselectată a legăturilor. Grafurile cu
o complexitate prestabilită a legăturilor sunt utilizate în euristicile de evaluare a planificărilor.
Această tehnică definește construirea sarcinilor g rafului, nivel cu nivel. Pentru fiecare nivel, cu
excepția primului, se caută definirea unui număr de părinți pentru fiecare nod, care este mai mic
decât limita prestabilită pentru muchiile din nivelul anterior. Pentru construirea grafului se iau
în consid erare următorii parametri definiți: numărul de noduri, numărul de niveluri de activitate,
puterea de procesare, complexitatea muchiilor și costurile de comunicare. Folosind această
metodă, cu mici modificări, cum ar fi restricția ca grupurile de noduri din tr-un nivel să aibă un
singur copil comun în nivelul următor sau ca grupurile de noduri dintr -un nivel mai inferior să
aibă un singur părinte comun în nivelul anterior, pot fi generate de asemenea modele de grafuri
cu arbori.

 Algoritmi de calcul paralel utilizați în realizarea de corespondențe între grafuri. În
continuare detaliem grafurile de sarcini reprezentative pentru diferite tipuri de algoritmi de
calcul paralel. Aceste tipuri sunt alese având în vedere numărul de grafuri cu aplicații reale.
Luăm în considerare cele mai frecvente tipuri de algoritmi folosiți în literatura de specialitate,
cum ar fi: algoritmul LU -descompunere, algoritmul Laplace, algoritmul FFT (Fast Fourier
Transform), algoritmul Stencil. În toate aceste cazuri, generarea de grafu ri de mărimi diferite
este realizată prin varierea numărului de noduri și a valorilor CCR. Deși algoritmii originali
necesită, pentru unele aplicații, aceleași costuri pentru toate nodurile și toate muchiile sau doar
pentru o parte dintre acestea, costuril e sunt selectate aleator dintr -un interval dat și doar
structura grafului este limitată la un anumit model în momentul generării.

Evaluarea DAG -urilor
Este importat ca în cazul DAG -urilor generate să fie luate în considerare un set de
măsurători de evaluar e a DAG -urilor pentru a oferi o modalitate de clasificare a euristicilor de
planificare pe baza caracteristicilor diferitelor aplicații. Aceste măsurători sunt detaliate în
continuare:
1. Granularitatea
În funcție de granularitatea sa, care este o măsurătoare a raportului dintre comunicare și
calcul, un graf poate fi aspru granulat (calculul domină comunicarea) sau fin granulat
(comunicarea domină calculul). Granularitatea unui graf este definită astfel:
g(G) = min(cn(x)/max(c(x,i)))
unde cn(x) – reprezintă c ostul calculului nodului x
c(x,j) – costul comunicării dintre nodul x și nodul j
x,j – reprezintă nodurile și pot lua valori cuprise între 1 și numărul total al nodurilor
În [9] s -a concluzionat că: termenul de „limită I/O” este echivalent cu granularitate a
fină, iar termenul de „limită a CPU” este echivalentul granularității dure. Intuitiv un graf este
de o granularitate aspră dacă cantitatea de calcul este relativ mai mare decât comunicarea.
2. CCR (Communication to Computation Ratio)
Conform literaturii de specialitate, o definiție a CCR este exprimată ca și costul mediu
al muchiei față de costul mediu al nodului ( raportul dintre acestea două). Cu ajutorul raportului
CCR putem evidenția importanța legăturilor de comunicare din cadrul unui graf care determin ă
într-un mod puternic comportamentul planificării. Pe baza lui CCR, putem clasifica grafurile
în:
 CCR < 1 – graf de granularitate aspră
 CCR = 1 – graf mix
 CCR > 1 graf de granularitate aspră
CCR= ∑ 𝑐(𝑥,𝑗)∗𝑛𝑢𝑚 ă𝑟𝑢𝑙_𝑑𝑒_𝑛𝑜𝑑𝑢𝑟𝑖 𝑥,𝑗
∑𝑐𝑛(𝑥)∗𝑛𝑢𝑚 ă𝑟𝑢𝑙_𝑑𝑒_𝑚𝑢𝑐 ℎ𝑖𝑖 𝑥
unde cn(x) – reprezintă costul calculului nodului x
c(x,j) – costul comunicării dintre nodul x și nodul j
x,j – reprezintă nodurile și pot lua valori cuprise între 1 și numărul total al nodurilor
3. Gradul de constrâ ngeri
Gradul de constrângeri (Constraint Degree – CD) al unui DAG este definit ca numărul
de conexiuni dintre noduri. Gradul de constrângeri poate fi: scăzut, mediu sau ridicat. Valorile
care separă aceste trei clase sunt recomandate a fi alese având în ved ere structura rețelei de
resurse. O variație a măsurii gradului de constrângeri poate fi considerată ca densitate a unui
DAG, care determină numărul de dependențe între nodurile a două nivele consecutive. Desigur,
această măsurătoare poate fi aplicată doar la DAG -uri pe bază de nivele.

4. Gradul de paralelism
Un alt parametru important care trebuie luat în considerare este gradul de paralelism al
grafului (Parallelism Degree – PD), care este numărul maxim de sarcini ce pot fi executate
simultan. Folosind aceast ă valoare, DAG -urile pot fi clasificate în felul următor: o valoare mică
pentru PD indică un paralelism redus al sarcinilor, iar o valoare mare indică un grad ridicat de
paralelism între sarcinile DAG -ului. Acestă valoare este calculată ținând cont de cons trângerile
dintre sarcini. Asemenea lui CD, valoarea care separă cele două clase trebuie să fie aleasă
corespunzător cu numărul de procesoare pe care vrem să planificăm aplicația curentă [9].
Cum evaluăm performanța unui algoritm de planificare?
Un studiu de evaluare a performanței și de comparare ar trebui să ofere răspunsuri la
următoarele întrebări:
 Care sunt măsurile importante de performanță?
Performanța unui algoritm de planificare a taskurilor unui graf de tip DAG este de obicei
măsurată în termeni de calitate a planificării (durata totală a programului) și timpul de
funcționare a algoritmului de planificare. Uneori, numărul de procesoare țintă alocate este de
asemenea luat ca parametru de performanță. Una dintre probleme este că, de obicei, există u n
compromis între cele două prime măsuri de performanță; respectiv, eforturile de a obține o
soluție mai bună suportă adesea o complexitate de timp mai mare. În plus, folosind mai multe
procesoare poate conduce, eventual, la o soluție mai bună. O altă prob lemă este că cei mai mulți
algoritmi sunt evaluați folosind probleme de mici dimensiuni și nu se știe cum reacționează
algoritmii față de dimensiunea problemei.
 Ce parametri ai problemei afectează performanța?
Performanța unui algoritm de planificare a t askurilor unui graf de tip DAG, în general,
tinde să încline spre structura graficului. În plus, și alți parametri, cum ar fi raportul de
comunicare -calcul, numărul de noduri și de muchii din graf și numărul de procesoare țintă,
afectează performanțele unu i astfel de algoritm. Astfel, este important să se măsoare
performanța algoritmilor de acest tip prin testarea lor cu fermitate prin diferite intervale ale
acestor parametri.
 Ce criterii de referință ar trebui utilizate?
Nu există nici un set de obiective de referință care pot fi considerate ca un standard
pentru a evalua și compara diferiți algoritm de planificare a taskurilor unui graf de tip DAG pe
o bază unită. Cea mai comună practică este de a utiliza grafuri aleatoare. Utilizarea grafurilor
de sarcin i derivate din diferite aplicații paralele, este de asemenea comună. Cu toate acestea, în
ambele cazuri, nu există încă nici un standard care poate oferi un set robust de cazuri de testare.
Prin urmare, este nevoie de un set de repere care sunt reprezentat ive pentru diverse tipuri de
cazuri de testare sintetice și reale. Aceste cazuri de testare ar trebui să fie diverse, fără a fi
părtinitoare față de o anumită tehnică de planificare și ar trebui să permită variații în parametri
importanți.
 Cum variază perf ormanța algoritmilor de planificare a taskurilor unui graf de tip
DAG?

Din moment ce majoritatea algoritmilor se bazează pe tehnici euristice, limitele privind
nivelurile de performanță și variațiile din soluția optimă nu sunt cunoscute. În plus, media di n
cel mai rău, respectiv cel mai bun caz de performanță al acestor algoritmi este necunoscută.
Deoarece nu toți algoritmii au structuri identice, aceștia trebuie să fie separați și evaluați în
cadrul diferitelor categorii.
 De ce unii algoritmi au performan țe mai bune?
Deși în trecut au fost realizate unele comparații calitative și cantitative ale algoritmi de
acest tip, s -au prezentat în principal rezultatele experimentale fără a da o justificare de ce unii
algoritmi funcționează bine, iar alții nu. Studii le anterioare au fost de asemenea limitate la câțiva
algoritmi și nu au făcut o evaluare cuprinzătoare. Filozofiile de proiectare și caracteristicile
diferiților algoritmi trebuie înțelese pentru a evalua meritele și deficiențele lor. Analizele
calitative pot conclude o serie de orientări viitoare pentru proiectarea unor euristici chiar mai
bine.
Există numeroase variații ale metodelor de atribuire a priorităților și de menținere a listei
de noduri pregătite pentru planificare, precum și criterii pentru sel ectarea unui procesor pentru
a găzdui un nod. Mai jos sunt descrise câteva dintre aceste variante și se arată faptul că acestea
pot fi utilizate pentru a caracteriza majoritatea algoritmilor de planificare.
Alocarea de priorități nodurilor
Cele două atribu te principale pentru atribuirea priorităților sunt t-level (top level -nivelul
superior) și b-level (bottom level -nivelul inferior). Nivelul -t al unui nod n i este lungimea celui
mai lung drum de la un nod de intrare la n i, (excluzând n i). Aici, lungimea unu i drum este suma
tuturor ponderilor nodurilor și a muchiilor de -a lungul drumului. Nivelul -t al unui nod n i este
extrem de corelat cu valoarea EFT a lui n i, notată cu T s (ni), care se determină după ce n i este
atribuit unui procesor. Nivelul -b al unui nod ni este lungimea celui mai lung drum de la nodul
ni la un nod de ieșire: Nivelul -b al unui nod este delimitat de lungimea drumului critic. O cale
critică (Critical Path -CP) a unui DAG este o cale de la un nod de intrare la un nod de ieșire, a
cărui lungime este maximă. Diferiți algoritmi utilizează nivelul -t și nivelul -b în moduri diferite.
Unii algoritmi atribuie o prioritate mai mare unui nod cu un nivel -t mai mic în timp ce ați
algoritmi atribuie o prioritate mai mare unui nod cu un nivel -b mai mare. În general, planificarea
într-o ordine descrescătoare a nivelului -b tinde să planifice mai întâi nodurile drumul critic, în
timp ce planificarea într -o ordine crescătoare a nivelului -t tinde să planifice nodurile într -o
ordine topologică.
Inserție vs. Non -Inserție
La determinarea timpului de începere a execuției unui nod pe un procesor P, unii
algoritmi iau în considerare numai planificarea unui nod după ultimul nod de pe procesorul P.
Alți algoritmi iau în considerare și alte intervale de timp, cele inactiv e de pe P și pot introduce
un nod între două noduri deja planificate.
Bazare -pe-Drum -Critic vs Fără -Bazare -pe-Drum -Critic
Algoritmii pe bază de drum critic determină o ordine de planificare sau dau o prioritate
mai mare unui nod de pe drumul critic (criti c-path) (CPN -Critical Path Node). Algoritmii care
nu sunt pe bază de drum critic nu dau preferințe speciale nodurilor CPN; ei atribuie priorități,
pur și simplu, pe baza nivelurilor sau pe baza altor atribute ale nodurilor.

Listă statică vs Listă dinamică
Setul de noduri pregătite de execuție este adesea menținut ca o listă „de gata”. Inițial,
lista „gata” include doar nodurile de intrare. După ce un nod este planificat, nodurile eliberate
de nodul planificat sunt inserate in listă astfel încât lista este sortată descrescător în ordinea
priorităților nodurilor. Lista poate fi menținută în două moduri: o listă „gata” este statică dacă
este construită înainte de începerea planificării și rămâne aceeași pe tot parcursul procesului de
planificare. O listă „gata ” se numește dinamică dacă este rearanjată conform priorităților
nodurilor în schimbare.
Greedy vs. Non -Greedy
În atribuirea unui nod la un procesor, cei mai mulți algoritmi de planificare încearcă să
minimizeze timpul de start al unui nod. Aceasta este o strategie „greedy”. Cu toate acestea, unii
algoritmi nu minimalizează neapărat timpul de start al unui nod, ci iau în considerare alți factori.
Complexitatea timpului
Complexitatea timpului unui algoritm de planificare a taskurilor unui graf de tip DAG
este de obicei exprimată în termeni de: număr de noduri, v, număr de muchii, e, și număr de
procesoare, p. Cele mai importante etape ale unui algoritm includ traversarea grafului și o
căutare de goluri pe procesoare pentru a plasa un nod. Asignarea priorită ților în mod static în
general rezultă într -un timp de complexitate mai mic în timp ce atribuirea dinamică a
priorităților duce inevitabil la o complexitate mai mare de timp a algoritmului de planificare.
Backtracking -ul poate suporta o complexitate foarte mare de timp și, prin urmare, nu este de
obicei luat în considerare [13].
Codificarea problemei
O aplicație este reprezentată de un graf aciclic direcționat, G=(V,E), unde V este setul
de noduri, iar E setul de muchii dintre noduri. Fiecare muchie (i,j) ϵ E reprezintă constrângerea
de precedență, nodul n i ar trebui să își încheie execuția înainte ca nodul n j să își înceapă execuția.
Într-un graf dat un nod fără nici un părinte este numit „entry task” -nod de intrare, iar
un nod fără nici un copil este numit „exit task” -nod de ieșire. Unii algoritmi de planificare a
task-urilor pot necesita grafuri cu câte un singur nod de intrare și de ieșire. Dacă există mai
multe noduri de intrare/ieșire, acestea sunt conectate la un alt nod având costul zero numit
„pseudo -task” prin muchii de cost zero, ceea ce nu afectează planificarea.
Sistemul de planificare constă dintr -un set P de p procesoare heterogene, conectate într –
o topologie complet conectată în care toate comunicațiile dintre procesoare sunt presupuse spre
a fi efectuate fără afirmație. În modelul de față se presupune de asemenea că costul calculului
poate fi suprapus de cel al comunicării. În plus, execuțiile sarcinilor sunt asumate a fi non –
preemptive. W este o matrice de dimensiuni v × p în care sunt reținu te valorile costurilor
execuțiilor, unde fiecare wi,j reprezintă timpul estimativ al execuției task -ului ni pe procesorul
pj. Înainte de planificare, nodurilor li se atribuie costuri medii de execuție. Costurile medii de
execuție ale task -uilor sunt utili zate în ecuațiile referitoare la prioritățile nodurilor.
Costul mediu de execuție al fiecărui nod ni este definit astfel:

Data este o matrice care reține dimensiunile datelor transferate(în bytes) între noduri.
Ratele datelor transferate (în bytes/secundă) între procesoare sunt stocate într -o matrice de
dimensiuni p × p, numită rate.
Costul comunicării muchiei (i,j) care este aferent transerului de date de la task -ul ni
(programat pe procesorul pm) la task -ul nj (programat pe procesorul pn), este definit de
ci,j= data(n i ; nj)/rate(p m ; pn)

Dacă ambele noduri n i și n j sunt programate pe același procesor, atunci p m = p n, deci c i,j devine
zero, din moment ce costul comunicării intra -procesor este neglijabil față de costul comunicării
interprocesor.
Costul mediu de comunicare al unei muchii este definit de
𝑐𝑖,𝑗= data(n i ; nj)/𝑟𝑎𝑡𝑒

unde 𝑟𝑎𝑡𝑒 este media ratei de transfer dintre procesoarele în cauză.
Fiecărui nod îi corespund de asemenea două atri bute EST (Earliest Start Time) și EFT
(Earliest Finish Time). Aceste două valori sunt calculate recursiv, începând cu nodul de intrare.
Pentru a putea calcula valoarea EFT a unui nod n i trebuie ca predecesorii imediați ai nodului n i
să fie deja programați. Valorile EST(n i,pj) și EFT(n i,pj) reprezintă „earliest execution start
time”, respectiv „earliest execution finish time” al nodului n i pe procesorul p j. Acestea sunt
definite de:
EST(n i,pj) = max { T Available[j]; max
𝑛𝑚 ∈𝑝𝑟𝑒𝑑 (ni)(𝐸𝐹𝑇 (𝑛𝑚,𝑝𝑘)+𝑐𝑚,𝑖)} (1)

EFT(n i,pj) = w i,j + EST(n i,pj) (2)

unde pred(n i) este setul predecesorilor imediați ai nodului n i , iar T_Available[j] este cel mai
devreme timp la care procesorul p j este disponibil pentru execuție. Blocul max din interiorul
ecuației EST returnează „ready time” , adică timpul la care toate datele necesitate de nodul n i
ajung la gazda procesor p j.
Obiectivul programării este să se determine o asignare a task -urilor unei aplicații date
pe procesoare astfel încât timpul total de execu ție(„makespan” ) să fie minimizat respectând în
același timp constrângerile de precedență. După ce toate nodurile au fost programate, lungimea
programului va fi de fapt cel mai devreme timp de finalizare a execuției nodului de ieșire n e ,
EFT(n e,pj), unde n odul n e este programat pe procesorul p j. Dacă există mai multe noduri de
ieșire, acestea vor fi conectate la un alt nod având costul zero numit „pseudo exit node” prin
muchii de cost zero, ceea ce nu afectează planificarea.
În cadrul algoritmului vom atrib ui fiecărui nod câte un rank upward și câte un rank
downward pentru a seta prioritățile de planificare. Rank -ul upward este definit recursiv de
următoarea formulă: 𝑤𝑖̅̅̅= ∑ 𝑤𝑖,𝑗/𝑝𝑝
𝑗=1

rank u(ni)=𝑤𝑖 ̅̅̅̅+ max
𝑛𝑗 ∈ 𝑠𝑢𝑐𝑐 (𝑛𝑖)(𝑐𝑖,𝑗̅̅̅̅̅+rank u(nj)) (3)

unde succ(n i) este setul succesorilor imediați ai task -ului n i. Denumirea de „upward ranking”
provine de la faptul că este calculat recursiv, traversând graful de jos în sus, începând cu nodul
de ieșire. În esență, rank u(ni) este lungimea drumului critic (cel mai lun g drum) de la nodul n i
la nodul de ieșire, incluzând media costurilor de execuție a nodului în sine.
Similar, rank-ul downward al task -ului n i este definit recursiv astfel:
rank d(ni)= max
𝑛𝑗 ∈ 𝑝𝑟𝑒𝑑 (𝑛𝑖){ rank d(nj)+𝑤𝑗 ̅̅̅̅+𝑐𝑗,𝑖̅̅̅̅̅ } (4)

2.3 Algoritmi folosiți
Algoritmii de planificare bazați pe liste de planificare mențin o listă a tuturor nodurilor
unui graf în funcție de prioritățile acestora. Aceștia constau din două etape: etapa de prioritizare
a taskurilor (sau etapa de selecție a taskulu i) pentru selectarea taskului cu cea mai mare
prioritate și etapa de selecție a procesorului pentru a selecta un procesor potrivit care
minimizează un cost predefinit (care poate fi timpul de start al execuției). Câteva exemple dintre
acestea sunt: Modifie d Critical Path Algorithm, Dynamic Level Scheduling Algorithm,
Mapping Heuristic, Insertion -Scheduling Heuristic, Earliest Time First Algorithm, Dynamic
Critical Path Algorithm, Highest Level First with Estimated Times Algorithm, LAST
Algorithm. Euristicil e bazate pe liste sunt în general mai practice și oferă performanțe mai bune
într-un timp mai scurt decât alte grupuri de euristici.
Cele două atribute principale pentru atribuirea priorităților sunt t-level (top level -nivelul
superior) și b-level (bottom level -nivelul inferior). Nivelul -t al unui nod n i este lungimea celui
mai lung drum de la un nod de intrare la n i, (excluzând n i). Aici, lungimea unui drum este suma
tuturor ponderilor nodurilor și a muchiilor de -a lungul drumului. Nivelul -t al unui nod n i este
extrem de corelat cu valoarea EFT a lui n i, notată cu T s (ni), care se determină după ce n i este
atribuit unui procesor. Nivelul -b al unui nod n i este lungimea celui mai lung drum de la nodul
ni la un nod de ieșire: nivelul -b al unui nod este delimit at de lungimea drumului critic. Un drum
critic (Critical Path -CP) a unui DAG este o cale de la un nod de intrare la un nod de ieșire, a
cărui lungime este maximă. Trebuie remarcat faptul că unii algoritmi de planificare pe un număr
limitat de resurse nu ia u în considerare ponderile muchiilor în calculul nivelului -b. Pentru a
distinge astfel definiția nivelului -b față de cea descrisă mai sus, o numim nivel -b static.
Diferiți algoritmi utilizează nivelul -t și nivelul -b în moduri diferite. Unii algoritmi
atribuie o prioritate mai mare unui nod cu un nivel -t mai mic în timp ce alți algoritmi atribuie o
prioritate mai mare unui nod cu un nivel -b mai mare. În general, planificarea într -o ordine
descrescătoare a nivelului -b tinde să planifice mai întâi nodurile dr umul critic, în timp ce
planificarea într -o ordine crescătoare a nivelului -t tinde să planifice nodurile într -o ordine
topologică. Atributul compozit (de la nivelul -b – la nivelul -t) este un compromis între cele două
cazuri anterioare. În cele ce urmează, vom prezent succint șase algoritmi de planificare (BNP –
Bounded Number Processor Algorithms).

Dynamic -Level Scheduling Algorithm (DLS)
La fiecare pas, algoritmul selectează perechea (nodul pregătit de execuție, procesorul
disponibil) care maximizează valoar ea nivelului dinamic , egal cu DL(n i,pj)= rank us(ni)-
EST(n i,pj). Valoarea utilizată în calcul a unui task, ponderea sa, este egală cu media costurilor
de execuție de pe toate procesoarele. În acest algoritm, în calculul upward rank -ului nu se ține
cont de c osturile de comunicare. Pentru medii eterogene de planificare, este adăugat un nou
termen, echivalent cu diferența dintre media timpilor de execuție a taskului pe toate resursele
și timpul de execuție de pe procesorul curent. Algoritmul DLS are complexitat ea timpului de
execuție egală cu O(v3x q), unde q este numărul de procesoare, iar v numărul de taskuri [12].
Levelized – Min Time Algorithm (LMT)
Este un algoritm cu două etape. Prima grupează taskurile care pot fi executate în paralel
folosind atributul level . A doua atribuie fiecare task celui mai rapid procesor disponibil. Un task
dintr -un nivel mai inferior are o prioritate mai mare decât unul dintr -un nivel mai superior. În
cadrul aceluiași nivel, nodul cu cea mai mare pondere are o prioritate mai mar e. Fiecare task
este asignat unui procesor care minimizează suma dintre ponderea taskului (timpul de execuție)
și costurile de comunicare cu taskurile din nivelul anterior. Pentru un graf complet conectat,
complexitatea timpului este de O(v2x q2), unde v e ste numărul de taskuri, iar q este numărul de
procesoare [12].
Mapping Heuristic (MH)
În cadrul acestui algoritm ponderea unui task pe un procesor se calculează ca raportul
dintre numărul de instrucțiuni executate în cadrul taskului și viteza procesorului. Cu toate
acestea, înainte de planificare, în setarea ponderilor taskurilor și ale comunicării dintre muchii,
sunt stabilite elemente de procesare similare (de exemplu, resursele omogene); eterogenitatea
apare pe parcursul planificării [12].
Modified Criti cal Path (MCP)
Înainte de a descrie algoritmul MCP, vom introduce un atribut numit „cel mai târziu
posibil timp de începere a execuției” unui nod. Este atribuit fiecărui nod prin legătura „cât -mai-
tarziu -cu-putință” (Alap -As late as possible), care se face prin traversarea grafului invers,de jos
în sus, de la din nodurile de ieșire la nodurile de intrare și prin tragerea nodurilor jos cât mai
mult posibil. Algoritmul MCP este descris pe scurt mai jos:
(1) Efectuați legătura Alap și atribuiți cei mai târzii timpi de start posibili tuturor nodurilor.
(2) Pentru fiecare nod, creați o listă care constă din cei mai recenți timpi posibil de începere a
execuției nodului în sine și ai tuturor copiilor săi, în ordine descrescătoare. Sortați această listă
în ordine c rescătoare lexicografic. Conform acestui ordin, creați o listă nouă L.
(3) Planificați primul nod din L la un procesor care dă cel mai devreme timp de începere.
Ștergeți nodul din L și repetați acest pas până când L devine gol.
Algoritmul MCP atribuie o pr ioritate mai mare nodurilor care au timpii cei mai târzii
posibili de pornire mai mici. Cu toate acestea, algoritmul MCP nu planifică neapărat nodurile
întâi pe CP. Algoritmul MCP nu atribuie priorități nodurilor cu exactitate, chiar dacă este nevoie
de co municare între nodurile în cauză la stabilirea priorităților. Complexitatea timpului acestui
algoritm este de O(v2*log𝑣) [10] .

Dynamic Critical Path (DCP)
Algoritmul Dynamic Critical Path (DCP) este diferit față de restul prin diverse moduri.
În primu l rând, determină drumul critic al grafului și selectează următorul nod pentru planificare
într-un mod dinamic. În al doilea rând, rearanjează planificarea pe fiecare procesor în mod
dinamic în sensul că pozițiile nodurilor din listele parțiale nu sunt fix ate până nu au fost luate
în considerare toate nodurile. În al treilea rând, folosește un mod inteligent de a selecta
procesorul potrivit pentru un nod uitându -se înainte la potențiali timpi de începere ai nodurilor
critice rămase pe procesorul respectiv ș i planificând nodurile relativ mai puțin importante pe
procesoarele deja în uz.
În ciuda faptului că utilizează mai multe trăsături în plus, algoritmul DCP este rapid,
economic în ceea ce privește numărul de procesoare utilizate și la fel de potrivit pentr u diferite
tipuri de structuri de grafuri [10].
Highest Level First with Estimate Times Algorithm (HLFET)
Acesta este cel mai simplu algoritm dintre algoritmii de planificare pe un număr limitat
de resurse. A fost dezvoltat pentru procesoare identice compl et conectate. În acest algoritm,
prioritatea sarcinii este decisă prin utilizarea atributului static level (sl) . Problema majoră a
acestui algoritm este faptul că nu folosește costuri de comunicare pe parcursul întregului proces,
adică ignoră costurile de comunicare. Complexitatea timpului acestui algoritm este O(v2) [11].
Earliest First Time (EFT)
Algoritmul ETF folosește atributul nivel static (sl) pentru a calcula prioritatea fiecărei
sarcini a graficului. Nu este nevoie să fie planificată sarcina cu cea mai mare prioritate la fiecare
pas al procesului. Algoritmul ETF calculează cel mai devreme timp de start al fiecărei și îl
selectează pe cel mai mic pentru planificare. Dacă două sau mai multe sarcini au același timp
de start, algoritmul EFT selectează s arcina cu cu cea mai mare prioritate de pe nivelul static
(sl). Problema majoră a algoritmului este că nu poate reduce durata parțială a planificării la
fiecare pas al procesului de planificare. Complexitatea timpului acestui algoritm este O(p*v2)
[11].
Insertion Scheduling Heuristic (ISH)
Algoritmul ISH utilizează o idee simplă, dar eficientă, de a folosi găurile create de
planificările parțiale. Algoritmul alege mai întâi un nod neplanificat cu cel mai mare nivel static
(sl) și îl atribuie la un proceso r care permite cel mai scurt timp de pornire, și, astfel, în esență,
are același dezavantaj ca și algoritmul HLFET. Algoritmul ISH încearcă să "insereze" alte
noduri neplanificate din lista de nodruri pregătite de execuție în intervalul orar inactiv înaint ea
nodului tocmai planificat [13].
Localized Allocation of Static Tasks Algorithm (LAST)
Algoritmul LAST nu este un algoritm de planificare pe liste și utilizează un atribut
pentru prioritatea nodului numit D_NODE, care depinde numai de muchiile incidente ale unui
nod. Scopul principal al algoritmului este de a minimiza comunicarea generală. Acest obiectiv,
cu toate acestea, nu duce în mod necesar la minimizarea timpului de finalizare. Una dintre
consecințele folosirii atributului D_NODE este aceea că un n od poate fi selectat pentru
planificare înaintea unuia dintre părinți. Astfel, cel mai scurt timp de începere a execuției unui

nod nu poate fi fixat până ce procesul de planificare nu se termină. În plus, poate fi necesar ca
un nod să fie introdus în orice interval de timp de inactivitate pe un procesor. Algoritmul LAST
ignoră ponderile nodului în procesul de selecție ale acestora [13].
În cadrul lucrării sunt aleși spre implementare doi algoritmi dintre cei mai uzuali folosiți
la comparare atunci când se p ropune o nouă strategie de planificare, algoritmul HEFT
(Heterogeneous Earliest Finish Time) și algoritmul CPOP ( Critical Path on a Processor) .
Algoritmul HEFT , algoritm de planificare a grafurilor aciclice direcționate, suportă un
număr definit de eleme nte eterogene de procesare. Pentru a seta o prioritate unui task n i,
algoritmul utilizează valoarea rank -ului upward aferent, care este lungimea celui mai lung drum
de la nodul n i la nodul de ieșire. Calculul rank -ului u se bazează pe media timpilor de exe cuție a
nodului și pe costurile comunicării. Lista taskurilor care urmează să fie programate este
generată sortând nodurile în ordinea descrescătoare a valorilor rank -urilor lor. HEFT folosește
valoarea EFT pentru pentru a -i atribui fiecărui nod un proceso r.
Acest algoritm are două părți importante, etapa de prioritizare a task -urilor, în care sunt
calculate prioritățile tuturor nodurilor și cea de selectare a procesorului, unde nodurile sunt
selectate în ordinea priorităților și programate fiecare pe „cel mai bun” procesor corespunzător,
care minimizează timpul său final de execuție.
În algoritmul HEFT, căutarea unui timp apropiat de inactivitate pentru un task n i pe un
procesor p j începe în clipa în care se ajunge la „the ready time” -timpul la care nodul n i este
pregătit pe procesorul p j, timpul la care toate datele nodului n i au fost trimise de către toți
predecesorii nodului n i au ajuns la procesorul p j. Căutarea continuă până când este găsit acel
timp de inactivitate capabil să susțină timpul total nece sar execuției taskului n i. HEFT are o
complexitate de timp O(e × p) pentru e muchii și p procesoare. Pentru un graf dens în care e,
numărul muchiilor, este proporțional cu O(v2) și v fiind numărul de noduri, complexitatea
timpului va avea un ordin de O(v2 × p).
Deși algoritmul CPOP are aceleași etape de prioritizare a taskurilor și de selecție a
procesorului, utilizează un atribut diferit pentru setarea priorităților și o altă strategie pentru
determinarea „celui mai bun” procesor pentru fiecare task selec tat. În etapa de prioritizare sunt
calculate valorile upward ranking -ului și downward ranking -ului pentru fiecare nod în parte
folosind media timpilor de execuție și media costurilor comunicării. CPOP utilizează drumul
critic al unui graf dat. Lungimea ace stui drum, |𝐶𝑃|,este egală cu suma mediilor timpilor de
execuție a nodurilor din acest drum și a costurilor muchiilor aferente nodurilor interconectate
de-a lungul drumului. Prioritatea fiecărui task este de fapt suma rank -urilor upward și
downward. Lungi mea drumului critic inițială este egală cu prioritatea nodului de intrare. Inițial,
nodul de intrare este nodul selectat și marcat ca nod al drumului critic . Un succesor imediat (al
nodului selectat) care are cea mai mare prioritate este selectat și marca t ca nod al drumului
critic. Acest proces este repetat până când ultimul nod este selectat, nodul de ieșire. Dintre
succesorii imediați ai unui nod este selectat întâi nodul cu cea mai mare prioritate. Ordinea este
respectată în continuare pentru fiecare n od.
Se menține o coadă de priorități (cu valorile key -lor rankurilor upward și downward)
care va conține taskurile pregătite de execuție la orice moment. La fiecare pas, taskul cu cea
mai mare valoare rank u+rank d este selectat din coada priorităților.

În etapa de selecție a procesorului, procesorul drumului critic, pCP, este acela care
minimizează costurile cumulative ale nodurilor aflate pe acest drum. Dacă nodul selectat se află
pe drumul critic, atunci el va fi programat pe procesorul drumului critic; altfel este atribuit unui
procesor care minimizează cel mai devreme timp final de execuție al nodului. Ambele cazuri
folosesc o politică de planificare bazată pe inserție. Complexitatea timpului algoritmului CPOP
este de ordin O(e × p).

Capitolul 3 – Algo ritmi folosiți

În lumea reală există diverse domenii de aplicabilitate ale acestor algoritmi, ale
variantelor algoritmilor deja implementați sau ale altor algoritmi adiacenți, de la bioinformatică
până la economie. Dintre acestea amintim Algoritmul Elimin ării lui Gauss(Gauss Elimination),
Transformarea Fast Fourier, Codul Dinamicii Moleculare, Ecuația Laplace, Montage
Workflow: An Astronomical Image Mosaic Engine (Montage este o aplicație utilă construcției
de mozaicuri de imagini astronomice particulariza te ale cerului), Epigenomic Workflow:
Analiza datelor undelor gravitaționale (Workflow -uri folosite pentru a mapa starea epigenetică
a celulelor umane pe o scară largă a genomului).

3.1 Descriere
În cadrul lucrării sunt prezentați și implementați trei algor itmi de planificare a taskurilor
unui graf orientat: algoritmul HEFT (Heterogeneous Earliest Finish Time) , algoritmul CPOP (
Critical Path on a Processor) și algoritmul Hybrid Heuristic .

3.1.1 Algoritmul HEFT
Algoritmul HEFT este un algoritm de planificare a grafurilor aciclice direcționate, care
suportă un număr definit de elemente eterogene de procesare. Pentru a seta o prioritate unui
task n i, algoritmul utilizează valoarea rank -ului upward aferent, (ecuația 3) care este lungimea
celui mai lung drum de la n odul n i la nodul de ieșire. Calculul rank -ului se bazează pe media
timpilor de execuție a nodului și pe costurile comunicării. Lista taskurilor care urmează să fie
programate este generată sortând nodurile în ordinea descrescătoare a valorilor rank -urilor lor.
Dacă două noduri au același rank, selecția nodului care va urma a fi planificat se va realiza
aleatoriu.
Algoritmul HEFT folosește valoarea EFT pentru pentru a atribui fiecărui nod un
procesor. Acest algoritm are două părți importante, faza de priori tizare a task -urilor , în care
sunt calculate prioritățile tuturor nodurilor și faza de selectare a procesorului , unde nodurile
sunt selectate în ordinea priorităților și programate fiecare pe „cel mai bun” procesor
corespunzător, care minimizează timpul să u final de execuție.
Etapa de prioritizare a task -urilor

Aceasta presupune ca prioritatea fiecărui să fie setată cu valoarea upward ranking -ului,
( rank u ) nodului respectiv, care se bazează pe media timpilor de execuție a nodului respectiv și
pe media cos turilor de comunicare cu celelalte noduri de legătură. Lista taskurilor care urmează
să fie planificate este generată sortând nodurile în ordinea descrescătoare a valorilor rank -urilor
lor upward.
Etapa de selecție a procesorului
Pentru majoritatea algorit milor de planificare , cel mai devreme timp la care un procesor
pj este pregătit de execuția unui task este acel timp la care procesorul p j își termină execuția
ultimului nod care i -a fost deja programat. Cu toaste acestea, HEFT are o politică bazată pe
inserție care consideră posibilă inserția unui nod în cel mai devreme interval de timp dintre
două noduri deja programate pe un procesor. Lungimea unui interval de timp de inactivitate,
adică diferența dintre cel mai timp ul de start și timpul de finish a două taskuri care au fost
consecutiv programate pe același procesor, trebui e să fie poată susține execuția nodului care
urmează să fie planificat, respectiv timpul de inactivitate să fie cel puțin minim față de timpul
de execuție al taskului . În plus, programa rea în acest timp de inactivitate ar trebui să mențină
constrângerile de precedență.
În algoritmul HEFT, căutarea unui timp apropiat de inactivitate pentru un task n i pe un
procesor p j începe în clipa în care se ajunge la „the ready time” -timpul la care no dul n i este
pregătit pe procesorul p j , timpul la care toate datele nodului n i au fost trimise de către toți
predecesorii nodului n i au ajuns la procesorul p j. Căutarea continuă până când este găsit acel
timp de inactivitate capabil să susțină timpul tota l necesar execuției taskului n i. HEFT are o
complexitate de timp O(e × p) pentru e muchii și p procesoare. Pentru un graf dens în care e,
numărul muchiilor este proporțional cu O(v2), v fiind numărul de noduri, complexitatea timpului
va avea un ordin de O(v2 × p).
Pseudo codul aferent algoritmului HEFT este prezentat în figura 3.1.
1. Calculați rank u pentru toate nodurile traversând graful invers, începând cu nodul de ieșire
2. Sortați nodurile într -o listă în ordinea descrescătoare a valorilor rank -urilor upward
3. while există noduri neplanificate în listă do
4. Begin
5. Selectați primul task ni din listă și înlăturați -l
6. Atribuiți taskul ni proces orului pj care minimize ază valoarea EFT a taskului ni.
7. End
Fig. 3.1. Algoritmul HEF T

3.1.2 Algoritmul CPOP
Deși algoritmul CPOP are aceleași etap e de prioritizare a taskurilor și de selecție a
procesorului, utilizează un atribut diferit pentru setarea priorităților și o altă strategie pentru
determinarea „celui mai bun” procesor pentru fiecar e task selectat.
Etapa de prioritizare a taskurilor

În această etapă sunt calculate valorile upward ranking -ului și downward ranking -ului
pentru fiecare nod în parte folosind media timpilor de execuție și media costurilor comunicării
(Pașii 1 -3 ai algori tmului CPOP: Pas 1: Calculați rank u pentru toate nodurile traversând graful
invers, pornind de la nodul de ieșire spre cel de start; Pas 2: Calculați rank d pentru toate nodurile
traversând graful normal, pornind de la nodul de start spre cel de ieșire; Pas 3: |CP|=rank u(ns),
unde ns este nodul de start).
CPOP utilizează drumul critic al unui graf dat. Lungimea acestui drum, |𝐶𝑃|, este egală
cu suma mediilor timpilor de execuție a nodurilor din acest drum și a costurilor muchiilor
aferente nodurilor inter conectate de -a lungul drumului. Practic, suma tuturor costurilor mediilor
execuției nodurilor aferente drumului reprezintă limita inferioară a lungimii programării
generată în cadrul algoritmilor de acest gen.
Prioritatea fiecărui task este de fapt suma r ank-urilor upward și downward. Lungimea
drumului critic este egală cu prioritatea nodului de intrare (Pasul 5). Inițial, nodul de intrare este
nodul selectat și marcat ca nod al drumului critic. Un succesor imediat (al nodului selectat)
care are cea mai m are prioritate este selectat și marcat ca nod al drumului critic. Acest proces
este repetat până când ultimul nod este selectat, nodul de ieșire (Pașii 6 -12 : Pas 6: ni este nod
al drumlui critic (CPN); Pas 7: Selectați procesorul -drumului -critic care minimizează
∑ 𝑤𝑖,𝑗 𝑛𝑖 ∈𝐶𝑃𝑁 ; Pas 8: Inițializați coada -priorităților cu nodurile de intrare; Pas 9: cât timp
există noduri neplanificate în coada de priorități; Pas 10: begin; Pas 11: Selectați nodul cu
prioritatea cea mai mare din coada de pr iorități; Pas 12: care maximizează valoarea rank d(ni) +
rank u(ni) ). Dintre succesorii imediați ai unui nod este selectat întâi nodul cu cea mai mare
prioritate. Ordinea este respectată în continuare pentru fiecare nod.
Algoritmul menține o coadă de prior ități (cu valorile rankurilor upward și downward)
care va conține taskurile pregătite de execuție la orice moment. Pentru implementarea acestei
cozi a fost folosită o variabilă binară, care are o complexitate O(log𝑣) pentru inserția și
ștergerea unui t ask și o complexitate O(1) pentru extragerea taskului cu cea mai mare prioritate.
La fiecare pas, taskul cu cea mai mare valoare rank u+ rank d este selectat din coada priorităților.
Etapa de selecție a procesorului
Procesorul drumului critic, pCP, este ac ela care minimizează costurile cumulative ale
nodurilor aflate pe acest drum (Pasul 13 : if (ni is a CPN) ). Dacă nodul selectat se află pe drumul
critic,atunci el va fi programat pe procesorul drumului critic; altfel este atribuit unui procesor
care minim izează cel mai devreme timp final de execuție al nodului. Ambele cazuri folosesc o
politică de programare bazată pe inserție. Complexitatea timpului algoritmului CPOP este de
ordin O(e × p).
Pseudo codul aferent algoritmului CPOP este prezentat în figura 3. 2.
1. Calculați rank u pentru toate nodurile traversând graful invers, începând cu nodul de ieșire
2. Calculați rank d pentru toate nodurile traversând graful în jos începând cu nodul de start
3. |CP|=rank u(ns), unde ns este nodul de start
4. For nod ni do
5. If (rank d(ni) + rank u(ni) =|CP|
6. ni este nod al drumului critic (CPN)
7. Select ați proces orul drumului critic care minimize ază ∑ 𝑤𝑖,𝑗 𝑛𝑖 ∈𝐶𝑃𝑁
8. Inițializați coada de priorități cu nodurile de intrare

9. while există n oduri neplanificate în coada de priorități do
10. begin
11. Selectați nodul cu cea mai mare prioritate din coada de priorități
12. care maximizează rank d(ni) + rank u(ni)
13. if (ni este CPN)
14. planificați ni pe proces orul critic
15. else
16. Atribuiți taskul ni proce sorului pj care minimize ază valoarea EFT a nodului ni
17. Updatați coada de priorități cu succes orul(ii) lui ni dacă devine (devin) pregătit(ți) de
execuție
18. end
Fig. 3.2. Algorit mul CPOP

3.1.3 Algoritmul Hybrid Heuristic
Ideea euristicii hibrid este de a utiliza o abordare standard de planificare bazată pe liste
pentru a seta priorități nodurilor DAG -ului și de a utiliza acest clasament pentru a atribui sarcini
unor grupuri de sarcini care pot fi ulterior programate independent . Algoritmul este format din
trei etape: setarea de priorități, creare a grupurilor și planificarea sarcinilor independente în
cadrul f iecărui grup.
În prima etapă , fiecărui nod și fiecărei muchii le sunt atribuit e ponderi ; acest lucru se
bazează pe o medie a tuturor valorilor posibile pentru costul fiecărui nod (respectiv muchie ) pe
fiecare procesor (respecti v combinație de procesoare). Folosind această pondere , clasament ul
ascendent este realizat și fiecărui nod îi este atribuit o prioritate .
În a doua etapă , noduri le sunt sortate în ordinea valori lor descrescătoare a rank -urilor;
pe baza acestei ordin i, taskurile sunt luate în considerare pentru crearea grupurilor, după cum
urmează. Primul nod (nodul cu valoarea cea mai mare a rank -ului) se adaugă la un grup
numerotat cu 0. N oduri le succesive, întotdeauna în ordine a descrescătoare a valorii rank-ului,
sunt plasate în același grup atâta tim p cât acestea sunt independente față de toate nodurile deja
alocat e grupului (adică dacă nu există o dependență între ele în DAG). Dacă se găsește o
dependență, atunci nodul cu cea mai mică prioritate devine membru al unui nou grup. Numărul
noului grup este numărul grupul curent incrementat cu o unitate . Din nou, sarcini le rămase , în
funcție de valoarea rank-ului, vor fi adăugate ultimului grup cât timp acestea nu sunt dependente
de oricare alt nod care este deja membru al acestui grup; dacă acestea sunt dependente , un nou
grup va fi creat și așa mai departe. Rezultatul acestui pro ces este un set de grupuri ordonate,
fiecare dintre ele constând dintr -un număr de sarcini independente și având o prioritate
predeterminată (bazat ă pe clasamentul inițial al nodurilor; un număr mic al grupului indică o
prioritate mai mare).
În a treia eta pă, este realizată o planificare a unui DAG prin luarea în considerare a
fiecărui grup în ordi nea crescătoare a numărului său și folosind un algoritm pentru taskuri
independente (BMCT – Balanced Minimum Completion Time) pentru a planifica sarcinile
independ ente din cadrul fiecărui grup. Datele de intrare sunt un set de sarcini (independente),
un set de procesoare, setul care conține costul de execuție a l fiecărui nod pe fiecare resursă și
un alt set oferind cel mai scurt timp la care fiecare sarcină își poate încep e execuția pe fiecare
procesor, respectiv EST.

O schiță a euristicii este dată în figura 3. 3. Față de alte euristici, a bordarea hibridă ia în
considerare atât structura DAG -ului, cât și costurile de calcul și de comunicare. Astfel, inițial
au loc atribuirea ponderilor și clasamentul pe baza acestora, urmând ca planificarea să se
realizeze pe această bază.
Pseudo codul aferent algoritmului Hybrid este prezentat în figura 3.3.
(1) Atribuiți o pondere fiecărui nod ca media costurilor de execuție de pe to ate resursele
Atribuiți o pondere fiecărei muchii ca media costurilor de comunicare de pe toate resursele
Calculați rank u pentru toate nodurile traversând graful invers, începând cu nodul de ieșire
Sortați nodurile în ordinea descrescătoare a valorilor ran k-urilor upward
Go={ } ; i=0
Parcurgeți nodurile în ordinea descrescătoare a valorilor rank -urilor upward
if nodul curent are o dependență cu oricare din nodurile grupului Gi
atunci i ++ ; Gi = { }
se adaugă nodul la grupul Gi
Se co ntinuă parcurgerea până când nu mai sunt noduri
for fiecare grup Gi, în ordinea crescătoare a lui i
se calculează valorile EST ale fiecărui nod pentru fiecare procesor
se planifică nodurile independente din cadrul fiecărui Gi conform algoritmu lui BMCT,
ținând cont de valorile EST
endfor (2)
(3)
Fig. 3.3. Algoritmul Hybrid Heuristic

Algoritmul BMCT surclasează alte euristici similare de planificare a taskurilor
independente deoarece după o alocare inițială de sarcini procesoarelor care red uc timpul de
execuț ie, există o etapă care încearcă să minimizeze timpul total de excuție al sarcinilor printr –
o încercare de a "echilibra" costul acestora, interschimbând taskurile între procesoare . După
cum s -a indicat deja, datele de intrare sunt câte un set de sarcini independente pentru fiecare
grup, setul de procesoare, setul care conține costul de execuție a l fiecărui nod pe fiecare resursă
și un alt set al valorilor EST. Obiectivul este de a finaliza executarea tuturor sarcinilor cât mai
devreme pos ibil (de a minimiza makespan -ul tota l).
Algoritmul BMCT este format din două etape. În prima etapă are loc o alocare inițială
a sarcini lor pe procesoare. Î n a doua etapă, cea de optimizare, sarcinile selectate sunt mutate
între mașini pentru a minimiza lun gimea totală a programul ui.
Alocarea inițială presupune atribuirea fiecărei sarcini resursei care dă cel mai bun, cel
mai scurt timp de execuț ie. După ce toate sarcinile sunt atribuite la câte o resursă, taskurile
fiecărui procesor sunt sortate în ordine a crescătoare a valorilor EST a fiecărui task pentru acest
procesor. Această ordin e determină ordinea în care sarcinile unui graf dat trebuie să fie
executate astfel încât să fie atins un timp minim de execuție pentru fiecare resursă în parte.
Etapa de opti mizare verifică dacă mutarea oricărui task de la procesorul care a
determinat un timp maxim de finalizare a execuției la un alt procesor ar da un makespan mai
mic; dacă există un astfel de task , atunci este realocat procesorului care minimizează makespan –
ul. Aceasta este o procedură iterativă, care se repetă până când nu mai există nici o sarcină de

verificat. În cursul fiecărei iterații au loc t rei acțiuni: (i) se selectează un nod din cadrul
procesorului care dă un timp maxim de finalizare a execuției; (i i) se selectează un procesor
pentru a muta taskul selectat; (iii) presupunând că un astfel de procesor este găsit, se introduce
taskul pe lista de sarcini a procesorului . Alegerea unei s arcini care urmează să fie luată în
considerare pentru o posibilă muta re pe un alt procesor se bazează pe o ordin e deja calculat ă
pentru toate sarcinile. Ace astă ordin e este rezultatul sortării în ordine crescătoare a mediei
valorilor EFT ale fiecărei sarcini de pe toate resursele . Algoritmul se termină atunci când nici
una dintre sarcinile resursei care dă timpul maxim de finalizare a execuției nu mai poate fi
mutat ă la orice altă resursă .
Pseudo codul aferent algoritmului BMCT este prezentat în figura 3.4.
(1) Atribuiți fiecare task procesorului care oferă cel mai rapid timp de execuție
For toate procesoarele
Creați o listă a nodurilor atrbuite procesorului respectiv
Sortați nodurile în ordinea crescătoare a valorilor EST pentru procesorul respectiv
endfor
Avg_FT[]< – lista tuturor taskurilor în ordine crescătoare a mediilor valorilor EFT de pe
toate procesoarele
repetă
m <- procesorul cu timpul maxim de terminare a execuției, MFT
moved _task <- false
Marcați toate taskurile procesorului m din lista Avg_FT[] ca și unchecked , iar restul
taskurilor ca și checked
while (există taskuri unchecked ȘI moved_task e false)
t <- următorul task unchecked din lista Avg_FT[]
for toate procesoarele i cu excepția lui m
Calculați finish time, FT i, pentru fiecare procesor, pentru cazul fiecărei posibi le
inserări în lista de taskuri a procesorului
endfor
i <- procesorul cu cea mai mică valoare FT i
if FTi < MFT mutași taskul t în lista de taskuri a procesorului i ; moved_task <-
true
else marcați t ca și checked
endwhile
until moved_task e false (2)
Fig. 3.4. Algoritmul BMCT

3.2 Variante
Pe lângă varianta inițială a algoritmului HEFT în literatură există diferite variante ale
algoritmului HEFT.
1. HEFT with lookahead
Algoritmul Lookahead folosește o nouă metodologie pentru a selecta procesorul potrivit
pentru taskul selectat în fiecare etapă de planificare. În Lookahead, în primul rând, se calculează
upward rank pentru toate sarcinile dintr -un anumit DAG la fel ca în algoritmul HEFT.

Dar, în etapa de selecție a procesorului, spre deosebire de algoritmul HEFT care
selectează procesorul pe baza valorii EFT (earliest finish time) nodul curent, algoritmul
Lookahead pentru a testa fiecare procesor, alocă mai întâi taskul selectat procesorului și apoi
planifică copiii nodului selec tat și salvează maximul dintre valorile EFT ale copiilor ca valoare
EFT a nodului selectat pe procesor.
După testarea tuturor resurselor în cazul adăugării taskului selectat pe fiecare dintre
acestea, algoritmul Lookahead selectează procesorul cu valoar ea minimă a EFT -ului bazată pe
taskurile copii participante la calculul acestei valori[3].
Algoritmul Lookahead:
 utilizează informațiile taskurilor succesoare pentru a prevedea modul în care
deciziile afectează celelalalte taskuri
 testează fiecare task pe fiecare resursă și verifică consecințele pe nodurile copii
aferente fiecărui nod
 mărește complexitatea
– HEFT este simplu și rapid: mărirea timpului de execuție este accesibilă
Câteva dezavantaje ale acestei vesiuni sunt:
 în momentul testării unui task t pe fiecare resursă, unele taskuri copil ar putea
deveni indisponibile pentru planificare
o se vor lua în considerare doar taskurile părinte deja planificate când se
calculează valorile EFT ale taskurilor copii
 există mai multe modalități de a selecta o res ursă pentru un task t bazându -ne pe
valorile EFT ale taskurilor copii. Prezentăm două moduri:
o minimul dintre valorile maxime EFT ale taskurilor copil ale taskului t pe
toate procesoarele
o valorile medii EFT ale copiilor taskului t

2. Priority list change – relaxing priorities

 altă abordare: modelarea priorităților date de algoritmul HEFT
 inversează ordinea de planificare dată de rank u în ideea de a obține o planificare
mai bună
 sortează noua „listă de priorități looakahead”
 folosește algoritmul Lookahead d e două ori:
o consideră taskurile in ordinea dată de rank u
o inversează ordinea primelor două taskuri
Fie t taskul neplanificat pregătit de planificare cu cea mai mare prioritate și t1 următorul
task neplanificat pregătit de planificare cu cea mai mare prior itate[4].
1) L ⇐ t1 ∪ suc(t) ∪ suc(t1) , unde L este setul „lookahead” conținând taskurile care au
valorile EFT considerate la selecția resursei, iar suc() lista de succesori ai nodului în
cauză
2) se execută algoritmul Lookahead utilizând L ca și listă lookahe ad

3) se interschimbă taskurile t și t1, apoi se repetă pașii 1 -3
4) ordinea care dă cel mai bun rezultat per ansamblu este apoi menținută.

3. Algoritmul P -HEFT (Parallel task -HEFT)

Algoritmul P -HEFT este o adaptare a algoritmului HEFT pe DAG -uri cu taskuri
paral ele, care inițial, asemenea lui HEFT, calculează mediile timpilor de execuție și ale
costurilor de comunicare ale muchiilor, precum și lungimea celui mai lung drum al fiecărui nod,
începând cu nodul respectiv până la nodul de ieșire, pe care îl numim b-level. Apoi, algoritmul
stabilește o listă de taskuri pregătite de planificare și calculează pentru fiecare task în parte
capacitatea de calcul care minimizează taskul, Si* , pe principiul că se utilizează procesoarele
care dau cel mai bun timp de execuție.
În continuare, algoritmul planifică taskurile în ordinea descrescătoare a b-level -ului și
le atribuie pe procesoarele care pot porni execuția acestora începând cu valoarea EFT
corespunzătoare. Este ales cel mai rapid procesor pregătit pentru execuție la timpul t-level al
taskului i ( tli ) , t-level echivalând cu lungimea celui mai lung drum de la nodul de intrare până
la nodul i; în cazul în care nici un procesor nu este disponibil la timpul respectiv, este ales
primul procesor disponibil după timpul tl i. Această condiție este utilă în cazurile în care un timp
întârziat de start rezultă într -un mai scurt de finish. În aceste cazuri pot apărea diverse găuri în
planificare pe care algoritmul nu reușește să le umple. Valoarea EFT i a unui task i este valoare a
maximă a valorii tl i și timpul de finish al ultimului task atribuit procesorului k. Este introdus de
asemenea un parametru limit pentru a limita capacitatea atribuită unui singur task. Cât timp
această limită încă nu este depășită, ne referim la algoritm cu P-HEFT -limit. La pasul 13 ( if
p=1 OR est i + ti,p < est i’ + ti,p-1) ti,p este timpul de procesare obținut până la momentul respectiv
de procesorul p. La pasul 15 (i k==null break ), planificarea taskului i se încheie dacă nu mai
sunt procesoare de tes tat.
Față de varianta originală a algoritmului, P -HEFT oferă un makespan mai bun doar în
cazul unui singur DAG, nu și pentru DAG -uri multiple, iar un dezavantaj este scăderea
eficienței[5].

4. An Improved Heft Algorithm Using MultiCriterian Resource Factors

Această variantă îmbunătățită a algoritmului HEFT include diverși noi factori care
contribuie la atribuirea resurselor potrivite pentru un task pregătit de planificare, cum ar fi
lățimea de bandă dintre noduri, memoria de stocare și memoria RAM.
Lățimea de bandă dintre fiecare pereche de mașini virtuale este specificată ca și
parametru, iar scopul este de a optimiza costul comunicării în loc de a folosi media costului de
comunicare din algoritmul HEFT. Acest parametru este introdus pentru a studia abunden ța și
pentru a implementa dependența dintre taskuri precum și cea dintre resurse.
Analiza comparativă a algoritmului nostru propus cu algoritmul existent HEFT arată
faptul că algoritmul propus are rezultate mai bune și este un algoritm de planificare mai fiabil.
Următorii doi parametri sunt luați în considerare pentru evaluarea rezultatelor:
Primul parametru este timpul de „turnaround”, egal cu timpul dintre momentul trimiterii
taskului pentru execuție și timpul returnării rezultatului complet:

Turnaround time= Submission Time + Waiting Time + Execution Time
Timpul de „turnaround” este comparat pentru algoritmul original HEFT, algoritm care
nu conține acest parametru față de algoritmul propus, care utilizează parametrul. Comparația
este realizată cu numărul de taskuri, crescând acest număr treptat. Pentru orice algoritm de
planificare, este așteptat ca timpul de „turnaround” sau timpul total de execuție al taskului ,
începând cu timpul de trimitere până când este finalizat cu succes, să fie minimizat.
Al doi lea parametru , timpul de răspuns ( Response Time ) al unui task sau al unui
thread, este egal cu diferența dintre timpul la care taskul este pregătit de execuție și timpul la
care taskul își încheie execuția:
Response Time = Arrival Time – Finish Time
Timpul de răspuns este comparat pentru algoritmul original HEFT, care nu conține acest
parametru față de algoritmul propus, care utilizează parametrul. Comparația este realizată cu
numărul de taskuri, crescând acest număr treptat.
Timpul de răspuns depinde de o varietate de factori, iar unul dintre aceștia este lățimea
de bandă. Viteza de rețea poate fi mărită prin implementarea lățimii de bandă dintre noduri;
algoritmul propus are un timp de răspuns bun.
Inițial, pentru orice operațiuni de calcul, prima necesitate este memoria RAM. Această
memorie este prima utilizată; prin urmare, disponibilitatea sa ajută programatorii să obțină o
funcționare mai bună din moment ce au posibilitatea să reducă timpul de răspuns, timpul de
execuție [6].

Capitolul 4 – Aplicația
Acest capitol conține structura aplicației și teste comparative cu algoritmii implementați
(HEFT, CPOP ) pentru a le determina eficiența pentru câteva exemple de aplicații de tip
workflow care se planifică pe mai multe procesoare.
4.1 Structura
Aplicația este structurată în nouă clase . Testele s -au realizat pentru trei grafuri . Limbajul
de programare folosit pentru implementarea aplicației este Java . Java este un limbaj orientat
obiect care se pretează pentru implementarea problemei ab ordate . Aplicația conține următoarele
clase :

Figura 4.1 Relațiile dintre clasele aplicației
Datorită faptului că în lucrare subiectul prezentat este planificarea de grafuri aciclice ,
clasele de bază care descriu datele de intrare sunt „Nod”, „Graf”, „Procesor” și „Machine”.
Ideea pe care este structurată aplicația, respectiv clasele, este aceea că un obiect de tip graf
conține mai multe obiecte de tip nod și un obiect de tip machine cuprinde mai multe obiecte de
tip procesor.
Clasa Nod conține atributele și metodele necesare prelucrării grafului. Obiectul clasei
este un nod pe baza căruia se dezvoltă metodele: g etStartTime (), getFinishTime (), toString (),
getId (), adaugaCopil (), compute_Cost (), upward_ranking (), downward_ranking (),
edge_Cost ().
Metoda upward _ranking (), parte esențială a algoritmilor de planificare implementați și
setează priorități nodurilor. Dacă nodul nu are succesori, este returnată valoarea mediei rezultată
de funcția compute_Cost() . Se parcurge setul de părinț i și pentru fiecare părinte în parte se reține
într-un tablou valNod suma dintre valoarea mediei muchiei dintre cele două noduri și valoarea
recursivă a funcției curente pentru părinte. În final este returnată suma dintre media timpilor de
execuție a nodul ui curent și valoarea returnată de funcția maxArray(valNod) , funcție care
extrage maximul dintre valorile tabloului creat mai sus.
Analog se calculează și valorile downward ranking -ului, cu diferența că de această dată
se parcurge setul de copii, în condițiile în care această funcție presupune începerea calculului
de la nodul de start, nu invers, cum era la upward ranking.
Clasa Graf descrie topologia grafului, lista de noduri și cea d e muchii , reținând
ponderile asociate muchiilor . Metodele adaugaNod (), getNod (), procesare_TimpiExecutie(),
groups_creating(), atribuire().
Clasa Procesor conține metodele getId(), toString(), procesor_disponibil() , care
returnează timpul la care procesor ul respectiv își încheie execuția ultimului task atribuit .
Metodele nodOnProcesor(), goluriNodOnPr ocesor(), removeNodOnProcesor() realiz ează
planificarea task -urilor. Metoda nodOnProcesor() realizează atribuirea inițială a task -urilor pe
procesoare, iar prin goluriNodOnProcesor() se planifică nodurile luând în calcul și perioadele
inactive de timp lăsate noduri de la prima planificare. MainGraf Nod
Machine Procesor
Metode
Hybrid
HeuristicBMCT
HEFT
CPOP

Clasa Machine , pe baza listei de procesoare (creată pr in adaugaProcesor(), cu elemente
identificate prin getProcesor() ), asigură de fapt replanificarea sarcinilor prin metoda
replanificare(), folosindu -se și de metodele transfer_procesoare() și costuriMasini() pentru a
manipula datele aferente resurselor, dat e reținute în fișierele externe.
Am utilizat de asemenea o clasă Metode pentru crearea separată a metodelor
independente de sarcinile grafului, metode generice ce au aplicabilitate globală: readFile(),
maxArray(), minArray(), sortByValues().
Cu ajutorul metodelor descrise mai sus, am implementat algoritmii descriși în capitolele
2 și 3 ale lucrării. Pentru fiecare dintre aceștia am creat o clasă separată, după cum urmează:
HEFT, BMCT, CPOP , HybridHeuristic .
În clasa HEFT inițial se calculează rank -urile upward ale task -urilor prin metoda
ranksComputing() și se sortează – sorting(), creând lista nodurilor pregătite de execuție . Tot aici
se calculează valorile EST și EFT ale sarcinilor prin metodele EST() și EFT() . La final, în
metoda assign() se atribuie task -urile pe proc esoare, pe baza metodelor corespondente din clasa
Procesor.
Clasa CPOP are ca scop atribuirea sarcinilor pe un procesor critic, procesor care are ca
scop minimizarea timpului de execuție de pe drumul critic din graf. Pentru aceasta calculează
cu metodele ranksUpward() și ranksDownward() rank-urile task -urilor, marchează nodurile ca
noduri critice dacă suma rank -urilor upward și downward ale nodului egalează lungimea
drumului critic până la nodul selectat în criticalPath() , calculează și planif ică sarcinile pe
resurse în funcție de prioritate, pe procesorul critic sau pe un altul prin implementarea metodelor
criticalProcesor() și priorityScheduling().
Clasa HybridHeuristic seteză priorități le prin metoda ranksComputing() , crează
grupurile prin groups _creating() și planifică sarcinile independente în cadrul f iecărui grup prin
scheduling().
Clasa BMC T planifică fiecare grup de sarcini independente astfel: le atribuie inițial prin
metoda assign(), le sortează cu sortareNoduriPeProcesor() și le replanifică conform
algoritmului prin movingT asks() , metodă ce apel ează la rândul său calculSumaEFTProcesor( ),
MFTValue(), MFT(), getNextUnchecked().

4.2 Date de test

Datele de t est sunt grafuri aciclice direcț ionate. Un exemplu de graf folosit pentru testare
este cel din figura 4.2.

Fig. 4.2-Graf 1
Pentru a stoca datele despre graf și timpi de execuție a taskurilor din graf s -a folosit
următoarea structură de fișiere pentru a reține datele pentru un caz de testare:
1. communications_costs_machine s
2. computation_costs
3. noduri
Fișierul „noduri” reține structura grafului și este organizat astfel: pe fiecare linie primul
număr este nodul, al doilea numărul de succesori, apoi sunt luați în ordine succesorii, pe rând
fiecare nod copil urmat de costul muchi ei care face legătura între acel nod copil și părintele său.
Fișierul „computation _costs” reține timpii de execuție (computation costs) ai fiecărui
task pe fiecare procesor.
Fișierul „communication_costs_machines” cuprinde ratele de transfer între proce soare.
De exemplu pentru graful din figura 4.2 fișierele sunt organizate astfel:
 noduri. Pe fiecare linie sunt reținute următoarele informații: primul număr este nodul,
al doilea numărul de succesori (copii), apoi sunt luați în ordine succesorii, pe rând
fiecare nod copil urmat de costul muchiei care face legătura între acel nod copil și
părintele său. Ultimul nod nu are copii, ca atare locurile aferente sunt necompletate.
0 5 1 14 2 18 3 22 4 13 5 25
1 1 7 15
2 1 8 20
3 1 6 26
4 2 7 14 8 21
5 1 8 17
6 1 9 26
7 1 9 20
8 1 9 19
9

 computation _costs. Pe fiecare linie sunt enumerate costurile timpilor de execuție ai
fiecărui nod.
17
22
15
4
17
30
17
49
25
23 19
27
15
8
14
27
16
49
22
27 21
23
9
9
20
18
15
46
16
19

 communication_costs_machines. Aici sunt reținute ratele de transfer de date dintre
procesoare.
0
1
0 1
2
2 0.9
1
1.4

În cadrul aplicației au fost utilizate mai multe grafuri, fiecare cu datele corespunzătoare.
Primul graf cuprinde 10 noduri cu următorii timpi de execuție:
nod p0 p1 p2 nod p0 p1 p2
0
1
2
3
4 17
22
15
4
17 19
27
15
8
14 21
23
9
9
20 5
6
7
8
9 30
17
49
25
23 27
16
49
22
27 18
15
46
16
19

Ratele de transfer dintre procesoare sunt reținute asemănător nodurilor: pe prima poziție
se află primul procesor, pe a doua poziție al doilea procesor, iar la final costul aferent ratei de
trans fer dintre cele două :

0 1 0.9
1 2 1
0 2 1.4
După cum am menționat algoritmi utilizați se bazează pe stabilerea up -down ranking
care presupune calcului mediile timpilor de execuție și apoi a rank-urile upward, respectiv
downward corespunzătoare fiecărui nod:

nod medie rank u rank d nod medie rank u rank d

0
1
2
3
4 19
24
13
7
17 167.9
133.5
99.9
103.199
125.4 19.0
58.4
51.8
50.2
50.3 5
6
7
8
9 25
16
48
21
23 108.60
67.6
93.0
64.9
23.0
71.5
94.8
122.9
111.2
167.9

Al doilea exemplu de graf folosit este cel din figura următoare , conținând 10 task -uri :

Fig. 4.3 -Graf 2
Pentru graful din figura 4.3 fișierele sunt organizate astfel:
 noduri. Structur a fișierului are același format.
1 5
2 2
3 1
4 2
5 1
6 1
7 1
8 1
9 1
10 2 17
8 3
7 16
8 11
9 57
8 5
10 9
10 42
10 7 3 31
9 30
9 7 4 29 5 13 6 7

 computation_costs . Analog, pe fiecare linie sunt enumerate costurile timpilor de
execuție ai fiecărui nod.

22
22
32
7
29
26
14
29
15
13 21
18
27
10
27
17
25
23
21
16 36
18
43
4
35
24
30
36
8
33

 communication_costs_machines . În cadrul acestui graf nu există costuri de transfer între
procesoare.
Tabelul următor conține valori le mediei costurilor de execuție, upwad ranking -ului și
downward ranking -ului:
nod medie rank u rank d
1 26.33 169 26.33
2 19.33 114.3 64.36
3 34 102.7 94.43
4 7 110 65.23
5 30.33 129.7 73.16
6 22.33 119.3 56.36
7 23 52.7 135.03
8 29.33 92 106.66
9 14.66 42.3 150.53
10 20.66 20.7 178.89

Al treilea graf utilizat în testare și comparare conține tot 10 noduri:

Fig. 4.4 -Graf 3

Se păstrează aceeași structură a fișierelor :
 noduri. Organizarea este similară.
1 5
2 1
3 2
4 1
5 3
6 1
7 1
8 1
9 1
10 2 11
7 11
7 6
8 10
7 13
9 7
10 19
9 12
10 10 3 24
9 17
8 3 4 13
9 14 5 9 6 14

 computation_costs
11
18
7
12
19
8
14
7
12
17 19
5
20
16
5
23
24
9
14
7 6
12
13
4
16
14
19
20
16
13

 communication_costs_machines . În cadrul acestui graf nu există costuri de transfer între
procesoare.
Tabelul următor conține valorile mediei costurilor de execuție, upwad rank ing-ului și
downward ranking -ului:
nod medie rank u rank d
1 12 105.66 0
2 11.66 73 23
3 13.33 69.66 36
4 10.66 57 25
5 13.33 76.66 21
6 15 58.33 26
7 19 50.33 55.33
8 12 36.33 45.66
9 14 36.33 66.33
10 12.33 12.33 93.33

4.3 Teste

Pentru algori tmii implementați s -au realizat teste în funcție de timp și de codificarea
algoritmilor.

4.3.1 Teste în funcție de timp

Algoritmii HEFT și CPOP au fost fiecare, testați pe rând, conform unei planificări
inițiale și a unei replanificări bazate pe inserție. Algoritmul Hybrid Heuristic, bazat pe un alt
algoritm de planificare a taskurilor independente (BMCT), a fost testat do ar pentru o singură
planificare. Toate testele în funcție de timp au fost realizate în nanosecunde și transformate
ulterior în secunde. În tabelul următor sunt afișate rezultatele:

Algoritm Planificare inițială (sec) Replanificare (sec)
Grafuri Graf 1 Graf 2 Graf 3 Graf 1 Graf 2 Graf 3
HEFT 0.012735022 0.014590614 0.018227081 0.013398438
0.015135797 0.015127996
CPOP 0.181340139 0.015713001 0.01670525 0.024019646 0.027852756 0.032510209
Hybrid
Heuristic Graf 1 Graf 2 Graf 3
0.02071694 0.018844517 0.022480983

4.3.2 Teste în funcție de codificarea algoritmilor

Capitolul 5 – Concluzii

5.1 Concluzii
Planificarea sarcinilor este o problemă importantă în domeniul calculului paralel.
Pentru rezolvarea ei s unt necesari algoritmi eficienți de planificare a taskurilor pentru a
utiliza eficient resursele și pentru a minimiza timpul total de planificare. Algoritmii de
planificare pot face uz de capacitatea de prelucrare a sistemului de rețea, îmbunătățind
astfel performanța aplicațiilor și producând un transfer optimizat. Problema planificării
implică opti mizarea mai multor obiective, inclusiv timpul de încheiere a execuției ,
prioritățile taskurilor, utilizarea resurselor, măsurători ale calității programului,
costurile, factorii de fiabilitate, cerințele sarcinilor față de resurse,etc. Mulți algoritmi
de planificare nu iau în considerare eșecul oricărei sarcini sau al oricărei resurse în
timpul planificării , respectiv posibilitatea ca nodul să producă o mare întârziere
planificării deși aparent sugerează o minimizare, iar ca un procesor să fie nevoit să
suporte execuție majorității sarcinilor, dezechilibrând astfel planificarea . Unii algoritmi
de planificare îmbunătățesc makespan -ul, dar provoacă un dezechilibru între sarcini
sever . Un algoritm eficient de planificare po ate fi proiectat în funcție de factoru l de
calitate pentru echilibrarea sarcinilor , precum și pentru îmbunătățirea ratelor de transfer
din cadrul program ului, în ciuda posibilelor eșecuri ale nodurilor din structură . Ace astă

metodă este foarte utilă pentru planificarea în acest domeniu deoarece există o
posibilitate pentru orice nod de a eșua din cauza mai multor factori.
Pentru a măsura calitatea și eficiența diferiților algoritmi și a metodelor de
planificare ar trebui să se compare performanțele obținute cu cele ale planificării
optim ale. Planificarea optimală este aceea care asigură un timp minim de execuție a
programului paralel. Atunci când soluția optimală nu poate fi atinsă, se încear că
rezolvarea planificării într -o manieră eficientă prin utilizarea unor euristici de
planificare care să conducă la găsirea unor soluții sub -optimale în timpi de execuț ie
rezonabili. Pentru marea majoritate a problemelor de planificare însă, soluția optimă nu
poate fi obținută. Din acest motiv, concluzii asupra eficienței unui algoritm de
planificare se pot stabili doar comparând performanțele acestuia cu performanțele altor
algoritmi de planificare cunoscuți în condițiile în care testele se efectuează asupra
acelorași seturi de date.
În această lucrare am prezentat doi algoritmi, HEFT și CPOP, pentr u planificarea
unor grafuri de sarcini interconectate pe un sistem de procesoare eterogene. Pentru
testare și comparare am folosit trei grafuri cu rezultate prezentate în capitolul 4,
secțiunea „Teste”. În urma acestor rezultate se poate constata că algori tmul HEFT
depășește ceilalți algoritmi în termeni de performanță și măsurători ale costurilor
incluzând raportul mediei lungimii planificării, viteză, frecvența celor mai bune
rezultate și media timpului de procesare. Datorită performanței sale robuste, a timpului
redus de rulare și a abilității de a oferi performanțe stabile peste o gamă largă de structuri
de grafuri, algo ritmul HEFT reprezintă o soluție viabi lă pentru problema p lanificării
DAG -urilor pe sisteme de resurse eterogene. Am observat de asemene a faptul că
algoritmul CPOP are performanțe mai bune și timp de rulare mai bun decât ceilalți
algoritmi.
Am prezentat de asemenea și alte metode pentru etapele de prioritizare și de
selecție a procesorului ale algoritmului HEFT, inclusiv o nouă metodă de selectare a
procesorului pe baza minimizării timpului EFT al nodului copil critic al fiecărui task
selectat.

5.2 Direcții viitoare
O viitoare cercetare asupra algoritmilor este investigarea compromisurilor dintre
calitatea pla nificărilor algoritmilor, ca de exemplu valorile medii ale makespan -ului și
numărul de procesoare disponibile. Aceasta ar putea aduce însă limite ale degradării
valorilor makespan -ului precum insuficiența numărului de procesoare disponibile. O
idee ar fi replanificarea algoritmului HE FT ca răspuns la schimbările de procesor și de
rețea a conexiunilor sarcinilor.
Adițional, se pot adăuga tehnici local e de căutare de un cost scăzut pentr u a
îmbunătăți calitatea algoritmilor . Activitatea viitoare va putea include tehnici diferite

pentru organizarea sarcinilor pregătite de execuție și extensii pentru etap a de selecție a
procesor ului.
În cele din urmă, evaluări suplimentare folosind diferite aplicații, valori de
execuție al e sarcini lor mai diversificate, etc ar oferi o perspectivă mult mai bună asupra
comportamentul ui algoritmilor .