aplicat¸ii ale inteligent¸ei artificiale în sistemele ... rez.pdf · •capitolul 3 se axeaza...
TRANSCRIPT
UNIVERSITATEA TEHNICA“GHEORGHE ASACHI” DIN IASI
Scoala Doctorala a Facultatii de
Automatica si Calculatoare
Aplicatii ale Inteligentei Artificiale înSistemele Distribuite Heterogene
– REZUMATUL TEZEI DE DOCTORAT–
Conducator de doctorat:
Prof. Univ. Dr. Mitica Craus
Doctorand:
Ing. Adrian Alexandrescu
IASI – 2012
Teza de doctorat a fost realizata cu sprijinul financiar al proiectului “Bu-
rse Doctorale pentru Performanta în Cercetare la Nivel European (EURO-
DOC)”.
Proiectul “Burse Doctorale pentru Performanta în Cercetare la Nivel
European (EURODOC)”, POSDRU/88/1.5/S/59410, ID 59410, este un
proiect strategic care are ca obiectiv general “Dezvoltarea capitalului uman
pentru cercetare prin programe doctorale pentru îmbunatatirea participa-
rii, cresterii atractivitatii si motivatiei pentru cercetare. Dezvoltarea la nivel
european a tinerilor cercetatori care sa adopte o abordare interdisciplinara
în domeniul cercetarii, dezvoltarii si inovarii”.
Proiect finantat în perioada 2009 - 2012.
Finantare proiect: 18.943.804,97 RON
Beneficiar: Universitatea Tehnica “Gheorghe Asachi” din Iasi
Partener: Universitatea “Babes Bolyai” din Cluj-Napoca
Director proiect: Prof. univ. dr. ing. Mihaela-Luminita LUPU
Responsabil proiect partener: Prof. univ. dr. ing. Alexandru OZUNU
Cuprins
Cuprins i
1 Introducere 11.1 Contextul problemei . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . 1
1.2 Principalele Contributii . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . 11.3 Organizarea tezei . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . 2
2 Concepte utilizate 42.1 Sistemele Distribuite Heterogene . . . . . . . . . . . . . . . . . .. . . . . . . . . 4
2.1.1 Echilibrarea Încarcarii . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42.1.2 Toleranta la Defecte . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . 4
2.1.3 Scalabilitatea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 42.2 Inteligenta Artificiala . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2.1 Algoritmul Genetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 52.2.2 Reteaua Neuronala Artificiala . . . . . . . . . . . . . . . . . . . . . . . . 6
2.3 Maparea task-urilor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . 6
2.3.1 Notiuni utilizate în maparea task-urilor . . . . . . . . .. . . . . . . . . . . 62.3.2 Indicatorii eficientei unei solutii . . . . . . . . . . . . .. . . . . . . . . . 8
3 Maparea Task-urilor Utilizând Algoritmi Genetici în Sist emele Distribuite Hetero-gene 93.1 Consideratii Generale . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . 9
3.2 Algoritmul Genetic cu Mutatie Inteligenta(Genetic Algorithm with a Smart Mutation - GASM) . . . . . . . . . .. . . . . . 9
3.2.1 Structura Algoritmului . . . . . . . . . . . . . . . . . . . . . . . . .. . . 93.2.2 Concluzii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.3 Algoritmul Genetic cu o Mutatie în 3 Pasi
(The Genetic Algorithm with a 3-Step Mutation - GA3SM) . . . . .. . . . . . . . 113.3.1 Structura Algoritmului . . . . . . . . . . . . . . . . . . . . . . . . .. . . 11
3.3.2 Concluzii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133.4 Algoritmul de optimizare a emtodei GA3SM
(The Optimization Genetic Algorithm - OGA) . . . . . . . . . . . . . .. . . . . . 133.4.1 Structura Algoritmului . . . . . . . . . . . . . . . . . . . . . . . . .. . . 14
4 Studiu de Caz: Procesarea Eficienta a Datelor Primite de la Senzori într-un Mediude Mari Dimensiuni 154.1 Contextul Problemei . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . 154.2 Euristica Weighted Minimum Completion Time (WMCT) . . . .. . . . . . . . . . 16
4.2.1 Structura Algoritmului . . . . . . . . . . . . . . . . . . . . . . . . .. . . 164.2.2 Concluzii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
4.3 Controller-ul Inteligent pentru Optimizarea Fluxuluide Date (Intelligent Data FlowController - IDFC) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
i
4.3.1 Consideratii Generale . . . . . . . . . . . . . . . . . . . . . . . . .. . . . 16
4.3.2 Arhitectura Controller-ului . . . . . . . . . . . . . . . . . . . .. . . . . . 184.3.3 Neural Network Mapping Heuristic . . . . . . . . . . . . . . . . .. . . . 194.3.4 Genetic Algorithm Mapping Heuristic . . . . . . . . . . . . . .. . . . . . 19
4.3.5 Capacitatea sistemului de a se adapta la schimbari, toleranta la defecte siverificari de performanta . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
5 Evaluarea Metodelor Propuse 225.1 Platforma de Simulare a Maparii Task-urilor
(Task Mapping Simulation Framework - TMSF) . . . . . . . . . . . . . .. . . . . 22
5.2 Evaluarea Algoritmului Genetic de Optimizare . . . . . . . .. . . . . . . . . . . . 225.3 Evaluarea euristicilor GASM si GA3SM . . . . . . . . . . . . . . .. . . . . . . . 22
5.3.1 Parametrii Simularii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
5.3.2 Rezultate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235.4 Evaluarea euristicii WMCT . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . 23
5.4.1 Parametrii Simularii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235.4.2 Rezultate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
5.5 Evaluarea IDFC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 255.5.1 Parametrii Simularii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
5.5.2 Rezultate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
6 Stadiul Actual 276.1 Stadiul Actual în Domeniul Maparii Task-urilor . . . . . . . . . . . . . . . . . . . 276.2 Stadiul Actual în Domeniul Procesarii Datelor Primite de la Senzori si în Domeniul
Maparii Task-urilor cu Prioritati si Termene Limita . . . . . . . . . . . . . . . . . 27
7 Concluzii 28
Bibliografie 29
ii
1 Introducere
1.1 Contextul problemei
Evolutia permanenta a tehnologiilor a atins un nivel la care se resimte o nevoie urgenta pentrurezolvarea problemelor cu cerinte computationale ridicate, a caror solutionare nu poate fi oferita de
o singura unitate de calcul. Pentru a raspunde acestor cerinte s-au implementat sisteme distribuiteeterogene de mare capacitate computationala. Un astfel de sistem utilizeaza unitati de procesare
care dispun de resurse diferite si care sunt de regula conectate la o retea de mare viteza.În sistemele distribuite eterogene, task-urile trebuie mapate la unitati de procesare într-un mod
cât mai eficient. Maparea unui task consta în asignarea acelui task la o anumita unitate de procesare
urmata de planificarea acelui task la unitatea respectiva. Studii si comparatii ale celor mai impor-tante tehnici de mapare pot fi regasite în lucrari precum [Braun 2001], [Siegel 2000], [Braun 2008]
si [Magoules 2009]. Metoda de mapare aleasa depinde de sistemul computational eterogen anali-zat. Sistemele de calcul pot avea o eterogenitate a unitatilor de procesare variabila ceea ce duce la
fluctuatii semnificative între timpii de executie ai unui task pe unitatile din sistem. Task-urile caretrebuie mapate pot fi independente sau inter-dependente sipot avea prioritati, termene limita sau
versiuni diferite. O metoda de mapare eficienta ia în considerare toate caracteristicile task-urilor siale unitatilor de procesare.
Aceasta lucrare se axeaza pe metode de crestere a eficientei procesarii de task-uri într-un sistem
distribuit eterogen. Din cauza ca spatiul de cautare este extrem de vast, euristicile de mapare suntfolosite pentru a rezolva problema maparii task-urilor prin asignarea acestora la cele mai indicate
unitati de procesare, urmarindu-se o buna încarcare a echilibrarii. Sunt situatii când task-urileau prioritati si termene limita si, pentru a obtine o solutie de calitate, trebuie luati în calcul alti
indicatori de eficienta care aplica penalitati acelor task-uri care îsi termina executia dupa termenullimit a.
1.2 Principalele Contributii
Contributia I:
Un algoritm genetic cu mutatie inteligenta pentru maparea task-urilor independente
la unitati de procesare
Algoritmul genetic propus imbunatateste durata de executie a algoritmului prin lipsa operatorului
de crossover si obtine un makespan foarte bun prin utilizarea unei mutatii inteligente. ContributiaI a fost prezentata initial în [Alexandrescu 2010a].
Contributia II:
Un algoritm genetic cu o mutatie în trei pasi pentru maparea task-urilor independente
la unitati de procesare
Scopul algoritmului cu o mutatie în trei pasi este de grabi convergenta la o solutie superioara cali-tativ. Fiecare pas al mutatiei se poate realiza în mai multemoduri, iar fiecare dintre aceste moduri
1
are o anumita probabilitate ca sa fie utilizat. Cele mai eficiente probabilitati sunt determinate uti-
lizând un algoritm genetic de optimizare suplimentar. Algoritmul genetic în trei pasi obtine unmakespan mai bun si o echilibrare a încarcarii foarte buna. Contributia II a fost prezentata initialîn [Alexandrescu 2011a], iar algoritmul de optimizare în [Alexandrescu 2011b].
Contributia III:
O metoda eficienta de asignare a datelor primite de la senzori într-un mediu de mari dimensiuni
Tehnicile de mapare a task-urilor sunt adaptate si utilizate pentru a asigna eficient datele primite
de la senzori la gateway-uri în vederea procesarii acestora. Pentru a rezolva problema procesariieficiente a datelor de la senzori este propusa o metoda numita Weighted Minimum Completion
Time care este evaluata din perspectiva a cinci indicatori ai eficientei metodei.Contributia III afost prezentata initial în [Alexandrescu 2012c].
Contributia IV:
Un controller pentru optimizarea fluxului de date într-un sistem dinamic senzor-gateway
Într-un sistem dinamic senzor-gateway nu sunt cunoscuti în prealabil timpii în care gateway-urile
proceseaza datele primite de la senzori. Din aceasta cauza nu se pot aplica euristici de maparepentru rezolvarea problemei asignarii eficiente sensor-gateway într-un astfel de sistem. Pentru op-timizarea fluxului de date într-un sistem dinamic senzor-gateway este propus un controller care
utilizeaza doua metode de mapare: o retea neuronala care utilizeaza învatarea supervizata si nesu-pervizata, si un algoritm genetic cu o mutatie inteligenta. Contributia IV a fost prezentata initial în
[Alexandrescu 2012b].
Contributia V:
O platforma de simulare a maparii task-urilor pentru evaluarea si determinarea celor mai
eficiente euristici de mapare pentru o situatie data
Unele euristici de mapare obtin rezultate mai bune decât altele în functie de scenariul considerat.
Platforma de simulare a maparii task-urilor este propusa pentru a adresa aceasta chestiune si a punela dispozitia utilizatorului modalitati de a evalua si de a determina cele mai eficiente euristici demapare în functie de situatia data. Aceasta platforma a fost de asemenea utilizata pentru a testa trei
dintre metodele propuse în teza. Contributia V a fost prezentata initial în [Alexandrescu 2012a].
1.3 Organizarea tezei
• Capitolul 1 include o prezentare a structurii tezei, o privire de ansamblu a problematiciistudiate, doua directii de cercetare care stau la baza acestei lucrari si principalele contributii
aduse de aceasta teza în domeniul sistemelor distribuite eterogene.
• Capitolul 2 prezinta conceptele referite în aceasta teza, începând cu o analiza a sistemelor
distribuite eterogene si a problemelor care pot aparea, printre care: echilibrarea încarcarii,toleranta la defecte si scalabilitatea. Mai apoi sunt prezentate doua metode de inteligenta
artificiala: algoritmii genetici si retelele neuronale. Sectiunea de mapare a task-urilor descrie
2
notiunile utilizate în etapa de asignare, modul de functionare al euristicilor de mapare si
metodele folosite pentru evaluarea solutiilor obtinutede un algoritm de mapare. În ultimaparte a acestui capitol sunt incluse contributiile în ceeace priveste evaluarea metodelor demapare.
• Capitolul 3 se axeaza pe problema maparii task-urilor utilizând algoritmi genetici si include
primele doua contributii majore ale acestei teze. Sunt propuse doua noi metode de mapare atask-urilor in sistemele distribuite eterogene, folosindalgoritmi genetici optimizati pentru aoferi o solutie superioara: un algoritm genetic cu mutatie inteligenta si un algoritm genetic
cu mutatie în trei pasi (Sectiunea 3.3). De asemenea, este prezentat un algoritm genetic deoptimizare a probabilitatilor mutatiei în trei pasi.
• Capitolul 4 prezinta un studiu de caz care urmareste o metoda eficienta de procesare a datelorprimite de la senzori în medii de mari dimensiuni si includedoua noi contributii majore.
Prima contributie este o metoda eficienta de procesare a datelor primite de la senzori, numitaWeighted Minimum Completion Time (WMCT), care ia în considerare faptul ca task-urile au
prioritati si termene limita. Al doilea element de noutate îl reprezinta un controller inteligentcare supervizeaza mediul senzorial dinamic pentru a creste eficienta procesarii datelor si
fiabilitatea sistemului.
• Capitolul 5 include evaluarile contributiilor prezentate in Capitolele 3 si 4. Pentru evaluarea
metodelor propuse, se prezinta o platforma de simulare a maparii numita Task MappingSimulation Framework.
• Capitolul 6 prezinta o serie de studii existente, relevante pentru solutiile ¸si ideile incluse înaceasta lucrare. Prima pare face un rezumat al cercetarilor efectuate în domeniul maparii
task-urilor cu accent pe asignarea task-urilor simple si independente catre unitati de proce-sare. A doua parte include elemente de cercetare privind procesarea datelor primite de la
senzori si maparea task-urilor cu prioritati si termene limita.
• Capitolul 7 încheie teza si face un rezumat al rezultatelorobtinute prin prisma noutatii meto-
delor propuse pentru maparea task-urilor si pentru procesarea datelor primite de la senzori.Pentru a încheia, acest capitol prezinta viitoare directii de cercetare care se pot dezvolta
plecând de la elementele de noutate din teza
3
2 Concepte utilizate
2.1 Sistemele Distribuite Heterogene
Sistemele distribuite heterogene sunt constituite din unitati de procesare diferite inter-conectate deobicei printr-o retea de mare viteza. Acest tip de sistem deseori utilizeaza solutii persistente de
stocare care presupun existenta unui sistem distribuit defisiere ([Alexandrescu 2010b]). Datelestocate pot fi procesate folosind tehnici de data mining sau de clusterizare. În [Agavriloaei 2011a]
si [Agavriloaei 2011b] autorii propun si evalueaza metode de web clustering care utilizeaza seturifoarte mari de date stocate într-un mediu distribuit.
Cele mai importante probleme care pot aparea într-un sistem distribuit heterogen sunt: echi-
librarea încarcarii unitatilor de procesare, transparenta, problemele de comunicare si conexiune,detectia si toleranta la defecte, excluziunea mutuala, sincronizarea, coordonarea resurselor, secu-
ritatea, descoperirea resurselor si scalabilitatea. Metodele noi prezentate în aceasta teza au ca scoprezolvarea problemelor de echilibrare a încarcarii, toleranta la defecte si scalabilitate.
2.1.1 Echilibrarea Încarcarii
Echilibrarea încarcarii se realizeaza prin asignarea eficienta a task-urilor astfel încât toate unitatile
de procesare din sistem au aceeasi încarcare. Conceptele utilizate în ceea ce priveste asignareatask-urilor sunt prezentate în Sectiunea 2.3. Exista metode de asignare care proceseaza task-urile
pe rând, cum ar fi Opportunistic Load Balancing, Minimum Execution Time sau Minimum Com-pletion Time, si metode care considera toate task-urile care înca nu au fost procesate atunci cândun task este asignat, cum ar fi Min-Min, Max-Min sau Duplex. Cele mai cunoscute metode de
asignare a task-urilor sunt prezentate in Sectiunea??.
2.1.2 Toleranta la Defecte
Toleranta la defecte ([Avizienis 1985]) reprezinta capacitatea unui sistem distribuit de a-si punela dispozitie serviciile si resursele în ciuda aparitiei unor defecte în sistem. Un sistem distribuit
heterogen trebuie sa fie capabil sa execute task-uri complexe care au o durata mare de executie.În aceasta situatie, daca apare o eroare care ar afecta executia task-ului, respectivul task ar trebui
repornit sau ar trebui sa fie executat de o alta unitate de procesare, preluându-l din punctul în careera în momentul aparitiei defectului de sistem. Exista mai multe tipuri de defecte ([Sathya 2010])si diverse metode de a tolera aceste defecte ([Magoules 2009]).
2.1.3 Scalabilitatea
Scalabilitatea este definita în [Bondi 2000] ca fiind abilitatea sistemului de a procesa un numar
foarte mare de task-uri cu aproximativ aceeasi eficienta ca în cazul unui numar mai redus de task-uri. Unii algoritmi de asignare dau rezultate bune pentru putine task-uri, dar, pe masura ce numarul
task-urilor creste, timpul de asignare al acelor task-uricreste chiar si exponential.
4
2.2 Inteligenta Artificial a
2.2.1 Algoritmul Genetic
Algoritmii genetici sunt utilizati pentru a rezolva probleme cu un spatiu foarte mare de cautare a
solutiei si care necesita un volum ridicat de resurse computationale si de timp pentru a procesa toatesolutiile posibile. Algoritmul genetic îsi are origineaîn biologie si împrumuta o serie de termeni
din acest domeniu cum ar fi: cromozom, gena sau alela. Cromozomul este o solutie candidat carepoate fi reprezentata în diferite moduri, în functie de problema. Cromozomii sunt alcatuiti din
gene, care sunt entitati care codifica un anumit element din solutia candidata. În cele din urma, oalela reprezinta una dintre trasaturile posibile ale unei gene. De exemplu, un cromozom poate fireprezentat sau codificat ca un vector în care fiecare elementpoate avea o valoare cuprinsa între 0
si 10. O gena este elementul din vector care este situat la o anumita pozitie, cunoscuta sub numelede locus. Trasaturile pe care le poate avea o gena sunt numere între 0 si 10, o alela putând fi, de
exemplu, numarul 4.Pseudocodul algoritmului genetic este prezentat în Algoritmul 2.1, iar în continuare este dis-
cutata structura algoritmului genetic clasic.
1 Generarea populatiei initiale;2 Evaluarea populatiei;3 while conditia de stop nu este satisfacutado4 Selectia;5 Încrucisarea;6 Mutatia;7 Crearea noii populatii;8 Evaluarea Crearea noii populatii;9 end
10 Returnarea celei mai bune solutii;Algoritmul 2.1: Pseudocodul Algoritmului Genetic
Populatia initiala este de obicei generata aleator prin selectarea unei alele din trasaturile dis-
ponibile pentru fiecare gena. Uneori solutia obtinuta prin rularea unui alt algoritm pentru aceeasiproblema poate fi folosita pentru a initializa unul sau mai multi cromozomi din populatia initiala.
Fitness-ul cromozomului este o metoda de evaluare a calitatii solutiei: cu cât este mai mare va-loarea fitness-ului, cu atât este mai buna solutia. Algoritmul genetic se executa pâna când estesatisfacuta conditia de stop: pâna când un numar suficient de iteratii s-au executat de la startul
algoritmului sau daca solutia cea mai buna nu a mai fost îmbunatatita dupa un anumit numar deiteratii.
La fiecare iteratie sunt selectate mai multe perechi de cromozomi pentru reproducere: încruci-sare si mutatie. Procesul de selectie a cromozomilor care urmeaza sa se reproduca, se poate realiza
în mai multe moduri. Cele mai cunoscute modalitati de selectie sunt: selectia bazata pe fitness,selectia bazata pe rang sau selectia-turnir. Selectia bazata pe fitness este cea mai utilizata metodadeoarece, în aceasta situatie, probabilitatea ca un cromozom sa fie selectat este direct proportionala
cu fitness-ul lui.Operatorul de încrucisare este aplicat, cu o anumita probabilitate, unei perechi de cromozomi,
numiti si cromozomi „parinti”, pentru a produce doi cromozomi „copii”. Cea mai cunoscuta me-
5
toda de a realiza încrucisarea a doi cromozomi este încrucisarea cu un punct de taiere ales aleatoriu.
Aceasta metoda presupune producerea a doi cromozomi copii care vor avea jumatate din gene dela un parinte si cealalta jumatate de la celalalt parinte. Alte doua metode de încrucisare folositesunt încrucisarea multi-punct si încrucisarea uniforma. Celalalt operator utilizat în procesul de
reproducere este mutatia, care în majoritatea situatiilor implica înlocuirea valorii unei gene cu oalta alela. O alta modalitate de a realiza mutatia unui cromozom este de a selecta aleatoriu doua
gene si de a inter-schimba alelele lor.În urma reproducerii se formeaza o noua populatie care va contine si cromozomi din vechea
populatie. Pentru a se asigura ca cea mai buna solutie nu se pierde, cel mai bun cromozom dinvechea populatie este pastrat în populatia noua, proces numit elitism. Atunci când conditia de stopeste satisfacuta, cromozomul cu fitness-ul cel mai mare este ales ca fiind solutia algoritmului.
Spatiul de cautare este suficient de mare pentru ca un algoritm exhaustivsa aiba o durata deexecutie extraordinar de mare pentru a obtine cea mai buna solutie. Algoritmul genetic nu face
o cautare exhaustiva, prin urmare, este posibil ca solutia obtinuta sa nu fie cea mai buna solutieexistenta, dar totusi va fi o solutie foarte buna obtinuta într-un timp scurt.
2.2.2 Reteaua Neuronala Artificial a
Reteaua Neuronala Artificiala este o este o tehnica de machine learning bazata pe structura si
functionalitatea retelelor neuronale biologice ([Russell 2009]). Aceasta retea este alcatuita dinmai multe straturi interconectate de neuroni. De obicei, exista un strat de intrare care este conectatprintr-un strat intermediar de stratul de iesire. O astfelde retea se numeste retea neuronala feed-
forward, deoarece are structura unui graf orientat aciclic. Un neuron este alcatuit din mai multeintrari, o functie de intrare, o functie de activare si una saumai multe iesiri. Legaturile dintre neu-
roni au anumite ponderi care sunt determinate prin intermediul tehnicilor de învatare supervizata,nesupervizata sau prin întarire.
Aplicatiile retelelor neuronale sunt diverse si acopera domenii cum ar fi clasificarea si procesa-rea datelor, aproximarea functiilor sau gasirea de pattern-uri în seturi de date de mari dimensiuni.
2.3 Maparea task-urilor
2.3.1 Notiuni utilizate în maparea task-urilor
Una din cele mai importante probleme întâlnite în sistemeledistribuite heterogene este maparea
eficienta a task-urilor la unitati de procesare. Maparea task-urilor presupune asignarea task-urilorla unitati de procesare si ordonarea lor pentru executie la unitatile respective. Pentru a mapantask-uri (T1,...,n) lam unitati de procesare (M1,...,m), trebuie gasit un echilibru între calitatea solutiei
obtinute si timpul în care se obtine solutia respectiva. În practica, problema maparii task-urilor esterezolvata prin aplicarea euristicilor de mapare, respectiv prin metode bazate pe experienta folosite
în rezolvarea problemelor unde o cautare exhaustiva a solutiei optime nu este posibila.Euristicile de mapare folosesc estimari ale timpilor de executie a fiecarui task la fiecare unitate
de procesare. În aceasta teza, timpii de executie sunt exprimati în unitati de timp generice (timeunits - t.u), care pot fi milisecunde, secunde, minute sau orice alta unitate de timp. Timpii sunt
6
Tabelul 2.1: Matrice ETC inconsistenta cu hete-rogeneitate mare
M1 M2 M3
T1 2.3 5.9 1.9T2 5.4 7.9 5.1T3 3.1 2.8 2.1T4 4.4 2.3 4.3T5 3.5 1.5 1.1T6 7.5 7.6 7.4T7 6.4 5.9 6.7T8 3.9 3.8 2.6
Tabelul 2.2: Matrice ETC consistenta cu hetero-geneitate mare
M1 M2 M3
T1 1.9 5.9 2.3T2 5.1 7.9 5.4T3 2.1 3.1 2.8T4 2.3 4.4 4.3T5 1.1 3.5 1.5T6 7.4 7.6 7.5T7 5.9 6.7 6.4T8 2.6 3.9 3.8
M1 M2 M3
0
5
10
2.6
5.9
7.4
1.5
2.3
3.1
5.4
2.3
unitati de procesare
un
itati
de
timp
T1
T2
T3
T4
T5
T6
T7
T8
Figura 2.1: O posibila mapare pentru matricea ETC din Tabelul 2.1
retinuti într-o matriceExpected Time to Compute (ETC), unde fiecare rând al matricii reprezintaun task, iar fiecare coloana o unitate de procesare.
În ceea ce priveste heterogeneitatea sistemului, aceasta teza considera doua situatii: heteroge-neitate mare, atunci când timpii de executie ai unui task variaza semnificativ în functie de unitatea
de procesare la care a fost asignat task-ul, si heterogeneitate mica, atunci când variatiile sunt mi-nore. O matrice ETC poate ficonsistenta(Fig. 2.2),inconsistentaFig. 2.1) sausemi-consistenta
în functie de timpii de executie ai task-urilor.Un task poate avea asociat un termen limita care reprezinta timpul în care task-ul respectiv
trebuie sa-si termine executia. De asemenea un task poate avea o prioritate care poate fi mare,medie sau mica. În [Braun 2008] si [Kim 2007] este definit un factor al termenului limita (DFi).O adaptare a acestui factor este utilizata în aceasta teza:
DFi =
1.00, if TCTi ≤ Di,
0.50, if TCTi ≤ 2Di,
0.25, if TCTi ≤ 4Di,
0.05, otherwise.
. (2.1)
De asemenea, este definita si calitatea unui task ca fiind:
worthi = Pi ×DFi. (2.2)
7
2.3.2 Indicatorii eficientei unei solutii
Cinci indicatori ai eficientei sunt utilizati pentru a determina eficienta euristicilor de mapare:
1. Durata algoritmului - timpul în care se face asignarea task-urilor;
2. Makespan-ul - timpul în care toate unitatile de procesare termina de executat task-urile asig-
nate;
3. Dezechilibrul încarcarii - diferenta dintre unitatea de procesare cea mai incarcata si cea mai
putin încarcata;
4. Calitatea solutiei - suma prioritatilor task-urilor la care se adauga penalizari procentuale înfunctie de cât de mult task-urile au depasit termenul lor limita;
5. Rata de succes - procentajul task-urilor care îsi termina executia înainte de limita ponderatcu prioritatea task-urilor respective.
8
3 Maparea Task-urilor Utilizând Algoritmi Genetici în
Sistemele Distribuite Heterogene
Acest capitol se axeaza pe problema maparii task-urilor utilizând algoritmi genetici si include
primele doua contributii majore ale acestei teze. Sunt propuse doua noi metode de mapare a task-urilor in sistemele distribuite heterogene, folosind algoritmi genetici optimizati pentru a oferi osolutie superioara: - algoritmul genetic cu mutatie inteligenta (GASM) care urmareste îmbunatati-
rea makespan-ului si scurteaza timpul de executie al algoritmului ([Alexandrescu 2010a]), - urmatde algoritmul cu mutatie în trei pasi (GA3SM) care, pe lânga obtinerea unui bun makespan, se
axeaza pe echilibrarea încarcarii ([Alexandrescu 2011a]). Ambii algoritmi folosesc ca punct deplecare solutia data de o tehnica de mapare mai simpla si îmbunatatesc solutia respectiva aplicând
o mutatie inteligenta.
3.1 Consideratii Generale
Algoritmii genetici au fost folositi pentru a rezolva problema maparii task-urilor, însa marele lor
inconvenient comparativ cu alte euristici de mapare îl reprezinta durata de executie a algoritmuluicare este semnificativ mai mare. Totusi, solutia obtinuta de algoritmii genetici este mult mai buna
calitativ. Abordarile traditionale care utilizeaza algoritmi genetici, pornesc de la o solutie care afost obtinuta prin executia unei euristici de mapare mai ineficiente darmult mai rapida, cum ar fi:
Min-Min sau Max-Min. Structura cromozomului este prezentata în Fig. 3.1 si reprezinta solutiadin Fig. 2.1. Elementul de pe pozitiai din cadrul cromozomului reprezinta unitatea de procesare
la care task-ulTi este asignat.
3.2 Algoritmul Genetic cu Mutatie Inteligenta
(Genetic Algorithm with a Smart Mutation - GASM)
În [Alexandrescu 2010a] este propusa o abordare diferita a maparii task-urilor folosind algoritmi
genetici. Metoda propusa este un algoritm genetic cu mutatie inteligenta (Genetic Algorithm witha Smart Mutation - GASM) a carui structura este prezentata în sectiunea urmatoare.
3.2.1 Structura Algoritmului
Reprezentarea cromozomului
Reprezentarea cromozomului folosita de algoritmul GASM difera de abordarea clasica cum sepoate observa din Fig. 3.2, unde pozitiaj a cromozomului contine task-urile care sunt asignate launitatea de procesareMj . Structura cromozomului utilizata de algoritmul propus nu influenteaza
makespan-ul, dar în schimb micsoreaza durata de executie a algoritmului prin reducerea timpului
M1 M1 M1 M2 M2 M3 M2 M3
1 2 3 4 5 6 7 8
Figura 3.1: Reprezentarea cromozomului algoritmului genetic clasic pentru solutia din Fig. 2.1
9
T1, T2, T3 T4, T5, T7 T6, T8
1 2 3
Figura 3.2: Reprezentarea cromozomului algoritmului genetic cu mutatie inteligenta pentru solutia dinFig. 2.1
de realizare al mutatiei. Cel mai mare avantaj al structurii utilizate de GASM este însa considerareaordinii de executie a task-urilor la unitatile de procesare la care au fost asignate.
Populatia initial a
Populatia initiala a algoritmului propus este formata din cromozomi generati aleatoriu folosind odistribuitie uniforma, iar un cromozom reprezinta solutia obtinuta de euristica Min-Min.
Evaluarea
Pentru a evalua cromozomii este folosita o functie de fitness care este invers proportionala cumakespan-ul. O solutie candidata este considerata a fi cea mai buna daca makespan-ul solutiei
respective este cel mai mic.
Conditia de stop
Algoritmul de mapare se termina când una din doua conditii de stop au fost satisfacute. Primaconditie este executia a unui numar 1000 de iteratii ale algoritmului genetic, iar cea de-a douaconditie de stop este pastrarea neschimbata a celei mai bune solutii pentru un numar de 300 de
iteratii.
Selectia
Metoda de selectie utilizata este selectia bazata pe fitness deoarece aceasta metoda favorizeaza mai
mult selectarea cromozomilor cu un fitness superior pentru reproducere.
Încrucisarea
Euristica GASM nu utilizeaza operatorul de încrucisare, ceea ce duce la micsorarea timpului deexecutie al algoritmului.
Mutatia
Principalul mod de obtinere a unei solutii mai bune este operatorul de mutatie inteligenta care întaiselecteaza aleatoriu o unitate de procesare si un task de la unitatea respectiva, iar apoi muta task-ulselectat la unitatea care este cel mai putin ocupata. Figura 3.3 arata cum operatorul de mutatie
inteligenta poate sa obtina solutia prezentata în Fig. 2.1.
Noua populatie
Algoritmul utilizeza principiul elitismului si mentine 20% din cei mai buni cromozomi din vechepopulatie când creaza o populatie noua.
3.2.2 Concluzii
Caracteristicile care disting metoda propusa, GASM, de algoritmul genetic clasic sunt:
• o noua reprezentare a cromozomului care permite retinerea ordinii de executie a task-urilor,
• absenta operatorului de crossover care are ca efect scurtarea duratei algoritmului,
10
M1 M2 M3
0
5
10
15
5.9
2.6
6.7
7.41.5
2.3
3.1
5.4
2.3
unitati de procesare
un
itati
de
timp
T1
T2
T3
T4
T5
T6
T7
T8
Figura 3.3: Exemplu de cum poate operatorul de mutatie a GASM sa obtina solutia din Fig. 2.1
• utilizarea operatorului de mutatie inteligenta pentru obtinerea mai rapida a unei solutii supe-rioare,
• utilizarea unui procentaj în aplicarea elitismului pentrua avea asigurat un numar mai mare
de solutii candidate superioare pentru reproducerea urmatoare.
3.3 Algoritmul Genetic cu o Mutatie în 3 Pasi
(The Genetic Algorithm with a 3-Step Mutation - GA3SM)
Algoritmul genetic cu o mutatie în trei pasi considera gradul de dezechilibrare a încarcarii înevaluarea unei solutii candidate si, de asemenea, utilizeaza un operator de mutatie complex pentru
a îmbunatati semnificativ solutia initiala.
3.3.1 Structura Algoritmului
Reprezentarea cromozomului
Modalitatea de reprezentare a cromozomului utilizata este cea clasica din Fig. 3.1.
Populatia initial a
Populatia initiala este generata în acelasi mod ca la algoritmul GASM, prezentat anterior.
Evaluarea
Evaluarea se face în functie de makespan-ul si de dezechilibrul încarcarii obtinut de solutia candi-
data. Solutiile sunt evaluate folosind trei functii de fitness:
f1 =1
M, f2 =
1
∆ + 1, f3 =
1
M +∆+ 1(3.1)
Figura 3.4 prezinta trei posibile solutii pentru problema de mapare data de matricea ETC dinTabelul 2.1. Makespan-ul, dezechilibrul încarcarii (diferenta de timp∆) si valorile functiilor defitness pentru cele trei posibile mapari sunt prezentate în Tabelul 3.1.
Desi solutia S3 nu are nici cel mai bun makespan si nici ceamai echilibrata încarcare dintrecele trei, dupa aplicarea celei de-a treia functii de fitness, solutia S3este mai buna decât S2 datorita
faptului ca S2 a avut un makespan semnificativ mai mare comparativ cu S3.
11
M1 M2 M3
0
5
10
15
2.6
5.9
7.41.5
2.3
3.1
5.4
2.3
unitati de procesare
un
itati
de
timp
(a) S1
M1 M2 M3
0
5
10
15
2.6
6.7
7.5
3.5
4.33.1
7.9
5.9
unitati de procesare(b) S2
M1 M2 M3
0
5
10
15
3.8
5.9
7.5
1.1
4.4
2.1
5.1
1.9
unitati de procesare
T1
T2
T3
T4
T5
T6
T7
T8
(c) S3
Figura 3.4: Trei mapari posibile pentru matricea ETC din Tabelul 2.1
Tabelul 3.1: Makespan-ul, diferenta de timp∆ si valorile functiilor de fitness pentru cele trei posibile mapariFig. 3.4
makespan ∆ f1 f2 f3
S1 10.8 1.1 0.0926 0.4762 0.0775
S2 12.2 0.5 0.0709 0.6667 0.0641
S3 11.9 2.2 0.0840 0.3125 0.0662
Conditia de stop
Una din trei conditii trebuie îndeplinite pentru ca algoritmul de mapare sa îsî încheie executia:
• Limita maxima a numarului de iteratii ,
• Sa nu existe nici o îmbunatatire a celei mai bune solutii pentru un numar specificat de iteratii,
• Solutia initiala sa fie îmbunatatita suficient de mult.
Selectia
Metoda de selectie folosita este aceeasi ca la algoritmul GASM, respectiv selectia bazata pe fitness.
Încrucisarea
Operatorul de încrucisare folosit este încrucisarea cu un punct de taiere ales aleatoriu.
Mutatia
La fel ca în cazul algoritmului GASM, componenta critica a algoritmului GA3SM este mutatia întrei pasi. Operatorul de mutatie utilizat are ca scop mutarea unui task de la o unitate de procesare
la alta în vederea obtinerii unei solutii mai bune. Cei trei pasi ai mutatiei sunt dupa cum urmeaza:
1. Selectarea unei unitati de procesareMx
a) aleatoriu,
b) cea mai ocupata.
2. Selectarea unui taskTp de la unitatea de procesareMx
a) aleatoriu,
12
b) cu timpul cel mai lung de executie laMx,
c) cu timpul cel mai scurt de executie laMx,
d) cu cea mai marepenalizare timp.
3. Selectarea unitatii de procesare destinatieMy
a) aleatoriu,
b) cea mai putin ocupata,
c) care executa task-ul selectatTp în cel mai scurt timp.
În final, task-ulTp este mutat la unitatea de procesare destinatieMy. O combinatie a mutatieiestedefinita ca fiind alegerea unei metode pentru fiecare din cei trei pasi ai mutatiei. Primul pas al
mutatiei se poate realiza în doua moduri (1a si 1b), al doilea pas în patru moduri (2a, 2b, 2c si 2d),iar al treilea pas în una din trei metode (3a, 3b and3c). Mutatia în trei pasi utilizeaza penalizarea
timpΦp care este definita caΦp = max
q(Φq) (3.2)
undeq = 1, . . . , n, task-ulTq este asignat la unitatea de procesareMx si
Φq = ETCqx − minz=1,...,m
(ETCqz) (3.3)
. ValoareaΦq reprezinta penalizarea timp pentru fiecare task de la unitatea de procesareMx si esteegala cu diferenta dintre timpul de terminare al executiei task-ului de la unitateaMx si cel mai
scurt timp de executie al task-ului respectiv la celelalteunitati de procesare.
Noua populatie
La fel ca în cazul algoritmului GASM, methoda GA3SM utlizeaza elitismul pentru a mentine 20%
din cei mai buni cromozomi din vechea populatie când este creata o populatie noua.
3.3.2 Concluzii
Caracteristicile care disting metoda GA3SM de algoritmul genetic clasic sunt:
• utilizarea indicatorului de dezechilibrare a încarcarii în evaluarea unei solutii candidate,
• utilizarea operatorului de mutatie în trei pasi pentru obtinerea mai rapida a unei solutii supe-
rioare,
• utilizarea unui procentaj în aplicarea elitismului pentrua avea asigurat un numar mai mare
de solutii candidate superioare pentru reproducerea urmatoare.
3.4 Algoritmul de optimizare a emtodei GA3SM
(The Optimization Genetic Algorithm - OGA)
Scopul algoritmului de optimizare este acela de a îmbunatatii operatorul de mutatie a euristiciiGA3SM prin determinarea probabilitatilor optime de selectie a metodelor utilizate de cei trei pasiai mutatiei.
13
0.09 0.91 0.24 0.17 0.18 0.41 0.05 0.36 0.591a 1b 2a 2b 2c 2d 3a 3b 3cSection 1 Section 2 Section 3
Figura 3.5: Reprezentarea cromozomului pentru algoritmulgenetic de optimizare
parent 1
offspring 1-1
offspring 2-1
offspring 3-1
parent 2
offspring 1-2
offspring 2-2
offspring 3-2
Figura 3.6: Operatorul de încrucisare utilizat de algoritmul genetic de optimizare
3.4.1 Structura Algoritmului
Reprezentarea cromozomului
O gena a cromozomului reprezinta probabilitatea de selectie a unei metode a mutatiei, iaralelele
au valori cuprinse între 0.00 si 1.00. Figura 3.5 prezinta un exemplu de codare a cromozomuluialgoritmului OGA.
Populatia initial a
Populatia initiala este formata din 50 de cromozomi generati aleatoriu respectând rescrictia ca,pentru fiecare din cele trei sectiuni, suma probabilitatilor sa fie egala cu unu.
Evaluarea
Functia de fitness executa algoritmul GA3SM pentru un set predifinit de matrici ETC inconsistente.Pentru fiecare cromozom, fitnessul rezultat este egal cu media îmbunatatirilor makespan-ului pen-
tru pentru setul respectiv de matrici.
Conditia de stop
Din cauza duratei ridicate a fiecarei iteratii, algoritmul de optimizare se încheie dupa 100 de iteratii.
Selectia
Metoda de selectie utilizata este aceeasi ca în cazul euristicii GA3SM si anume, selectia bazata pefitness.
Încrucisarea
Sunt utilizate trei metode de încrucisare: doua încrucisari cu un singur punct de taiere si o încruci-sare cu doua puncte de taiere (Fig. 3.6).
Mutatia
În ceea ce priveste mutatia este utilizata o mutatie în care toate probabilitatile dintr-o sectiune suntgenerate aleatoriu
si o mutatie în care doua din genele unei sectiuni sunt modificate cu o valoare aleatorie .
14
4 Studiu de Caz: Procesarea Eficienta a Datelor Primite de la
Senzori într-un Mediu de Mari Dimensiuni
4.1 Contextul Problemei
Pentru a întelege mai bine un anumit mediu este necesara adunarea si procesarea informatiilorcu privire la mediu respectiv, iar aceste informatii sunt monitorizate de senzori. Acestia trimit
date care pot fi analizate sau pot controla direct elementeledin mediul respectiv. O categorieimportanta de senzori este cea a senzorilor stationari, care sunt conectati la o sursa de energie
stabila si continua. Retele de senzori stationari sunt utilizate în cladiri inteligente unde au rolul de amonitoriza functiile cladirii, securitatea si consumul de energie pentru a spori confortul rezidentilor
([Giladi 2004]). Cercetarea prezentata în aceasta teza este în domeniul senzorilor care trimit datespre procesare la gateway-uri ([gbo 2010]) si care, la rândul lor, trimit datele procesate la aplicatiisau le stocheaza în baze de date distribuite.
Sistemul senzor-gateway folosit în teza este un sistem în care un numar foarte mare de senzorieste conectat la o retea de gateway-uri. Structura sistemului este prezentata în Fig. 4.1.
Exista multe tipuri de senzori în functie de aplicabilitatea lor, de exemplu senzori acustici,termici, de proximitate, optici etc. Fiecare senzor trimite periodic date de diferite dimensiuni, iar
gateway-urile trebuie sa fie capabile sa proceseze informatiile corespunzator în cel mai scurt timpposibil. Se pot distinge patru caracteristici ale senzorilor: prioritatea, volumul datelor, rata detrimitere si termenul limita în care informatia trebuie procesata.
Un gateway poate fi un calculator cu capacitati computationale ridicate sau un cluster de calcu-latoare care, din punctul de vedere al problemei considerate, poate fi vazut ca o singura entitate de
procesare. Gateway-urile sunt considerate a fi interconectate prin intermediul unei retele de mareviteza.
Problema considerata poate fi modelata ca o problema de mapare în care task-uri independentecu prioritati si termene limita trebuie sa fie asignate pentru executie la gateway-uri. Pentru a obtine
o mapare eficienta trebuie ca euristicile de mapare sa ia în considerare caracteristicile sistemuluisenzor-gateway. Performanta unei euristici de mapare este evaluata din perspectiva celor cinciindicatori ai eficientei din Sectiunea 2.3.2.
Gateway
Network
S
S
S
S
GW
S S
SGW
S S
SS
GWS
SS
GW
S SS
S
SGW
Figura 4.1: The sensor-gateway system
15
4.2 Euristica Weighted Minimum Completion Time (WMCT)
Scopul metodei propuse, Weighted Minimum Completion Time (WMCT), este de a obtine o so-
lutie superioara din prisma timpului de executie al algoritmului, a makespan-ului, a echilibrariiîncarcarii, a calitatii solutiei si a ratei de succes. Algoritmul WMCT utilizeaza euristica de mapareMinimum Completion Time (MCT) si beneficiaza de un avantaj major pe care aceasta metoda îl
are asupra celorlalte metode: o durata mica de executie.
4.2.1 Structura Algoritmului
Algoritmul este format din trei faze: sortarea task-urilordupa ponderea lor, asignarea task-urilorîn functie de termenul lor limita si reasignarea task-urilor care îsi termina executia dupa de patru
ori termenul lor limita. Pseudocodul pentru algoritmul propus este prezentat în Pseudocodul 4.1.Task-urile sunt sortate initial dupa ponderea lor pentru aasigura asignarea task-urilor cu prio-
ritate mai mare si cu un termen limita mai strâns. Algoritmul MCT este rulat de maxim patru ori,în functie de cât de mult task-urile îsi depasesc termenul limita. Scopul procesului de reasignare a
task-urilor din ultima faza este acela de a minimiza makespan-ul si de a echilibra încarcarea prinmutarea unor task-uri la gateway-urile mai putin încarcate.
4.2.2 Concluzii
Scopul urmarit de euristica WMCT este obtinerea unor valori superioare pentru cei cinci indicatoriai eficientei, Caracteristicile principale ale metodei propuse sunt urmatoarele:
• Utilizarea algoritmului MCT care asigura o durata scurta de executie a algoritmului,
• Utilizarea fazei de reasignare care duce la un makespan minim si o echlibrare bine încarcata,
• Sortarea task-urilor în functie de ponderea lor pentru a obtine o solutie de calitate superioarasi o rata mare de succes.
4.3 Controller-ul Inteligent pentru Optimizarea Fluxului de
Date (Intelligent Data Flow Controller - IDFC)
4.3.1 Consideratii Generale
Contextul procesarii datelor de la senzori este unul dinamic. Înainte de procesarea datelor primitede la senzori nu se cunoaste timpul de procesare sau termenul limit a de procesare a informatii-
lor respective. Singurele detalii cunoscute de gateway-uri sunt dimensiunea datelor si sursa lor(senzorul care le-a trimis). Daca termenul limita de procesare a unor date a fost depasit, datele
respective trebuie în continuare procesate, dar au o importanta mai mica. Fiecare senzor poate ficonfigurat sa trimita date la un singur gateway, dar el poate fi oricând reconfigurat în momentul
rularii sa trimita date la un alt gateway. Scopul este ca fluxul de date de la senzori la gateway-urisa fie facut cât mai eficient. Modelul utilizat este prezentat în Figura 4.2.
În momentul în care un gateway termina de procesat un set de date de la un anumit senzor,gateway-ul respectiv trimite la controller informatii despre procesarea facuta: sursa datelor, volu-mul de date procesate, timpul de procesare, prioritatea sitermenul limita pentru task-ul respectiv.
16
input : etc matrix (ETCij), priorities array (Pi) and deadlines arrays (Di)output: task-to-gateway mappingother : task completion time (TCTij) and gateway availability time (MATp, MATq)
1 sort all the tasks (Ti) in descending order based on their weight (weighti);2 T ← the sorted task list;// map the tasks depending on how much they exceed their deadline
3 c← 1;4 while c ≤ 4 andT 6= ∅ do5 for Ti ∈ T do6 Gj ← the minimum completion time gateway forTi;7 if TCTij < c ·Di then8 assignTi toGj ;9 T ← T − {Ti};
10 end11 end12 c← c · 2;13 end
// map the tasks that will finish after four times their deadline
14 if T 6= ∅ then15 for Ti ∈ T do16 Gj ← the minimum completion time gateway forTi;17 assignTi to Gj;18 end
// reassign the tasks to obtain a lower makespan and load imbalance
19 repeat20 Gx ← the gateway that finishes its assigned tasks the latest;21 Gy ← the gateway that finishes its assigned tasks the earliest;22 dif ← 0;23 q ← 0;24 foreachTp assigned toGx andTp ∈ T do25 difp ←MATx − (MATy + ETCpy);26 if difp > dif then27 dif ← difp;28 q ← p;29 end30 end31 if dif > 0 then32 moveTq fromGx to Gy;33 T ← T − {Tq};34 end35 until dif = 0;36 end
Algoritmul 4.1: Pseudocodul algoritmului Weighted Minimum Completion Time
17
Sensors Gateways
Controller
send data to their
assigned gateways
send
feedback
reassigns
sensors
Figura 4.2: Modelul senzor-gateway-controller
Feedback
Processor
Dynamic ETC
Matrix
updates
Task Historyupdatesgateway
feedback
Mapping
Heuristicuses
uses
Decisionapplies
mapping
Decision
Activator
Activates at specific
times
Runs the heuristic
and, if it is the case,
applies the mapping
Figura 4.3: The architecture of the intelligent controller
Rolul controller-ului este de a utiliza informatiile de lagateway-uri pentru a decide reconfigurareaunui sau a mai multor senzori în vederea eficientizarii sistemului.
În practica este foarte dificila estimarea timpilor de executie ai unui task la un gateway fara o
cunoastere prealabila a sistemului. Principalul avantaj al modelului propus este ca acesta realizeazareconfigurarea bazându-se pe starea curenta a sistemului fara a avea cunostinte precise despre cum
aceasta reconfigurare va influenta starea urmatoare.
4.3.2 Arhitectura Controller-ului
Principalele componente ale controller-ului sunt prezentate în figura Fig. 4.3. Controller-ul aredoua roluri: de procesare a informatiilor primite de la gateway-uri si de reconfigurare a senzorilor
la anumite intervale de timp.Componentele controller-ului sunt urmatoarele:
• Feedback Processor- proceseaza datele de la gateway-uri si face estimari asupra timpilor deprocesare a unei informatii de la un anumit senzor;
• Task History- retine informatiile despre task-urile care au fost procesate;
• Dynamic Expected Time to Compute Matrix(DETC Matrix) - matrice dinamica în care seretin timpii medii de procesare a datelor de la senzori la gateway-uri;
• Decision Activator- determina momentele când se face evaluarea sistemului în urma careiase decide daca este necesara o reasignare a senzorilor;
• Decision- realizeaza evaluarea asocierilor senzor-gateway curente în functie de task-urilecare au fost procesate si de matricea DETC;
• Mapping Heuristic- algoritmul de mapare a senzorilor la gateway-uri.
18
S1
G11
wsg11
G12
wgo11
wgo12
wsg12
S2
G21
wsg21
G22
wsg22
S3
G31
wsg31
G32
wsg32
O1
O2
wgo22
wgo21
wgo31
wgo32
Da
ta s
ize
s
Hidden
layer
Output
layer
Input
layer
Figura 4.4: The mapping Neural Network structure for three sensors and two gateways
Pentru algoritmul de mapare sunt propuse doua metode: o retea neuronala si un algoritm genetic.
cele doua metode sunt prezentate în urmatoarele doua sectiuni.
4.3.3 Neural Network Mapping Heuristic
Rolul euristicii de mapare care utilizeaza o retea neuronala, Neural Network Mapping Heuristic
(NNMH), este acela de a obtine o rata de succes mare prin asigurarea unui timp scurt de executiea task-urilor si a unei echilibrari bine încarcate. Reteaua neuronala propusa are doua nivele si
utilizeaza tehnici de învatare supervizata si nesupervizata. Structura retelei pentru trei senzori sidoua gateway-uri este prezentata în Fig. 4.4. Neuronii din nivelul “ascuns” (hidden layer) cores-
punzatori unui senzor sunt inter-conectati, iar, prin intermediul învatarii competitive, se activeazadoar una din iesirile neuronilor respectivi. Iesirea activata corespunde cu gateway-ul la care va
fi asignat senzorul respectiv. Reteaua neuronala este antrenata prin intermediul unei tehnici debackpropagation simplificate care modifica ponderile legaturilor dintre neuroni.
4.3.4 Genetic Algorithm Mapping Heuristic
O alta euristica de mapare utilizata de controller esteGenetic Algorithm Mapping Heuristic (GAMH)
al carei principal scop este îmbunatatirea ratei de succes.
19
Reprezentarea cromozomului si populatia initiala
Reprezentarea cromozomului este similara cu cea din Fig. 3.1, cu mentiunea ca o pozitie din
verctor reprezinta un senzor si nu un task. Populatia este formata din 100 de cromozomi generatialeatoriu cu o distributie uniforma.
Evaluarea
Functia de fitness folosita pentru a evalua cromozomii este procentajul de task-uri care îsi terminaexecutia înainte de termenul lor limita.
Conditia de stop, noua populatie, selectia si încruci¸sarea
Algoritmul genetic ruleaza pentru 500 de iteratii sau pâna când blocul de decizie porneste urma-toarea mapare. Elitismul este utilizat pentru a mentine cei mai buni 20% de cromozomi. Selectia
bazata pe fitness este folosita pentru alegerea cromozomilor care se vor reproduce, iar operatorulde încrucisare este încrucisarea cu un singur punct de taiere.
Mutatia
Sunt implementate doua tipuri de mutatie: aleatorie si orientata pe îmbunatatirea solutiei candidate.Cel de-al doilea tip de mutatie este realizata în doi pasi dupa cum este aratat în Pseudocodul 4.2.
input : chromosome (Ch)output: mutated chromosome (NewCh)other : # sensors (n), # gateways (m), task list (T ), sensor (task source) index (s),
gateway (g)
/* step 1 - determine the number of tasks that finish after their
deadline for each sensor (afterS) and each gateway (afterG) */
1 afterS ← float[n];2 afterG← float[m];3 foreachTp ∈ T do4 s← Tp source;5 if Tp finished after its deadlinethen6 afterS[s]← afterS[s] + 1;7 afterG[Ch[s]]← afterG[Ch[s]] + 1;8 end9 end/* step 2 - reassign sensors to other gateways */
10 NewCh← copy ofCh;11 len← randomly generated integer between 1 andn · 0.01;12 foreachx← 1 to len do13 s← index of the maximum value fromafterS;14 g ← index of the maximum value fromafterG;15 afterG[newCh[s]]← afterG[newCh[s]]− afterS[s];16 afterS[s]← afterS[s] · 0.10;17 newCh[s]← g;18 end
Algoritmul 4.2: Operatorul de mutatie orientat pe îmbunatatirea solutiei candidate al GAMH
20
4.3.5 Capacitatea sistemului de a se adapta la schimbari, toleranta ladefecte si verificari de performant a
Sistemul dinamic considerat poate fi afectat de defectari ale senzorilor sau ale gateway-urilor.De asemenea, noi senzori si noi gateway-uri pot fi adaugate în sistem. Controller-ul ia actiunile
necesare, indiferent de situatie, pentru a mentine ridicata eficienta sistemului. Periodic, controller-ul efectueaza verificari de performanta pentru a determina daca este necesara adaugarea de noigateway-uri în sistem sau daca este posibila înlaturarea unor gateway-uri. În acest sens, controller-
ul executa simulari pentru a determina în ce mod aceste schimbari afecteaza rata de succes.
21
5 Evaluarea Metodelor Propuse
5.1 Platforma de Simulare a Maparii Task-urilor
(Task Mapping Simulation Framework - TMSF)
Platforma de simulare a maparii task-urilor permite utilizatorilor testarea si compararea euristici-lor de mapare în diverse scenarii definite prin intermediul parametrilor de configurare. Platforma
a fost dezvoltata folosind limbajul Java si are implementati peste 20 de algoritmi de mapare. Con-figurarea se face prin intermediul unor fisiere XSD si XML, iar datorita structurii modulare se pot
adauga cu usurinta noi implementari ale modulelor platformei: configurare, intrare, evaluare, al-goritmi sau generare a rezultatelor. Aceasta platforma a fost utilizata pentru realizarea simularilor
a caror rezultate sunt prezentate în acest capitol.
5.2 Evaluarea Algoritmului Genetic de Optimizare
Algoritmul genetic de optimizare prezentat în Sectiunea 3.4 a fost utilizat pentru a determina pro-
babilitatile optime pentru combinatiile mutatiei euristicii GA3SM din Sectiunea 3.3. Probabilita-tile determinate sunt prezentate în Fig. 5.1. Pentru primul pas al mutatiei, metoda1b are cea mai
mare probabilitate sa fie utilizata (90%), pentru cel de-al doilea pas, metoda2d este aplicata decele mai multe ori (65%), iar pentru ultimul pas, metoda3ceste folosita cel mai des (54%).
5.3 Evaluarea euristicilor GASM si GA3SM
5.3.1 Parametrii Simularii
Algoritmii GASM si GA3SM au fost comparati cu 11 euristicide mapare si anume: Opportu-nistic Load Balancing, Minimum Completion Time, Minimum Execution Time, K-Percent Best,
Switching Algorithm, Min-Min, Max-Min, Duplex, SimulatedAnnealing, Genetic Algorithm siGenetic Simulated Annealing.
Problema de mapare considerata este asignarea a 1000 de task-uri la 10 unitati de procesare.Simulatorul a rulat pentru câte 100 de matrici ETC consistente si inconsistente având trei nivele
de heterogeneitate: mica, medie si mare. Cele 13 euristici au fost comparate din perspectivamakespan-ului si a echilibrarii încarcarii.
0.10 0.90 0.18 0.08 0.09 0.65 0.25 0.21 0.541a 1b 2a 2b 2c 2d 3a 3b 3cSection 1 Section 2 Section 3
Figura 5.1: Probabilitatile obtinute de algoritmul de optimizare
22
0 50 100 150 200 250 300 350 400 450 500
5,320
5,340
5,360
5,380
genetic algorithm iterations
mak
esp
an(t
.u)
GA GSA GASM GA3SM
Figura 5.2: Comparatia makespan-ului pentru 500 de itera¸tii în cazul maparii a 1000 de task-uri la 10 unitatide procesare pentru 100 de matrici ETC inconsistente cu heterogeneitate medie
5.3.2 Rezultate
Evolutia metodelor GA, GSA, GASM si GA3SM
Evolutia makespan-ului obtinut de cei patru algoritmi genetici (GA, GSA, GASM si GA3SM)
matrici ETC inconsistente cu heterogeneitate medie sunt prezentate în Fig 5.2. GA3SM a obtinutcel mai bun makespan, urmat îndeaproape de GASM, iar apoi GSAsi GA. Testele au aratat ca
atât pentru matrici consistente cât si pentru cele inconsistente, GASM a avut convergenta cea mairapida spre o solutie superioara.
Comparatia makespan-ului si a echilibrarii încarcarii pentru 13 euristici de mapare
Cele doua euristici propuse, GASM si GA3SM, au obtinut cel mai bun makespan si au fost întreprimele trei în ceea ce priveste echilibrarea încarcarii indiferent de tipul matricilor ETC: consis-
tente sau inconsistente, cu heterogenitate mica, medie saumare. Chiar daca euristica Max-Min aobtinut un echilibru foarte bun al încarcarii, în ceea ce priveste makespan-ul aceasta metoda a datreultate dintre cele mai slabe.
5.4 Evaluarea euristicii WMCT
5.4.1 Parametrii Simularii
Eficienta algoritmilor de mapare este determinata pentru 1000 de seturi de date de intrare. Aceste
seturi sunt generate folosind o serie de parametrii care descriu comportamentul senzorilor. Pentrusimulare a fost aleasa problema maparii a unui numar de task-uri variind între 100 si 1000 care
sunt asignate la 10 gateway-uri. Task-urile asingate au prioritati si termene limita.
5.4.2 Rezultate
Trebuie obtinuta o mapare eficienta în cel mai scurt timp posibil, iar solutia rezultata trebuie saaiba un makespan si un dezechilibru al încarcarii minim, o calitate superioara a solutiei si o rata
mare de succes.
23
200 400 600 800 1,000
0
50
100
150
numarul de task-uri
du
rata
alg
orit
mu
lui(
s)
Two− PhaseF itness
ReschedulingMin−Min
RelativeCost
SlackSufferage
Max−Max
WMCT
Figura 5.3: Evolutiaduratei algoritmuluiîn functie de numarul de task-uri care sunt mapate la 10 unitati deprocesare
Comparatia duratei algoritmului
Algoritmul propus, WMCT, are durata cea mai mica de executie lucru care este foarte importantîntr-un sistem în care datele primite trebuie procesate în timp real. Figura 5.3 arata faptul caWMCT se scaleaza mult mai bine decât celelalte metode; pe masura ce numarul de task-uri de
mapat creste, diferentele devin din ce în ce mai semnificative.
Comparatia makespan-ului
Cel mai bun makespan a fost obtinut de euristica Relative Cost, iar metoda propusa a obtinut ovaloare a makespan-ului cu 9% mai mare decât Relatice Cost. Acest lucru s-a datorat utilizariiunei metode mai putin eficiente în ceea ce priveste makespan-ul (MCT) în euristica WMCT.
Comparatia dezechilibrarii încarcarii
Încarcarea cea mai bine echilibrata a fost obtinuta de euristica Relative Cost, dar WMCT obtinerezultate din ce în ce mai bune pe masura ce numarul de task-uri de mapat creste; dupa cum se
poate vedea în Fig. 5.4.
Comparatia calitatii solutiei
WMCT a obtinut cele mai mari valori în ceea ce priveste calitatea solutiei indiferent de numarulde task-uri care trebuiau de asignat. Pe masura ce numarul de task-uri crestea, diferentele dintrealgoritmi deveneau tot mai semnificative.
Comparatia ratei de succes
Figure 5.5 arata faptul ca, indiferent de numarul task-urilor, ordinea euristicilor din perspectivaratei de succes a fost: WMCT, Max-Max, Slack Sufferage, Two-Phase Fitness, Rescheduling Min-
Min si, în final, Relative Cost. Pentru mai putin de 300 de task-uri, metoda WMCT a fost singuracare a obtinut rata de succes maxima de 100%.
24
200 400 600 800 1,000
0
1
2
3
numarul de task-uri
ech
ilib
rare
aîn
carca
rii(t
.u)
Two− PhaseF itness
ReschedulingMin−Min
RelativeCost
SlackSufferage
Max−Max
WMCT
Figura 5.4: Evolutiadezechilibrarii încarcarii în functie de numarul de task-uri care sunt mapate la 10unitati de procesare
200 400 600 800 1,0000.4
0.6
0.8
1
numarul de task-uri
rata
de
succ
es(%
)
Two− PhaseF itness
ReschedulingMin −Min
RelativeCost
SlackSufferage
Max −Max
WMCT
Figura 5.5: Evolutiaratei de succesîn functie de numarul de task-uri care sunt mapate la 10 unitati deprocesare
5.5 Evaluarea IDFC
5.5.1 Parametrii Simularii
Controllerul propus este testat într-un sistem dinamic care simuleaza comportamentul a 10000 desenzori care trimit date spre procesare la 10 gateway-uri într-un interval de timp de 24 de ore.
Eficienta celor doua metode de mapare ale controller-ului (NNMH si GAMH) este determinataîn comparatie cu o euristica care reasigneaza senzorii aleatoriu cu o distribuitie uniforma, nu-
mita Uniform Distribution Mapping Heuristic (UDMH). Echilibrarea încarcarii în cazul folosiriiUDMH este asigurata datorita numarului foarte mare de senzori din sistem care sunt asignatiuni-
form la gateway-uri. Criteriile pentru evaluarea metodelor propuse sunt timpul mediu de executiea unui task, rata de succes, echilibrarea încarcarii si durata maparii.
25
5 10 15 20 25 30 35 40 45 50 55 60 65
0.7
0.8
0.9
puncte de evaluare
rata
de
succ
es(%
)
UDMH GAMH NNMH
Figura 5.6: Evolutia ratei medii de succe pe parcursul celor 68 de puncte de evaluare pentru cele trei metodede mapare folosite de controller
5.5.2 Rezultate
Testele au aratat ca timpul mediu de executie pentru un task a fost de 70.44 ms pentru UDMH,
64.77 ms pentru NNMH si 70.01 ms pentru GAMH, metoda NNMH fiind cu 8% mai buna decâtGAMH.
În ceea ce priveste echilibrarea încarcarii la sfârsitul perioadei de evaluare, cele doua metodepropuse, NNMH si GAMH, au avut o încarcare cu 50% mai bine încarcata decât UDMH.
Evolutia ratei de succes pentru cele trei metode de mapare este prezentata în Fig. 5.6. Ratade succes initiala este mare, 93.08%, deoarece nu toti senzorii au început sa trimita date. Cea
mai mare rata de succes medie a fost obtinuta de metoda NNMH, 95.28%, urmata îndeaproape demetoda GAMH cu 94.55%, iar metoda UDMH a obtinut o rata de succes de doar 67.77%.
26
6 Stadiul Actual
6.1 Stadiul Actual în Domeniul Maparii Task-urilor
Cele mai cunoscute euristici de mapare ( Opportunistic LoadBalancing, Minimum ExecutionTime, Minimum Completion Time, K-Percent Best, Min-Min, Max-Min, Simulated Annealing)
sunt discutate si comparate în lucrari cum ar fi [Braun 2001], [Maheswaran 1999] sau [Ilavarasan2007].De asemenea, exista si alte tehnici de a rezolva problema maparii task-urilor: algoritmi de
optimizare Bayesian-a, metode greedy sau metode bazate pe tehnici de clusterizare. Unele metodeconsidera ca task-urile sunt independente, iar altele ia în considerare dependentele dintre task-uriân procesul de mapare.
6.2 Stadiul Actual în Domeniul Procesarii Datelor Primite de
la Senzori si în Domeniul Maparii Task-urilor cu
Priorit ati si Termene Limit a
Cercetarea realizata în domeniul retelelor de senzori se ocupa în principal cu eficientizarea consu-
mului de energie. Exista totusi o serie de lucrari care prezinta retele de senzori conectati la o sursacontinua de energie care sunt utilizate în cladiri inteligente ([Giladi 2004]) sau în structuri de tip
grid inteligente.În ceea ce priveste maparea task-urilor cu prioritati si termene limita, cele mai cunoscute me-
tode au fost testate în capitolul de evaluare. Patru dintre euristici, Rescheduling Min-Min, RelativeCost, Slack Sufferage si Max-Max, sunt prezentate în [Kim 2007], iar metoda Two-Phase Fitnesseste descrisa în [Braun 2008]. În teza aceste cinci metode au fost adaptate pentru a fi potrivite
pentru contextul considerat al problemei.
27
7 Concluzii
Problema maparii task-urilor este una dificila din cauza spatiului mare al solutiilor. Algoritmii
genetici rezolva eficient aceasta problema cu conditia ca durata de executie a algoritmului sa nufie un factor decisiv. In multe situatii este suficient sa se obtina un makespan suficient de mic, dar,în alte cazuri, încarcarea trebuie sa fie cât mai bine echilibrata.
Algoritmul genetic cu o mutatie inteligenta este propus pentru a accelera convergenta solutieisi, implicit, a scurta timpul de executie al algoritmului. Cel de-al doilea algoritm genetic include
o mutatie in 3 pasi care introduce mai multe optiuni pentru efectuarea fiecarui pas al mutatiei. Înacest al doilea caz, un alt algoritm genetic de optimizare este folosit pentru a afla probabilitatile
optime de selectie a fiecarei metode din mutatia în 3 pasi. Aceste noi tehnici de mapare a task-urilor au fost comparate cu 11 euristici (de mapare) existente. Testele au aratat ca algoritmii
propusi obtin încarcari ale unitatilor de procesare bine echilibrate. În plus, algoritmulcu mutatieinteligenta converge cel mai rapid catre o solutie foarte buna, urmat îndeaproape de algoritmul cumutatie în 3 pasi care compenseaza prin obtinerea celui mai bun makespan.
Pentru a studia modul în care algoritmii de inteligenta artificiala pot fi aplicati in sistemele dis-tribuite eterogene, teza cuprinde un studiu de caz care urmareste o metoda eficienta de procesare
a datelor primite de la senzori in medii de mari dimensiuni. Metoda propusa pentru procesareaeficienta a datelor primite de la senzori ia în considerare faptul ca task-urile au prioritati si ter-
mene limita. Aceasta noua metoda este comparata cu alte cinci adaptari ale metodelor de mapareexistente utilizând cinci indicatori de eficienta: durata algoritmului, makespan-ul, dezechilibrulîncarcarii, calitatea solutiei si rata de succes. Testele au aratat ca metoda propusa obtine rezultate
mai bune privind rata de succes, calitatea solutiei si, înspecial, durata algoritmului. De asemeneaobtine o buna echilibrare a încarcarii în special pentru un numar mare de task-uri.
Un alt nou concept prezentat în aceasta teza este controller-ul inteligent al fluxului de datefolosit pentru a obtine un randament cat mai mare al sistemului si pentru a gestiona modificarile
care pot aparea într-un sistem dinamic de tip senzor-gateway. Controller-ul dispune de doua optiuniîn alegerea metodei pentru obtinerea unei mapari senzor-gateway stabile: un algoritm genetic
cu o mutatie orientata spre îmbunatatirea solutiei si o retea neuronala care foloseste învatareasupervizata (backpropagation) si cea nesupervizata (învatare competitiva). Testele au aratat ca unastfel de controller creste semnificativ rata de succes sieficienta întregului sistem.
Metoda de mapare cea mai eficienta pentru un anumit mediu poate fi determinata cu ajutorulplatformei de simulare a maparii task-urilor. Platforma este usor de folosit, extrem de flexibila,
are o structura modulara si un mod de functionalitate care nu necesita cunostinte de programaredin partea utilizatorului. Aceasta platforma este de asemenea folosita pentru a testa tehnicile de
mapare propuse si pentru a determina în ce situatii acestea depasesc în performante euristicile demapare existente.
28
Bibliografie
[Agavriloaei 2011a] Ioan Agavriloaei,Adrian Alexandrescu and Mitica Craus.Improving web
clustering through a new modeling for web documents. In 15th International Conferenceon System Theory, Control, and Computing (ICSTCC), 2011, pages 1–6, October 2011.→ pages4
[Agavriloaei 2011b] Ioan Agavriloaei, Mitica Craus andAdrian Alexandrescu. Performance
Evaluation of a Two-Step Clustering Method. Buletinul Institutului Politehnic din Iasi,
vol. Tome LVII (LXI), no. Fasc. 2, pages 31–43, 2011.→ pages4
[Alexandrescu 2010a]Adrian Alexandrescu and Mitica Craus.Improving Mapping Heuristics
in Heterogeneous Computing. In Proceedings ECIT2010 - 6th European Conference on
Intelligent Systems and Technologies, October 7-9, Iasi, pages 1–12, October 2010.→pages1, 9
[Alexandrescu 2010b]Adrian Alexandrescu and Mihai Horia Zaharia. A Java Based Light
Distributed File System. Buletinul Institutului Politehnic din Iasi, vol. Tome LVI(LX),no. Fasc. 2, pages 63–74, 2010.→ pages4
[Alexandrescu 2011a]Adrian Alexandrescu, Ioan Agavriloaei and Mitica Craus.A Genetic Al-
gorithm for Mapping Tasks in Heterogeneous Computing Systems. In 15th InternationalConference on System Theory, Control, and Computing (ICSTCC), 2011, pages 1–6, Oc-
tober 2011.→ pages2, 9
[Alexandrescu 2011b]Adrian Alexandrescu, Mitica Craus and Ioan Agavriloaei.Determining
the Best Mutation Probabilities of a Genetic Algorithm for Mapping Tasks. Buletinul
Institutului Politehnic din Iasi, vol. Tome LVII (LXI), no.Fasc. 2, pages 21–30, 2011.→pages2
[Alexandrescu 2012a]Adrian Alexandrescu, Ioan Agavriloaei and Mitica Craus. A Task Ma-
pping Simulation Framework for Comparing the Performance of Mapping Heuristics in
Various Scenarios. In 16th International Conference on System Theory, Control, and Com-
puting (ICSTCC), 2012, pages 1–6, October 2012. To appear.→ pages2
[Alexandrescu 2012b]Adrian Alexandrescu, Fei Li, Schahram Dustdar and Mitica Craus. Dy-namically processing sensor data in a sensor-gateway system. To be submitted, 2012.→
pages2
[Alexandrescu 2012c]Adrian Alexandrescu, Fei Li, Schahram Dustdar and Mitica Craus.Effi-
cient Scheduling for Data Processing in Large-Scale Sensory Environments. Journal ofApplied Sciences, vol. 12, no. 19, pages 2006–2015, 2012.→ pages2
[Avizienis 1985] A. Avizienis.The N-Version Approach to Fault-Tolerant Software. IEEE Trans.
Softw. Eng., vol. 11, pages 1491–1501, December 1985.→ pages4
[Bondi 2000] André B. Bondi.Characteristics of scalability and their impact on performance. InProceedings of the 2nd international workshop on Software and performance, WOSP ’00,
pages 195–203, New York, NY, USA, 2000. ACM.→ pages4
29
[Braun 2001] Tracy D. Braun, Howard Jay Siegel, Noah Beck, Lasislau L. Bölöni, Muthucumara
Maheswaran, Albert I. Reuther, James P. Robertson, Mitchell D. Theys, Bin Yao, DebraHensgen and Richard F. Freund.A comparison of eleven static heuristics for mapping a
class of independent tasks onto heterogeneous distributedcomputing systems. J. Parallel
Distrib. Comput., vol. 61, pages 810–837, June 2001.→ pages1, 27
[Braun 2008] Tracy D. Braun, Howard Jay Siegel, Anthony A. Maciejewski and Ye Hong.Static
resource allocation for heterogeneous computing environments with tasks having depen-
dencies, priorities, deadlines, and multiple versions. J. Parallel Distrib. Comput., vol. 68,
pages 1504–1516, November 2008.→ pages1, 7, 27
[gbo 2010] Pacific Controls - bot gateway, 2010.→ pages15
[Giladi 2004] Ran Giladi.Heterogeneous Building Automation and IP Networks Management. In
Proceedings of the 24th International Conference on Distributed Computing Systems Wor-kshops - W7: EC (ICDCSW’04) - Volume 7, ICDCSW ’04, pages 636–641, Washington,
DC, USA, 2004. IEEE Computer Society.→ pages15, 27
[Ilavarasan 2007] E. Ilavarasan and P. Thambidurai.Low Complexity Performance Effective Task
Scheduling Algorithm for Heterogeneous Computing Environments. Journal of ComputerSciences, no. 3, pages 94–103, 2007.→ pages27
[Kim 2007] Jong-Kook Kim, Sameer Shivle, Howard Jay Siegel,Anthony A. Maciejewski,Tracy D. Braun, Myron Schneider, Sonja Tideman, Ramakrishna Chitta, Raheleh B. Dil-
maghani, Rohit Joshi, Aditya Kaul, Ashish Sharma, Siddhartha Sripada, Praveen Vangariand Siva Sankar Yellampalli.Dynamically mapping tasks with priorities and multiple
deadlines in a heterogeneous environment. J. Parallel Distrib. Comput., vol. 67, pages154–169, February 2007.→ pages7, 27
[Magoules 2009] Frederic Magoules, Jie Pan, Kiat-An Tan andAbhinit Kumar. Introduction togrid computing. CRC Press, Inc., Boca Raton, FL, USA, 2009.→ pages1, 4
[Maheswaran 1999] Muthucumaru Maheswaran, Shoukat Ali, Howard Jay Siegel, Debra Hensgenand Richard F. Freund.Dynamic mapping of a class of independent tasks onto heteroge-
neous computing systems. J. Parallel Distrib. Comput., vol. 59, pages 107–131, November1999.→ pages27
[Russell 2009] Stuart Russell and Peter Norvig. Artificial Intelligence: A Modern Approach (3rdEdition). Prentice Hall, 3 édition, December 2009.→ pages6
[Sathya 2010] S. Siva Sathya and K. Syam Babu.Survey of fault tolerant techniques for grid.Computer Science Review, vol. 4, no. 2, pages 101 – 120, 2010.→ pages4
[Siegel 2000] Howard Jay Siegel and Shoukat Ali.Techniques for mapping tasks to machines in
heterogeneous computing systems. Journal of Systems Architecture, vol. 46, no. 8, pages
627 – 639, 2000.→ pages1
30