Echilibrarea încărcării în sistemele distribuite - limite și posibilități

1. INTRODUCERE

Utilizarea in paralel a mai multor procesoare duce la obtinerea unei puteri de calcul mai ridicate decit s-ar putea realiza cu cel mai performant sistem uniprocesor. Performanta aplicatiilor pentru un sistem paralel depinde de eficienta cu care este utilizat fiecare procesor in parte.

Pentru a obtine o utilizare eficienta a procesoarelor se folosesc metode de planificare: acestea determina modul in care programele trebuiesc distribuite procesoarelor in asa fel incit sa se optimizeze performanta sistemului. In functie de cind se iau deciziile de planificare, relativ la momentul executiei programului, metodele de planificare se subinpart in metode statice si metode dinamice.

Algoritmii de planificare dinamica au la baza deciziilor incarcarea nodurilor, eficienta lor fiind strins legata de calitatea masurilor folosite. Masura incarcarii este deci un alt domeniu care influenteaza performanta sistemului.

Pentru a forma o imagine cadru, se prezinta in cele ce urmeaza limitarile impuse si posibilitatile oferite de fiecare dintre aceste domenii. In final este prezentata o noua metoda de calcul a incarcarii procesoarelor.

2. PLANIFICAREA STATICA

In planificarea statica atribuirea proceselor elementelor de procesare se face la momentul compilarii cu telul minimizarii timpului total de executie al programului si al reducerii intirzierilor introduse de comunicatie.

Metodele de planificare statica folosesc ipoteza ca procesele unui program paralel, impreuna cu relatiile dintre ele, sint definite inainte ca operatiile de planificare sa inceapa. Totodata, informatia privitoare la timpul de executie si la intirzierile in comunicatie sint presupuse cunoscute inainte de momentul executiei programului. In general metodele de planificare sint non-preemptive, adica, sarcinile sint executate pina la sfirsit pe procesorul care le-a fost alocat.

Doua modele de baza sint folosite in reprezentarea programelor paralele: graful static al sarcinilor (STG) [1, 2] si graful aciclic directionat (DAG) [3, 4].

In modelul bazat pe graful static al sarcinilor STG, programul paralel este reprezentat printr-un graf nedirectionat, conex, in care nodurile sint sarcini ale programului iar arcele intre noduri arata ca sarcinile asociate nodurilor comunica intre ele. Graful este constituit dintr-un numar de noduri de pornire (cu care programul incepe), un numar de noduri de oprire (cu care programul se termina) si noduri intermediare. Intregul set de noduri este legat de arce care au asociate ponderi indicind intirzierea introdusa de comunicatie.

In modelul bazat pe grafuri aciclice directionate programul este reprezentat de un DAG, in care nodurile reprezinta sarcinile din program iar arcele directionate atit dependentele (precedenta) intre noduri cit si comunicatia intre ele. Grafului i se asociaza doua functii: una pentru a determina dimensiunea unui task asociat unui nod (timpul de executie) si alta care determina intirzierea in comunicatia care are loc pe un arc dat.

Un alt model introdus recent are la baza graful temporal al comunicatiei (TCG) [5]. Acest model inglobeaza modele STG si DAG si poate identifica fazele sincrone ale comunicatiei si procesarii. In plus, TCG poate fi folosit pentru a descrie comportamentul temporal al programelor paralele.

Pentru a putea folosi reprezentarile sub forma de graf ale programelor, se asociaza si sistemului multiprocesor un graf in care nodurile reprezinta elementele de procesare iar arcele legaturile de comunicatie intre procesoare. Pe baza acestei formalizari, avind graful programului si graful procesor, planificarea statica devine problema maparii grafului programului pe graful procesor cu scopul minimizarii timpului de executie al programului.

Metode de planificare statica

In general, problema planificarii statice, cu sau fara intirzieri in comunicatie, s-a dovedit a fi NP-complexa. Din acest motiv, eforturile din acest domeniu s-au concentrat asupra dezvoltarii de:

- planificari optimale pentru cazuri speciale,

- solutii local optimale,

- metode suboptimale.

Impunind restrictii in structura grafului program si/sau in structura sistemului multiprocesor se pot obtine planificari optimale. Restrictii tipice pentru obtinerea unor planificari optimale sint DAG-uri organizate ca arbori, seturi de procesoare complet conexe sau limitarea numarului de procese si elemente de procesare.

Metodele de planificare optimale local se bazeaza pe tehnici de cautare eficiente pentru a gasi solutia optimala in spatiul solutiilor unei probleme. Intrucit aceste metode adesea nu garanteaza gasirea unei solutii optimale global, ele sint cunoscute ca metode local optimale. Algoritmii din aceasta clasa se pot clasifica:

- metode bazate pe simularea difuziei caldurii: cautarea unei solutii optimale consta din mici schimbari aleatoare ale unei planificari initiale urmate de evaluarea noii planificari. Acest proces este continuat iterativ pina cind nu se mai obtin imbunatatiri in planificarea generata.

- metode de programare matematica: se bazeaza pe tehnici de programare in intregi, liniara sau nonliniara. Procesul consta din definirea unei functii de minimizat, a unui set de restrictii si aplicarea unei metode pentru a rezolva problema de optimizare.

- metode de cautare in spatiul starilor: procesul consta din construirea unui arbore de cautare pentru spatiul planificarilor posibile, definirea unei functii de evaluare a costului cautarii, si cautarea in arbore a celei mai bune solutii prin eliminarea cailor catre solutii inacceptabile.