Fire de executie si procese

MLFQ : Regulile de baza
In incercarea de a construi un astfel de planificator, MLFQ are un numar distinct de cozi, fiecare coada avand un nivel de prioritate diferita. La un moment de timp, o sarcina care e gata de rulat poate fi intr-o singura coada. MLFQ foloseste prioritatea pentru a stabili care sarcina ar trebui sa ruleze la un moment dat: o sarcina cu prioritatea cea mai mare va fi cea care va rula.

Desigur, mai mult de o sarcina poate sa fie intr-o coada data, si astfel ele au aceeasi prioritate. In acest caz, vom folosi planificarea round-robin printre aceste sarcini.

Astfel, cheia planificari MLFQ sta in modul cum planificatorul seteaza prioritatile. In loc sa dea fiecarei sarcini o prioritate fixa, MLFQ variaza prioritatea sarcini pe baza observari comportamentului acesteia.

• 
  Regula 1: Daca Prioritatea(A) > Prioritatea(B), A va rula (si B nu va rula).
  
• 
  Regula 2: Daca Prioritatea(A) = Prioritatea(B), atat A cat si B vor rula in modul round-robin.
  

Cum sa schimbi prioritatea?
Trebuie sa decidem cum MLFQ va schimba nivelul de prioritate pentru o sarcina (si astfel in ce coada se afla) de-a lungul timpului de viata al unei sarcini.

Pentru a face asta trebuie sa tinem minte incarcarea sarcinilor: un amestec de sarcini interactive care in mod frecvent elibereaza CPU si cateva sarcini care ruleaza mai mult “CPU bound”, sunt sarcini care au nevoie de mult timp al CPU-ului dar unde timpul de raspuns nu este important.

• 
  Regula 3: Cand o sarcina intra in sistem , ea este plasata in coada cu prioritatea cea mai mare.
  
• 
  Regula 4a: Daca o sarcina foloseste un intreg ciclu de timp in timp ce ruleaza, prioritatea sa este redusa ( este mutata mai jos in coada).
  
• 
  Regula 4b: Daca o sarcina elibereaza CPU inainte ca ciclul de timp sa se incheie, ea isi pastreaza acelasi nivel de prioritate.
  

In urma introduceri ultimelor trei reguli apar doua probleme. Daca sunt prea multe sarcini interactive in sistem, ele vor consuma tot timpul CPU-ului, si astfel sarcinile care ruleaza mai mult nu vor beneficia de timpul CPU-ului. A doua se refera la faptul ca un utilizator mai inteligent poate rescrie programul de planificare. Se refera la faptul ca utilizatorul incerca sa pacaleasca palnificatorul pentru a primi mai mult din partea de resurse care i se cuvine.

Idea care ne ajuta sa iesim din acest impas se refera la stimularea periodica a prioritati tuturor sarcinilor din sistem. Pentru aceasta le vom muta pe toate in coada cu prioritatea cea mai mare. Se impune astfel o noua regula.

• 
  Regula 5: Dupa o perioada de timp S, toate sarcinile din sistem vor fi mutate in coada cu prioritatea cea mai mare.
  

Regula noua rezolva doua probleme deodata. Prima se referea la faptul ca sarcinile stau in coada cu priotiatea cea mai mare, o sarcina va imparti astfel CPU-ul cu alte sarcini de prioritate ridicata conform metodei round-robin. A doua priveste “CPU bound”, si anume daca o sarcina devine interactiva, planificatorul o trateaza corespunzator de indata ce va primi stimularea prioritati.

Mai avem o problema de rezolvat si anume cum sa prevenim rescrierea programului de planificare.

Solutia care se impune aici este o contabilizare mai buna a timpului CPU-ului la fiecare nivel al MLFQ. Pentru aceasta vom rescrie regulile 4a si 4b intr-o singura regula.

• 
  Regula 4: O data ce o sarcina foloseste timpul alocat la un nivel dat(indiferent de cate ori a eliberat CPU), prioritatea sa este redusa.
  

Ciclul de timp al cozilor variaza. Astfel cozile cu prioritatea cea mai mare vor avea un ciclu de timp mai mic, iar cozile cu prioritatea cea mai scazuta vor avea ciclul de timp cel mai mare.
2.1.2.2 O (1) (Linux)
In timpul perioadei de dezvoltare Linux 2.5.x, un nou algoritm de planificare a fost unul dintre cele mai semnificative schimbari ale nucleului (kernel).

Planificatorul Linux 2.4.x, in timp ce era folosit la scara larga, sigur, si in general destul de bun, avea cateva caracateristici nedorite. Caracteristicile nedorite au fost complet incorporate in proiectarea lui, si astfel cand Ingo Molnar s-a ridicat la nivelul provocari de a-l perfectiona, el a proiectat un nou planificator in loc sa faca modificari la cel vechi. Faptul ca algoritumul de planificare Linux 2.4.x continea algoritmi O( n) a fost probabil cel mai mare defect, si ulterior noul planificator a utilizat numai algoritmi O( 1), aceasta a fost cea mai buna imbunatatire a planificatorului.

Ce este un algoritm O( 1)?
Un algoritm opereaza la intrare, si dimensiunea acelei intrari de obicei determina timpul de executie. Notatia O-mare este utilizata pentru a descrie rata de crestere a unei executi a unui algoritm bazat pe timp in functie de cantitatea de la intrare. De exemplu timpul de executie al unui algoritm O( n) creste liniar pe masura ce dimensiunea intrari n creste. Timpul de executie al unui algoritm O( n^2) creste patrat. Daca este posibil sa stabilim granita superioara constanta a unui algoritm cu executie in timp, acesta este considerat a fi algoritumul O( 1) (unul poate spune ca ruleaza in “in timp constant”). Astel un algortitm O( 1) este garantat sa termine intr-un anumit moment de timp indiferent de marimea intrari.

Planificatorul care foloseste algoritmul O( 1) se bazeaza pe tablouri de procese active si expirate pentru a atinge planificarea constanta a timpului. Fiecarui proces ii este dat un timp fix, dupa care este executat si mutat intr-un tablou expirat. O data ce toate sarcinile dintr-un tablu activ au epuizat timpul fix acordat si au fost mutate in tabloul expirat, un comutator de tablouri intervine. Acest comutator transforma tablou activ in nou tablou expirat, care este gol, in timp ce tabloul expirat devine tabloul activ.

Problema principala a acestui algoritm este utilizarea complexa pentru a marca o sarcina ca fiind interactiva sau non-interactiva. Algoritumul incearca sa identifice procese interactive prin analizarea timpului mediu de inactivitate ( starea de timp pe care o petrec procesele in astepatarea unei intrari). Procesele care sunt inactive pentru perioade mai lungi de timp probabil asteapta intrarea utilizatorului, astfel planificatorul ia decizia ca sunt interactive. Planificatorul da un bonus de prioritate sarcinilor interactive (pentru o mai buna tranzitie) in timp ce penalizeaza sarcinile non-interactive prin scadera prioritati acestora. Toate calculele pentru determinarea interactivitatea unei sarcini sunt complexe si supuse potentialelor erori de calcul, cauzand comportament non-interactiv din partea proceselor interactive.

Ce face ca planificatorul Linux 2.6.8.1 sa functioneze in timpul O( 1)?
Planificatorul Linux 2.6.8.1 nu contine nici un algoitm care sa ruleze mai prost decat O( 1). Astfel fiecare parte a planificatorului este garantata sa execute intr-un anumit moment constant de timp indiferent de cate multe sarcini sunt in sistem. Aceasta permite nucleului Linux sa manevreze in mod eficient numere masive de sarcini fara a creste costuri suplimentare pe masura ce numarul de sarcini creste. Sunt doua structuri de date cheie aici in planificatorul Linux 2.6.8.1 care permit acestuia sa execute sarcinile sale in O( 1), si proiectarea sa se invarte in jurul lor – cozi de executie si tablouri de prioritate.
2.1.2.3 Completely Fair Scheduler ( Linux)
Ingo Molnar, autorul CFS-ului afirma: “CFS in mod uzual modeleaza un CPU ideal, precis, multitasking pe hardware real.”

Sa incercam sa intelegem ce inseamana “CPU ideal, precis, multitasking”, pe masura ce CFS incearca sa imite acest CPU. Un “CPU ideal, precis, multitasking” este un hardware CPU care poate sa ruleze mai multe procese in acelasi timp (in paralel), dand astfel fiecarui proces o parte egala din puterea procesorului (nu timp, ci putere). Daca un singur proces ruleaza, el va receptiona 100% din puterea procesorului. Cu doua procese in executie, fiecare va avea exact 50% din puterea fizica (in paralel). Similar, cu patru procese ruland, fiecare va primi precis 25% din puterea fizica a CPU-ului in paralel.

Astfel CPU va fi “corect” cu toate sarcinile care ruleaza in sistem (Figura 1).

Figura 1

In mod clar, acest CPU ideal nu exista, dar CFS incearca sa imite un astfel de procesor in modul software. Pe un CPU actual din lumea reala, doar o sarcina poate fi alocata la un moment particular de timp. Din acest motiv, toate celelalte sarcini asteapta in decursul acestei perioade. Deci, pe masura ce sarcina curenta primeste 100% din puterea CPU-ului, toate celelalte sarcini primesc 0% din puterea CPU-ului. Acest lucru in mod evident nu este corect( Figura 2).

Figura 2
CFS incearca sa elimine aceasta lipsa de dreptate din sistem. CFS incearca sa tina evidenta parti corecte a CPU care a fost disponibila fiecarui proces din sistem. Deci, CFS ruleaza un ceas de corectitudine la o fractiune din viteza ceasului real al CPU-ului. Rata de crestere a ceasului de corectitudine este calculata prin divizarea timpului de obstacol ( in nanaosecunde) prin numarul total de procese care asteapta. Valoarea rezultata este momentul de timp al CPU cu care fiecare proces este indreptatit.

In timp ce un proces asteapta dupa CPU, planificatorul urmareste cantitatea de timp care ar fi fost folosita pe un procesor ideal. Acest timp de asteptare, reprezentat de timpul variabil de asteptare pe sarcina, este folosit pentru a clasa procesele pentru planificator si pentru a determina cantitatea de timp pentru care proceselor le este permis sa execute inainte de a fi modificate.

Procesul cu timpul de asteptare cel mai lung este luat de planificator si asignat CPU-ului. Cand acest proces ruleaza, timpul lui de asteptare este decrementat, pe cand timpul altor sarcini care asteapta creste. Aceasta inseamana ca dupa o perioada de timp, va fi o noua sarcina cu cel mai mare timp de asteptare, si sarcina curenta care ruleaza va fi modificata.

Folosind acest principiu, CFS incearca sa fie corect cu toate sarcinile si intotdeauna incearca sa aibe un sistem cu timp de asteptare zero pentru fiecare proces- fiecare proces are o parte egala din CPU ( acest lucru ar fi incercat sa faca un “CPU ideal, precis, multitasking”).

Pentru ca un CFS sa imite un “CPU ideal, precis, multitasking”, dand fiecarui proces o parte egala din timpul de executie el trebuie sa contina urmatoarele:

1. 
   Un mecanism care sa caluleze care este partea corecta din CPU care se cuvine fiecarui proces. Aceasta este indeplinita prin utilizarea unuei variabile “system-wide runqueue fair_clock” (cfs_rq->fair_clock). Acest ceas de corectitudine ruleaza la o farctiune din timpul real, pentru ca astfel sa ruleze la pasul ideal pentru o singura sarcina cand sunt N sarcini care ruleaza in sistem.
   
2. 
   Un mecanism care sa tina evidenta timpului pentru fiecare proces care asteapta in timp ce CPU a fost asignat cu rularea sarcini curente. Acest timp de asteptare este acumulat in “wait_runtime” variabilele pre-proces (process->wait_runtime).
   

Petre Marian Alin (434 Aa)

2.2 Algoritmi de alocare a resurselor in sistemele multiprocesor

Cresterea volumului de calcule efectuate de aplicatiile software moderne, de la servere de baze de date si servere web la programe de simulare complexe si aplicatii grafice 3D a adus necesitatea creearii de calculatoare din ce in ce mai rapide. Insa, datorita limitarilor tehnicilor VLSI actuale, viteza unui procesor nu este suficient de mare pentru a putea rula anumite tipuri de aplicatii.

Solutia la aceasta problema a fost impartirea aplicatiilor in taskuri care sa poata fi executate in paralel pe un numar mare de procesoare interconectate. Astfel, programe foarte complexe pot fi rulate intr-un timp rezonabil folosind supercalculatoare cu mii de procesoare interconectate, sau pot fi rulate distribuit pe un numar mare de statii in solutii de tipul Cloud Computing.

Principala problema a acestei abordari este alocarea eficienta a timpului fiecarui procesor, pentru a optimiza timpul de rulare al aplicatiei. Aceasta este o problema din punct de vedere computational, solutiile reprezentand compromisuri intre calitatea solutiilor si complexitatea si scalabilitatea algoritmilor folositi.

De asemenea, apare si problema dependentei intre taskuri, astfel ca se intalnesc des situatii in care executia unui task trebuie sa fie in mod necesar precedata de executia altor taskuri.

Problema poate fi modelata matematic folosind grafuri aciclice orientate. Astfel, fiecare nod al grafului reprezinta un task ce trebuie executat. O muchie orientata dinspre taskul T_i spre taskul T_jreprezinta faptul ca executia lui T_j este conditionata de executia prealabila a lui T_i. Valoarea fiecarui nod reprezinta timpul necesar executiei taskului respectiv pe unul dintre procesoarele sistemului ( acestea sunt considerate omogene ). Ponderea asociata fiecarei muchii reprezinta intarzierea de comunicare intre cele 2 taskuri. Problema este reprezentata de maparea taskurilor pe un set de procesoare, respectand dependentele dintre ele, si obtinerea unui timp de executie minim.

Datorita complexitatii problemei, obtinerea unei solutii optime nu este fezabila. In continuarea lucrarii sunt prezentati o serie de algoritmi care incearca sa gaseasca solutii cat mai apropiate de optim. Acesti algortmi sunt impartiti in doua categorii principale: algoritmi one-shot, care printr-o singura parcurgere a grafului incearca sa ghiceasca solutia optima si algoritmi iterativi, care, prin parcurgeri repetate, optimizeaza solutia initiala.

Sindrilaru Florin (433 A)

2.2.1 Algoritmi one-shot
2.2.1.1 Min-min

Programarea euristica min-min, prezentata de Ibbara si Kim, poate fi folosita pentru a programa un grup de sarcini fara dependente pe un sistem multiprocesor eterogen. Min-min este un algoritm simplu care selecteaza o sarcina Ti, cu minimum timp de completare pe orice procesor de la U, grupul de sarcini nemapate/nemarcate, si le programeaza pe procesor, care are minimum de timp de completare.

Acelasi alogoritm, cu mici modificari, poate fi aplicat pentru problema sarcinilor cu dependente. In prezenta dependentelor, toate sarcinile de la U, nu se pot compara, pentru ca timpii de completare nu se pot calcula pentru o sarcina daca toti predecesorii nu sunt deja mapati la un procesor. Asadar, numai acele sarcini pentru care toti predecesorii au fost deja mapati (acele sarcini pentru care toti predecesorii sunt in U) pot fi selectati pentru compararea timpului de completare. In al doilea rand, calculul timpilor de completare contine atat timpul de executie al sarcinii cat si timpul la care sarcina e gata de executie. Algoritmul min-min este foarte simplu, usor de implementat si a fost unul dintre cele mai rapide algoritme de comparatie.
2.2.1.2 Chaining

Chaining, propus de Djordjevic si Tosic, este un algoritm deterministic intr-un singur pas bazat pe tehnici de listare. In programarea eurisitca, numai sarcinile pregatite sunt considerate pentru mapare. Inlantuirea invinge aceasta constrangere prin permiterea si sarcinilor nepregatite pentru mapare. Asadar, sarcinile pot fi aranjate pentru mapare in orice ordine, indiferent de dependenta sarcinii.

Chainingul incearca sa imparta graficul sarcinii intre procesoare si nu permite duplicarea sarcinilor. Algoritmul incepe cu un grafic al sarcinii partial programat care este graficul sarcinii originale la care doua sarcini false cu timpul de executie zero, s si q sunt adaugate. Fiecare procesor incepe cu executarea sarcinii false s si termina cu executarea sarcinii false q. Toate celelalte sarcinii sunt executate doar o singura data. Atatea p-margini ca si procesoare sunt adaugate intre s si q. Fiecare p-margine de la s la q reprezinta ordinea executiei a unui singur procesor. In fiecare iteratie a algoritmului sunt doua etape majore : selectia sarcinii si selectia unei p-margini. In selectia sarcinii, in primul rand se alege o sarcina si apoi o p-margine. O sarcina care are cea mai mica mobilitate, ex. o sarcina cu timpi mari de executie si timpi mari de intarziere, este selectata in etapa alegerii sarcinii. Sarcina este mutata la o p-margine prin plasare in care marimea celei mai lungi rute care trece prin sarcina este minima. Graficul partial organizat al sarcinii este updatat prin inlaturarea a tuturor non p-marginilor dintre sarcina actuala si sarcinile care sunt deja selectate pe p-margine. Acest proces este continuat pana ce toate sarcinile au fost alocate unui procesor (mutate la o p-margine).

2.2.1.3 (HLFET) Highest Level First with Estimated Time

Algoritmul HLFET (primul cel mai ridicat nivel cu timp estimat), propus de Adam, este un algoritm de organizare in lista care atribuie prioritatea organizarii pe fiecare nod plasat pe nivelul static b-level, care este marimea celei mai lungi rute de la un nod la un nod de iesire, fara a lua in considereare lungimea marginii (sau timpul necesar comunicarii). De exemplu, in figura de mai sus, sa presupunem ca numarul din stanga fiecarui cerc reprezinta timpul executarii sarcinii. Cea mai lunga ruta de la nodul T1 la nodul de iesire T5 este T1, T3, T5. Asadar, nivelul static b al lui T1 = 1 + 3 + 2 = 6; nivelul static b al lui T4 este 3, deoarece T4 este insusi un nod de iesire. Similar, nivelele statice b ale lui T2 si T3 sunt 4 respectiv 5.

Dupa ce toti predecesorii acestei sarcini au fost organizati, sarcina este pusa pe o lista de sarcini gata pregatite. Aceasta lista este aranjata intr-o ordinde descrescatoare a nivelurilor statice b. Nodurile care au aceleasi valori ale nivelului static b sunt selectate la intamplare. Pentru a obtine o mai buna organizare , prima sarcina din lista celor pregatite este intotdeauna alocata unui procesor care permite cea mai rapida executie utilizand metoda noninseritiei. Lista sarcinilor pregatite se updateaza constant si procesul de organizare este repetat pana cand toate sarcinile au fost organizate. Folosind nivelurile statice b simplifica organizarea deoarece nicelurile statice b sunt constante pe parcursul intregului proces de organizare; cu toate aceastea, nu este optim deoarece nu a luat in considerare timpul de comunicare ca factor al prioritatii organizarii sarcinilor. In plus, algoritmul HLFET utilizeaza metoda noninsertiei si un slot de timpi inactivi nu sunt utilizati, care afecteaza imbunatatirea performantei.

2.2.1.4 Insertion scheduling heurisitic (ISH)
Algoritmul ISH (Introducerea de programare eurisitca), propus de Kruatrachue si Lewis, imbunatateste algoritmul HLFET prin utilizarea sloturilor cu timpi inactivi in programare. Initial foloseste aceeasi abordare ca si algoritmul HLFET pentru a face o lista cu sarcini pregatite pe baza nivelurilor statice b si organizeaza primul nod in lista utilizand metoda noninsertiei. Diferenta este ca atunci cand un nod este programat creeaza un slot cu timp inactiv, ISH verifica daca o sarcina din lista poate fi inserata in acel slot dar nu poate fi programata mai devreme pe un alt procesor. Programeaza astfel cat mai multe sarcini posibile in acel slot cu timpi inactivi.
2.2.1.5 Duplication scheduling heuristic (DSH)

Duplicarea programarii euristice (DSH), propusa de Kruatrachue si Lewis, este diferita fara de algoritmul HLFET si algoritmul ISH, care nu permit clonarea sau duplicarea sarcinilor. Algoritmul DSH multiplica niste predecesori in diferite procesoare astfel incat fiecare copil poate incepe cat mai devreme posibil prin eliminarea intarzierilor de comunicatie. Atunci cand un nod creeaza un slot cu timpi inactivi, algoritmul incearca sa multiplice cat mai multi predecesori posibili in slot daca predecesorii duplicati pot imbunatatii timpul de start al acelui nod. Initial, nivelul static b al fiecare nod bazat pe diagrama DAG este calculat si toate nodurile sunt puse in ordine descendenta in functie de nivelul static b. Nodul pregatit Ni cu cel mai mare nivel static b este selctat ca un candidat si programat primul si testat pe fiecare din procesoare. Daca nodul Ni creeaza un slot cu timp inactiv in unul din procesoare, atunci parintele Np al acestui nod care nu este programat in acest procesor si are cel mai indelungat timp de asteptare este considerat pentru duplicare. Daca aceasta are loc cu succes, timpul de start al nodului Ni este ajustat si Np este considerat candidat. Parintii lui Np sunt cautati din urma si acest proces se repeta pana nu se mai permite multiplicarea sau numai exista noduri de intrare. Sarcina selectata Ni ar trebui programata in procesorul care ofera timpul de start cel mai scazut.

Ahmad si Kwok au modificat algoritmul DSH in algoritmul numit Bottom-Up Top-Down Duplication Heuristic (BTDH). Marea imbunatatire a acestui algoritm BTDH fata de algoritmul DSH este ca BTHD continua multiplicarea predecesorilor unui nod chiar daca slotul timpului de duplicare este complet folosit in speranta ca timpul de start va fi minimalizat. In orice caz, autorii spus ca performanta celor doi algoritmi este apropriata.
Petre Marian Alin (434 Aa)

2.2.2 Algoritmi de cautare iterativa

2.2.2.1 Algoritmi genetici

Aceasta clasa de algoritmi emuleaza mecanismele naturale de variatie genetica si selectie. Se porneste cu alegerea unei codari a spatiului solutiilor sub forma unor “cromozomi” binari. “Genele” acestor cromozomi sunt reprezentate de elemente ireductibile ale solutiei, in acest caz asocieri intre un anumit task, un procesor al sistemului si perioada de timp in care acel task va rula. Functionarea algorimului este urmatoarea:

• 
  Se porneste de la un anumit set cromozomi generati aleator, care reprezinta prima generatie de solutii.
  
• 
  Acest set este evaluat de o functie de fitness, care determina care sunt cele mai bune solutii din generatia curenta si le foloseste pe acestea pentru a genera urmatoarea generatie de solutii. Este ideal ca si o parte a solutiilor slabe sa fie selectata, pentru a garanta diversitatea urmatoarei generatii. Aceasta actiune impiedica convergenta prea rapida a algoritmului intr-un set de solutii sub-optime.
  
• 
  Urmatoarea generatie de solutii este creata prin variatii ale solutiilor selectate din generatia curenta. Se folosesc in general doua metode de variatie, ambele inspirate de variatii naturale ale AND-ului. Prima metoda este mutatia, care implica variatia aleatoare a uneia sau mai multor gene. A doua metoda este cross-over, care implica schimbarea unei secvente de gene intre doi cromozomi.
  
• 
  Functia de fitness este aplicata acestei generatii, iar procesul continua pana cand o solutie suficient de buna este gasita.
  

Algoritmii genetici sunt algoritmi nedeterministi, deci pot avea mari variatii de performanta. In cazul alocarii taskurilor in sisteme multiprocesor, acestia dau rezultate bune.
2.2.2.2 A*

Algoritmul A* este un algoritm heuristic de cautare de tip best –first. Este un algoritm de cautare in arbori care incepe cu o solutie nula, apoi ajunge la solutie printr-o serie de solutii partiale. Solutia nula inseamna, in cazul nostru, ca nici un task nu va fi alocat pe nici un procesor. Solutiile partiale sunt obtinute alocand un task pe toate procesoarele posibile.

Fiecare alocare este o solutie partiala diferita, deci fiecare nod are p copii, unde p este numarul de procesoare. In fiecare nod, solutia partiala are un task in plus mapat fata de nodul parinte. Numarul total de noduri este limitat astfel incat sa se evite o crestere exponentiala a timpului de executie.

Pentru fiecare nod se aplica functia de cost f(n) = g(n) + h(n), unde g(n) este timpul de procesor total care mai este disponibil si h(n) reprezinta estimarea minim a timpului necesar pentru executia taskurilor ramase. Pentru a limita dimensiunea arborelui, nodurile cu cea mai mare valoare a f(n) sunt eliminate atunci cand numarul total de noduri depaseste limita admisa. Implementare acestui algoritm in pseudocod este:

function A*(start,goal)

closedset := the empty set // Setul de noduri care au fost deja evaluate

openset := set containing the initial node //Setul de noduri posibile ce var fi evaluate

g_score[start] := 0 //Distanta de la start pe traseul optim

h_score[start] := heuristic_estimate_of_distance(start, goal)

f_score[start] := h_score[start] // Estimated total distance from start to goal through y.

while openset is not empty

x := the node in openset having the lowest f_score[] value

if x = goal

return reconstruct_path(came_from[goal])

remove x from openset

add x to closedset

foreach y in neighbor_nodes(x)

if y in closedset

continue

tentative_g_score := g_score[x] + dist_between(x,y)

if y not in openset

add y to openset

tentative_is_better := true

elseif tentative_g_score < g_score[y]

tentative_is_better := true

else

tentative_is_better := false

if tentative_is_better = true

came_from[y] := x

g_score[y] := tentative_g_score

h_score[y] := heuristic_estimate_of_distance(y, goal)

f_score[y] := g_score[y] + h_score[y]

return failure
function reconstruct_path(current_node)

if came_from[current_node] is set

p = reconstruct_path(came_from[current_node])

return (p + current_node)

else

return current_node

2.2.2.3 Simulated annealing

Aceasta clasa de algoritmi este inspirata de un proces metalurgic ce consta in incalzirea unui metal urmata de racirea lui treptata, pentru a obtine o structura cristalina cat mai rezistenta. Atunci cand metalul este incalzit, atomii instabili sunt scosi din starea lor de energie si trecuti in stari superioare. Odata cu racirea metalului, atomii acestuia tind spre stari de energie minime, imbunatatind astfel proprietatile structurii cristaline. Prin repetarea procesului, metalul se apropie tot mai mult de o structura cristalina perfecta, de energie minima.

In cazul problemei noastre, se foloseste o varianta simplificata a algoritmului : mai intai toate taskurile sunt etichetate in functie de pozitia topologica in graf. Toate taskurile care

sunt asignate aceluiasi procesor sunt executate secvential in functie de eticheta. Temperatura sistemului este scazuta la fiecare noua generatie. In fiecare noua generatie, o solutie este generata prin modificarea aleatoare a solutiei curente. Aceasta modificare se face prin eliminarea unui task sau schimbarea intre doua taskuri. Noul rezultat este evaluat de functia de fitness. Daca acesta este mai bun sau mai slab in anumite limite decat rezultatul precedent, rezultatul precedent este inlocuit. Algoritmul se opreste atunci cand temeperatura ajunge la o valoare predefinita. Algoritmul este urmatorul:

• 
  initializeaza solutia
  
• 
  estimeaza temperatura initiala
  
• 
  evalueaza solutia
  
• 
  daca solutia este acceptabila, inlocuieste solutia precedenta
  
• 
  ajusteaza temperatura
  
• 
  daca temperatura a atins o valoare predefinita, opreste algorimul;
  

altfel, genereaza o noua solutie.
2.2.2.4 Tabu search

Tabu search este o tehnica de cautare in vecinatati care incearca se evite minimele locale si incearca sa ghideze cautarea spre un minim global.

Algoritmul este initializat cu o solutie initiala, care poate fi obtinuta cu un algoritm heuristic de tip one-pass, si cauta in vecinatatile soultiei curente, adica toate solutiile care difera de aceasta printr-o singura permutare. Pentru problema de alocare a taskurilor in sisteme multiprocesor, o permutare reprezinta mutarea unui task de pe un procesor pe altul sau schimbarea ordinii executiei taskurilor pe acelasi procesor. Aceasta tehnica considera toate mutarile posibile in vecinatatea imediata si o alege pe aceea cu cel mai mic timp total de executie posibil.
2.2.3 Concluzii

In aceasta sectiune vor fi folosite rezultatele studiului “A performance study of multiprocessor task scheduling algorithm” de S. Jin, G. Schiavone si D. Turgut.

Acest studiu testeaza eficienta algoritmilor mentionati anterior la rezolvare alocarii timpului de procesor pt doi algorimi: eliminarea Gauss-Jordan si factorizare LU a matricilor.

Grafurile de taskuri rezultate pentru cele doua probleme sunt prezentate in figurile 1 si 2.

Figura 1: Graful de taskuri pentru algoritmul de factorizare LU cu 35 de taskuri

Figura 2: Graful de taskuri pentru eliminare Gauss-Jordan cu 36 de taskuri.

Timpul toatal de procesare ( makespan )obtinut de fiecare algoritm in functie de numarul de taskuri este prezentat in figurile 3 si 4.

Figura 3: Makespan obtinut pentru factorizarea LU
Figura 4: Makespan obtinut pentru eliminarea Gauss-Jordan

Din comparatia celor noua algoritmi se obtin urmatoarele concluzii : DSH a avut cel mai scurt timp de executie si a obtinut cele mai bune alocari ale timpului de procesor. Algoritmii one-pass fara duplicarea taskurilor au obtinut rezultate bune si au avut timpi de executie scurti. Algoritmii de cautare iterativa au avut timpi de executie foarte ridicati, insa au obtinut makespan-uri foarte scurte. Folosirea acestora este justificata pentru a face o alocare a taskurilor pentru un algoritm ce va fi rulat de foarte multe ori, alocare ce va fi calculata antrerior executiilor si va fi folosita repetat.