¹INRIA, France ²University of California at Berkeley, U.S.A. ³Sybase Inc., U.S.A.

Anotácia

BOINC, stredne chránený systém pre dobrovoÂľnícke výpoèty, dovoÂľuje hostiteÂľom pripojenie k viacerým projektom. KaĹľdý hostiteÂľ periodicky Ĺľiada prácu zo servera projektu a vykonáva prácu. Tento proces zahròuje štyri súvisiace postupy:

1. spustiteÂľné úlohy na hostiteÂľovi, èo urobiÂť?

2. kedy a z ktorého projektu by mal hostiteÂľ ĹľiadaÂť ĂŻalšiu prácu?

3. koÂľko jednotiek by mal server poslaÂť v odpovedi na danú ĹľiadosÂť?

4. ako odhadnúÂť zostávajúci èas výpoètu úlohy?

V tomto èlánku zvaĹľujeme niekoÂľko alternatív pre kaĹľdý z týchto postupov. PouĹľitím simulovania, študujeme rôzne kombinácie postupov, porovnávame ich na základe niekoÂľkých vykonaní metriky a v rozsahu parametrov, takých ako premenlivosÂť trvania úlohy, nepresný hranièný termín, a poèet pripojených projektov.

1 Úvod

DobrovoÂľnícky výpoèet je forma distribuovaného výpoètu, v ktorom široká verejnosÂť dobrovoÂľníkov spracováva a akumuluje zdroje pre výpoèet projektov. Ranné dobrovoÂľnícke výpoètové projekty zahàòajú Great Internet Mersenne Prime Search [12] a Distributed.net [1]. BOINC (Berkeley Open Infrastructure for Network Computing - Otvorená infraštruktúra pre sieÂťové výpoèty z Berkeley) je stredne chránený systém pre dobrovoÂľnícky výpoèet [6, 3]. BOINC projekty sú nezávislé; kaĹľdý má svoj vlastný server, aplikácie a úlohy. DobrovoÂľníci sa podieÂľajú èinnosÂťou softvéru BOINC klienta na svojich poèítaèoch (hostiteÂľoch). DobrovoÂľníci môĹľu pripojiÂť kaĹľdého hostiteÂľa k hociktorému súboru projektov. Aktuálne je okolo 40 projektov zaloĹľených na BOINC a okolo 400,000 dobrovoÂľníckych poèítaèov vykonáva priemerne viac neĹľ 500 TeraFLOPs.

BOINC softvér pozostáva zo zloĹľiek klienta a servera. BOINC klient spúšÂťa aplikácie projektu, a vykonáva CPU plánovanie (implementované na vrchol lokálneho plánovaèa operaèného systému). Všetky sieÂťové komunikácie v BOINC sú spúšÂťané klientom; tento periodicky vyĹľaduje jednotky od serverov projektov, do ktorých je pripojený. Niektorí hostitelia majú prerušované fyzické sieÂťové pripojenia (napríklad, prenosné poèítaèe alebo tie s pripájaním cez modem). Také poèítaèe sa môĹľu pripojiÂť len kaĹľdých niekoÂľko dní, a BOINC sa pokúša naèítaÂť dostatok práce na "zamestnanie" poèítaèa aĹľ do nasledujúceho pripojenia.

Tento proces získavania a vykonávania práce zahròuje štyri súvisiace postupy:

1. CPU plánovanie (CPU scheduling): z aktuálne spustiteÂľných jednotiek, ktorú spustiÂť?

2. Sprístupnenie práce (Work fetch): kedy ĹľiadaÂť projekt o ĂŻalšiu prácu, ktorý projekt ĹľiadaÂť, a ako veÂľa práce poĹľadovaÂť?

3. Odoslanie práce (Work send): keĂŻ projekt prijíma poĹľiadavku práce, aké jednotky by mal poslaÂť?

4. Odhad èasu dokonèenia (Completion time estimation): ako odhadnúÂť zostávajúci CPU èas úlohy?

Tieto postupy majú veÂľký vplyv na výkonnosÂť projektov zaloĹľených na BOINC. PretoĹľe štúdium týchto postupov na mieste je obtiaĹľne, vyvinuli sme simulaèný program, ktorý modeluje BOINC klienta a súbor projektov. Tento simulaèný program sme pouĹľili na porovnanie niekoÂľkých kombinácií postupov plánovania, v rozsahu parametrov takých ako premenlivosÂť trvania úlohy, nepresný hranièný termín, a poèet pripojených projektov.

So simulaèným programom sú naše hlavné ciele ukázaÂť efektivitu postupov plánovania v scenároch predstavujúcich aktuálne naèítanie práce projektu, a tieĹľ hypoteticky extrémnych scenároch ktoré odráĹľajú schopnosÂť plánovaèa zaoberaÂť sa naèítaním novej ĂŻalšej jednotky.

Zvyšok èlánku je usporiadaný nasledovným spôsobom. V èasti 2, opisujeme rôzne postupy plánovania podrobne. Potom v èasti 3, podrobne opisujeme simulaèný program a jeho vstupné parametre. V èasti 4, opisujeme našu metriku pre hodnotenie rôznych aspektov kaĹľdého postupu plánovania. V èastiach 5 a 6, predstavujeme výsledky nášho hodnotenia a ich rozvinutie. V èasti 7, porovnávame našu prácu s ĂŻalšími príbuznými prácami. Koneène, v èasti 8, rekapitulujeme hlavné zhrnutia tohoto èlánku.

2 Detaily postupu plánovania

Postupy plánovania majú niekoÂľko vstupov. Prvým sú hardvérové charakteristiky hostiteÂľa, také ako poèet procesorov a porovnávacie testy. Klient hÂľadá rôzne charakteristiky pouĹľitia, také ako efektívny podiel (podiel doby spusteného BOINC a doby dovoleného výpoètu), a štatistiky jeho sieÂťovej pripojiteÂľnosti.

Druhým sú uĹľívateÂľské preferencie. Tieto zahàòajú:

• Zdroje poskytované pre kaĹľdý projekt.

• Obmedzenia pre vyuĹľívanie procesora: èi poèítaÂť pokiaÂľ je poèítaè pouĹľívaný, maximálny poèet CPU pre pouĹľívanie, a maximálny podiel CPU èasu pre pouĹľívanie (dovoÂľuje pouĹľívateÂľovi zredukovaÂť zahrievanie CPU).

• Interval pripojenia (ConnectionInterval): minimálna doba medzi periódami aktivity siete. Toto dovoÂľuje uĹľívateÂľovi poskytnúÂť "tip" o tom, ako èasto sa pripája, a to dovoÂľuje modemu pouĹľívateÂľa povedaÂť BOINCu ako èasto ho má ĹľiadaÂť o automatické pripojenie.

• Interval plánovania (SchedulingInterval): "èasový interval" plánovaèa CPU BOINC klienta (implicitná hodnota je jedna hodina).

• Zásoba práce (WorkBufMinDays): koÂľko práce do zásobníka.

• Prídavná zásoba práce (WorkBufAdditional): koÂľko práce do zásobníka okrem WorkBufMinDays.

Koneène, kaĹľdá úloha (tj. pracovná jednotka) má niekoÂľko projektom špecifikovaných parametrov, vrátane odhadu poètu jej operácií s pohyblivou rádovou èiarkou, ako aj hranièný termín, do ktorého by mala byÂť odoslaná. Väèšina BOINC projektov pouĹľíva niekoÂľkonásobný výpoèet, v ktorom dva alebo viac prípadov kaĹľdej úlohy sú spracované na rozdielnych hostiteÂľoch. Ak hostiteÂľ nenavráti úlohu do jej hranièného termínu, uĹľívateÂľ obyèajne nedostane kredit za úlohu. Budeme študovaÂť dva alebo tri varianty kaĹľdého postupu, ako je opísané niĹľšie.

2.1 Postupy plánovania CPU

CS1: cyklická obsluha rozvrhovania èasu medzi projektmi, váĹľeného podÂľa ich podielu zdrojov.

CS2: simulácia váĹľenej cyklickej obsluhy (round-robin - RR) plánovania, identifikujúc úlohy, ktoré nestihnú svoje hranièné termíny. Naplánuje teda úlohy s najskorším hranièným termínom najskôr (earliest deadline first - EDF). Ak sú zostávajúce CPU, naplánuje ĂŻalšie úlohy pouĹľitím váĹľenej cyklickej obsluhy.

2.2 Postupy volania práce

WF1: drĹľaÂť dostatok práce stojacej vo fronte postaèujúcej pre WorkBuf-MinDays+WorkBufAdditional, a rozdeliÂť túto frontu medzi projekty podÂľa podielu zdrojov, aby kaĹľdý projekt mal vĹľdy prinajmenšom jednu úlohu rozbehnutú, alebo stojacu vo fronte.

WF2: udrĹľiavaÂť "dlhodobý dlh" práce pre kaĹľdý projekt. PouĹľitie simulácie váĹľenej cyklickej obsluhy k odhadu jeho CPU schodku. VyvolaÂť prácu od projektu pre ktorý je dlh - manko najväèší. ZabrániÂť opätovnému privolávaniu práce od projektu s "napnutým" hranièným termínom. Detaily tohoto postupu sú dané v [14].

2.3 Postupy posielania práce

WS1: daná poĹľiadavka na X sekúnd práce, pošle súbor úloh ktorých odhadovaná doba výpoètu (zaloĹľená na FLOPS odhadoch, porovnávacích testoch, atĂŻ.) je najmenej X.

WS2: správa Ĺľiadosti obsahuje zoznam všetkých rozpoèítaných úloh na hostiteÂľovi, vrátane ich hranièných termínov a èasov dokonèenia. Pre kaĹľdého "kandidáta" úlohy J, robí EDF simuláciu aktuálnej pracovnej náplne s J pridanou. Pošle J len ak táto vyhovuje jej hraniènému termínu, všetky úlohy ktoré aktuálne vyhovujú ich hranièným termínom pokraèujú tak aby boli dokonèené, a všetky úlohy, ktoré nestihnú svoje hranièné termíny, ich ešte viac "nezmeškávali".

2.4 Postupy odhadu dokonèenia úlohy

JC1: BOINC aplikácie hlásia ich vykonané èasti periodicky v priebehu výpoètu. SpoÂľahlivosÂť odhadu zaloĹľeného na vykonanej èasti zvyšuje pravdepodobnosÂť s postupom úlohy.

Preto, pre úlohy v priebehu BOINC pouĹľíva odhad FA + (1 - F)B, kde F je vykonaná èasÂť, A je odhad zaloĹľený na uplynutom CPU èase a vykonanej èasti, a B je odhad zaloĹľený na porovnávacích testoch, výpoète s pohyblivou rádovou èiarkou, uĹľívateÂľských preferenciách, a CPU úèinnosti (stredná hodnota prevodového pomeru CPU èasu k reálnemu èasu pre tento projekt).

JC2: udrĹľovaÂť pre kaĹľdý projekt korekèný faktor trvania (duration correction factor - DCF), odhad prevodového pomeru efektívneho CPU èasu k pôvodne odhadovanému CPU èasu. Toto je vypoèítané konzervatívnym spôsobom; zvýšenia sa odzrkadlia okamĹľite, ale zníĹľenia sú exponenciálne vyhladené.

"úplný" postup je alternatíva kaĹľdého dielèieho postupu (napríklad, CS2_WF2_WS2_JC2).

3 Scenáre plánovania

Tieto postupy plánovania vyhodnocujeme pouĹľitím simulaèného programu BOINC klienta. Simulaèný program imituje logiku CPU plánovania a postupy volania práce klientom presne podÂľa zdrojového kódu samotného. Tento bol vhodne vyrobený pretvorením zdrojového kódu BOINC klienta tak, Ĺľe kód plánovaèa je naprosto oddelený od kódu poĹľadovaného pre pripojenie do siete a sprístupnenia pamäte. Ako taký, sa simulaèný program pripojí k reálnemu BOINC kódu plánovania s malou modifikáciou. V skutoènosti, len kód pre sprístupnenie siete (tj. RPC pre nadviazanie kontaktu s projektom a dátovými servermi) je nahradený simulaèným testovacím kódom. Teda, logika plánovania a skoro celý zdrojový kód simulovaného klienta sú identické s reálnym.

Simulaèný program dovoÂľuje špecifikovaÂť nasledovné parametre:

• Pre hostiteÂľa:

  • Poèet CPU a rýchlosÂť CPU.

  • Podiel èasu k dispozícii

  • Trvanie intervalov dostupnosti ako exponenciálne rozdelenie s parametrom λ_avail

  • Interval pripojenia - ConnectionInterval

• Pre klienta:

  • Interval plánovania CPU

  • Minimálna zásoba práce - WorkBufMinDays, dodatoèná zásoba práce - WorkBufAdditional

• Pre kaĹľdý projekt:

  • Podiel zdrojov

  • Medza latencie (tj. hranièný termín úlohy)

  • Odhad FLOPs - poètu operácií úlohy

  • Aktuálne rozdelenie (normálne) FLOPs úlohy

TabuÂľka 1. Parametre simulaèného programu.

TabuÂľka 2. Parametre projektu.

KaĹľdá kombinácia parametrov je nazvaná scenár.

Pri simulaèných experimentoch pouĹľívame hodnoty ukázané v tabuÂľkách 1,2,3 a 4 ako základné vstupné parametre do simulaèného programu. V našich simulaèných experimentoch variujeme nastavenie jedného alebo malej podmnoĹľiny týchto parametrov, pri ponechaní konštantných hodnôt ostatných parametrov. To je vhodné pre identifikovanie (extrémnej) situácie, kde konkrétny postup plánovania pracuje zle.

Hodnoty ukázané v týchto tabuÂľkách sú vybraté tak realisticky, ako je moĹľné pouĹľitím dát vybratých z reálnych projektov, pretoĹľe presnosÂť simulácie silno závisí na týchto hodnotách a ich proporciách vzhÂľadom k ostatným. Pre parametre hostiteÂľa a projektu pouĹľívame stredné hodnoty zistené z reálnych BOINC projektov ako je opísané v [7, 2]. Pre parametre klienta pouĹľívame implicitné hodnoty v reálnom klientovi.

TabuÂľka 3. Parametre hostiteÂľa.

TabuÂľka 4. Parametre klienta.

4 Vykonávanie metriky

PouĹľívame nasledovné metriky v hodnotení postupov plánovania:

1. NeèinnosÂť (Idleness): nevyuĹľitý podiel z celkového CPU èasu k dispozícii, pretoĹľe nie sú Ĺľiadne spustiteÂľné úlohy. Tento je v rozmedzí [0;1], a je v ideálnom prípade nula.

2. Strata (Waste): podiel CPU èasu vyuĹľitého úlohami, ktoré nestihli svoj hranièný termín.

3. NedodrĹľanie podielu (Share violation): miera presnosti rešpektovania podielov zdrojov uĹľívateÂľa , kde 0 je najlepšie a 1 je najhoršie.

4. MonotónnosÂť (Monotony): obrátená miera toho, ako èasto hostiteÂľ prepína medzi projektmi: 0 je tak èasto ako je moĹľné (daný interval plánovania a iné faktory) a 1 znamená bez prepínania. Táto metrika reprezentuje skutoènosÂť, Ĺľe ak dobrovoÂľník venoval rovnaký podiel zdrojov pre dva projekty, a jeho poèítaè navštevuje èinnosÂťou len jeden z nich po dlhú dobu, bude neuspokojený.

5 Výsledky a diskusia

5.1 Postupy plánovania CPU

V tejto èasti porovnávame postup ktorý pouĹľíva len cyklickú obsluhu rozvrhovania èasu (CS1_WF2_WS2_JC2) s postupom, ktorý bude potenciálne plánovaÂť (niektoré) úlohy v EDF móde, ak ich hranièné termíny sú v riziku nestihnutia (CS2_WF2_WS2_JC2).

Pre simulovanie reálneho stiahnutia úloh z projektov musíme zaistiÂť, aby existovala zmes projektov s mnoĹľstvom veÂľkostí úloh a hranièných termínov. Preto definujeme termín zmes (mix) nasledovným spôsobom. SÂťahovanie úloh má mix M ak obsahuje M projektov, a klient je registrovaný kaĹľdým projektom P_i, kde 1 ≤ i ≤ M, a kaĹľdý projekt P_i má nasledovné charakteristiky:

priemer FLOPs na úlohu = i × FLOPs základný

medza oneskorenia = i × medza oneskorenia základná

podiel zdrojov = i × podiel zdrojov základný,

kde základné hodnoty sú hodnoty definované v tabuÂľkách 1, 3, a 4.

(a) strata

(b) monotónnosÂť projektu

obrázok 1. Plánovanie CPU

Variujeme M od 1 do 20 pre kaĹľdú simuláciu sÂťahovania úloh. Výsledky sú ukázané v obrázku 1. Pozorujeme, Ĺľe CS2_WF2_WS2_JC2 èasto prevyšuje CS1_WF2_WS2_JC2 o viac neĹľ 10% kvôli strate keĂŻ mix projektu je väèší ako 3. Zvýšený výkon CS2_WF2_WS2_JC2 môĹľe byÂť vysvetlený zmenou na EDF mód, keĂŻ hranièné termíny úloh sú v riziku.

Pre neèinnosÂť, nedodrĹľanie podielu, a monotónnosÂť projektu, výkonnosÂť CS2_WF2_WS2_JC2 a CS1_WF2_WS2_JC2 je pribliĹľne ekvivalentná. nedodrĹľanie podielu je nízke, obyèajne pod 0,10, a rastie len nepatrne s poètom projektov a kombinácií (mixu). PokiaÂľ ide o neèinnosÂť, oba postupy majú výrazne nízke (blízko nuly) neèinnosti pre hocijaký poèet projektov a kombinácií (mixu). Naopak, monotónnosÂť projektu inklinuje k znaènému zvýšeniu s rastom mixu projektu. ZisÂťujeme, Ĺľe pomerne dlhé úlohy môĹľu èasto spôsobovaÂť monotónnosÂť, hlavne keĂŻ úloha je v nebezpeèenstve nestihnutia hranièného termínu a plánovaè prepne na EDF mód aby zaistil jej vèasné dokonèenie. V skutoènosti, vzrast monotónnosti s dĂĄĹľkou úlohy je nutný ale akceptovateÂľný, daný dôleĹľitejším cieÂľom stihnutia uzávierky úlohy a minimalizovaÂť stratu. Teda, v takmer všetkých prípadoch, postup CS2_WF2_WS2_JC2 kombinujúci EDF s RR pôsobí rovnako ako CS1_WF2_WS2_JC2.

Ako vedÂľajší úèinok z týchto experimentov, determinujeme rozšíriteÂľnosÂť BOINC klienta vzhÂľadom na poèet projektov. (Jeden by sa mohol spýtaÂť, ako sa uĹľívateÂľ môĹľe zapísaÂť do 20 projektov. Tento scenár môĹľe veÂľmi dobre vzniknúÂť, keĂŻĹľe poèet projektov rýchlo stúpa, a myšlienka projektu "spoloèného fondu" bola navrhnutá, kde projekty sú zoskupené istou charakteristikou [napríklad: nezárobkový, výpoètová biológia], a uĹľívateÂľský register pre fondy nielen pre projekty.)

ZisÂťujeme, Ĺľe dokonca keĂŻ poèet projektov sa blíĹľi k 20, strata, neèinnosÂť, a nedodrĹľanie podielu zostávajú relatívne konštantné v celom rozsahu medzi 1-20. Výnimkou je monotónnosÂť projektu, ktorá stúpa rýchlo, ale je akceptovateÂľná. Teda vyvodzujeme, Ĺľe plánovaè "ladí" s poètom projektov. Vo zvyšku tohoto paragrafu, preskúmame ĂŻalej CS2_WF2_WS2_JC2 postup vzhÂľadom na nepresný hranièný termín a veÂľkosÂť zásobníka.

5.1.1 VoÂľný termín uzávierky

Obrázok 2. VoÂľnosÂť

V tejto èasti vyšetríme citlivosÂť CS2 WF2 WS2 JC2 na medzu èakacej doby vzhÂľadom k priemernej dobe výpoètu úlohy na danom poèítaèi. VoÂľnosÂť (slack) definujeme ako podiel hranice èakacej doby a priemeru FPOPS odhadu násobeného prevrátenou hodnotou rýchlosti hostiteÂľa. Potom spustíme simulácie testovania plánovaèa so samostatným projektom a rozsahom hodnôt voÂľnosti od 1 do 60. VoÂľnosÂť 1 znamená, Ĺľe medza latencie je pribliĹľne ekvivalentná dobe výpoètu. VoÂľnosÂť 60 znamená, Ĺľe hranica latencie je 60 krát väèšia neĹľ priemerná doba výpoètu na danom poèítaèi. My vyberieme túto maximálnu hodnotu pretoĹľe ona v skutoènosti reprezentuje strednú voÂľnosÂť spomedzi všetkých existujúcich BOINC projektov [7]. To jest, spracovanie úloh v mnohých projektoch je rádovo v hodinách, kde ako medza latencie je v termíne dni.

Obrázok 2 ukazuje výsledok simulácie testovania voÂľnosti. Samozrejme, podiel nedodrĹľania a monotónnosti sú 0 pokiaÂľ máme len samostatný projekt. NeèinnosÂť je 0 kvôli malému intervalu pripojenia a tak plánovaè èiní perfektnú sluĹľbu vyĹľadovania práce. Avšak, inklinuje k privolaniu viac práce, neĹľ môĹľe vypoèítaÂť. ZisÂťujeme, Ĺľe pre voÂľnosÂť 1 je strata 1, a rýchlo klesá k 0 keĂŻ voÂľnosÂť dosahuje 5. Strata príslušná k hodnotám voÂľnosti 2, 3, 4, a 5 je 0,75; 0,24; 0,02 a 0 v tomto poradí. PodÂľa toho, pre hodnoty voÂľnosti väèšie alebo rovnajúce sa 5, strata ostáva pri 0. Po starostlivej prehliadke našich experimentov simulácie zisÂťujeme, Ĺľe nevyuĹľiteÂľnosÂť hostiteÂľa (nastavená na 20% èasu) je ten hlavný faktor, ktorý spôsobuje vysokú hodnotu straty, keĂŻ je voÂľnosÂť blízko 1. To jest, ak hostiteÂľ je nevyuĹľiteÂľný 20% èasu, potom 3,67 hodiny práce na danom poèítaèi zaberie 4,58 hodiny v priemere a pravdepodobne prevýši medzu latencie 3,67 hodiny.

Iný dôvod straty je celková veÂľkosÂť zásobníka práce, ktorá je nastavená na implicitnú hodnotu 0,35 (= 0,25 + 0,1) dòa. KeĂŻ veÂľkosÂť zásobníka práce sú špecifikovaná, klient zaisÂťuje, aby privolával najmenej takú hodnotu práce pri kaĹľdej Ĺľiadosti. Nastavenie hodnoty ktorá je príliš vysoká, môĹľu maÂť za následok privolanie príliš mnoho práce, ktorá nemôĹľe byÂť dokonèená do uzávierky. Túto záleĹľitosÂť ĂŻalej vyšetríme v nasledujúcej sekcii.

5.1.2 VeÂľkosÂť zásobníka

Na podporu našej hypotézy , Ĺľe veÂľkosÂť zásobníka je závaĹľný faktor ktorý prispieva k strate, sme vykonali simulácie s rozdielny veÂľkosÂťami zásobníka. Predovšetkým sme zisÂťovali ako strata variuje ako funkcia veÂľkosti zásobníka a voÂľnosti. Menili sme voÂľnosÂť od 1 do 5, èo zodpovedalo rozsahu hodnôt voÂľnosti na obrázku 2, èo konèilo kladnou stratou (okrem voÂľnosti 5, kde strata bola 0). Variovali sme veÂľkosÂť zásobníka medzi cca 1 a 8,4 hodiny práce. Maximálna hodnota v tomto rozsahu zodpovedá prednastavenej hodnote veÂľkosti zásobníka pouĹľívanej klientom, tj. 0,35 dòa, a pouĹľívanej pre experimenty s voÂľnosÂťou v èasti 5.1.1.

Obrázok 3. Strata ako funkcia minima veÂľkosti zásobníka a voÂľnosti

Obrázok 3 ukazuje výsledok našich simulácií. Rozdielne farby kaĹľdého segmentu krivky zodpovedajú rozdielnym hodnotám straty. KeĂŻ veÂľkosÂť zásobníka je v jeho maximálnej hodnote, vyplývajúca strata ako funkcia voÂľnosti je identická so stratou ukázanou na obrázku 2. Ako sa veÂľkosÂť zásobníka zniĹľuje, strata (a poèet zmeškaných uzávierok) dramaticky klesá. Pre prípad kde je voÂľnosÂť 2, strata je konštantná pre veÂľkosti zásobníka medzi 5 a 7 hodinami. Je to jednoducho preto, Ĺľe veÂľkosti úloh sú okolo 3,67 hodiny, a tak prírastkové zvyšovania veÂľkosti zásobníka nemôĹľu zmeniÂť poèet úloh stiahnutých zo servera.

Hoci zmenšovanie veÂľkosti zásobníka môĹľe tieĹľ zníĹľiÂť stratu, výnimka je keĂŻ voÂľnosÂť je 1; strata ostáva na 1 bez ohÂľadu na veÂľkosÂť zásobníka. Je to kvôli nevyuĹľiteÂľnosti hostiteÂľa a jeho vplyvu na dobu výpoètu úlohy. To má menší vplyv, keĂŻ voÂľnosÂť dosahuje 2, kedy je hostiteÂľ nevyuĹľiteÂľný len 20% èasu, a zodpovedá spomaleniu menej neĹľ 2.

Vyvodzujeme, Ĺľe zmenšovanie veÂľkosti zásobníka práce môĹľe maÂť za následok obrovské zníĹľenie straty, ale výhody sú limitované dostupnosÂťou klienta. Avšak, jeden nemôĹľe nastaviÂť veÂľkosÂť zásobníka práce ÂľubovoÂľne nízku, pretoĹľe to by mohlo maÂť za následok èasté zahltenie servera so ĹľiadosÂťami o prácu od klientov. Budeme vyšetrovaÂť tieto zaujímavé problémy v ĂŻalšej práci.

5.2 Postupy vyĹľadovania práce

V tejto èasti porovnáme dva spôsoby urèovania ktorý projekt má poĹľadovaÂť ĂŻalšiu prácu, a koÂľko práce má poĹľadovaÂť. KeĂŻ sa vytvára poĹľiadavka práce, prvý postup (CS2_WF1_WS2_JC2) sa pokúša zaistiÂť, aby fronta práce bola naplnená poĹľadovaním práce podÂľa poskytnutých zdrojov, aby prinajmenšom jedna jednotka bola poèítaná, alebo stála vo fronte. Druhý postup (CS2_WF2_WS2_JC2) stanovuje, aký je "dlhodobý dlh" prisúdený kaĹľdému projektu, a poĹľaduje prácu od projektu s najväèším rozdielom medzi dlhom a naplnením. (Podrobnosti o kaĹľdom postupe môĹľete nájsÂť v [14].)

ZisÂťujeme, Ĺľe strata pre CS2_WF1_WS2_JC2 inklinuje k dramatickému zvýšeniu s mixom projektov (pozri obrázok 4a), a Ĺľe narušenie podielu je relatívne vysoké (pozri obrázok 4b), keĂŻ úlohy pre projekty s tesnými uzávierkami sú stiahnuté, a predbiehajú iné menej naliehajúce jednotky, spôsobujúc, Ĺľe tieto premeškajú svoje uzávierky. Naopak, CS2_WF2_WS2_JC2 zlepšuje stratu o takmer 90% a nedodrĹľanie podielu o takmer 50%, pretoĹľe postup sa vyhýba privolávaniu práce z projektov s tesnými uzávierkami. (NeèinnosÂť a monotónnosÂť pre oba postupy boli skoro identické.)

a) strata

b) nedodrĹľanie zdrojov

Obrázok 4. VyĹľadovanie práce

5.3 Postupy odosielania práce

V tejto èasti porovnávame dva postupy pre odoslanie práce zo servera. Prvý postup (CS2_WF2_WS1_JC2) jednoducho posiela mnoĹľstvo práce Ĺľiadanej klientom. Druhý postup (CS2_WF2_WS2_JC2) kontroluje prostredníctvom simulácie EDF priamo serverovou stranou, èi by nanovo Ĺľiadané úlohy vyhoveli ich uzávierkam, èi všetky rozpoèítané úlohy na klientovi by stále stihli svoje uzávierky, a èi všetky rozpoèítané úlohy na klientovi, ktoré nestihnú svoje uzávierky, nespôsobia zmeškanie pre ĂŻalšie.

Zistili sme, Ĺľe druhý postup posielania práce CS2_WF2_WS2_JC2 je výhodný len keĂŻ je relatívne mnoho úloh na klientovi (majúcom veÂľký zásobník práce stojacej vo fronte), a ak mnoĹľstvo práce na úlohu má vysokú premenlivosÂť. Toto by mohlo vytvoriÂť "ideálny" stav tam, kde by nové úlohy mohli prerušiÂť rozpoèítané úlohy. A tak k ukázaniu efektivnosti postupov posielania práce sme zvýšili interval pripojenia a veÂľkosÂť zásobníka práce na 2 dni, variovali smerodajnú odchýlku FPOPS na úlohu faktorom s relatívne k priemernej veÂľkosti úlohy, a vytvorili dva projekty s rovnakými podielmi zdrojov a veÂľkosÂťou úloh, ktoré sa odlišujú faktorom 10.

Na obrázku 5 variujeme smerodajnú odchýlku s veÂľkosti úlohy faktorom s medzi 1 a 1000. ZisÂťujeme, Ĺľe CS2_WF2_WS2_JC2 èasto nedosahuje CS2_WF2_WS1_JC2 o 20% alebo viac z hÂľadiska straty, za cenu neèinnosti, ktorá je èasto vyššia o 20% alebo viac. Hlavný dôvod pre tento výsledok je, Ĺľe CS2_WF2_WS2_JC2 je prirodzene konzervatívnejší v odoslaní úloh ku klientovi, èo redukuje nestihnutie uzávierky, ale na druhej strane spôsobuje èastejšiu neèinnosÂť.

a) strata

b) Neèinnos

Obrázok 5. Odosielanie práce

5.4 Postupy odhadu dokonèenia úlohy

Na vytvorenie a formovanie jednotiek projektu, vývojár aplikácie musí poskytnúÂť odhad mnoĹľstva práce v FPOPS na jednotku. Tento odhad je na druhej strane pouĹľívaný plánovaèom klienta spolu s hranièným termínom jednotky na formovanie Ĺľiadostí práce a na urèenie akú prácu naplánovaÂť ĂŻalej. Avšak, odhady uĹľívateÂľa sú èasto notoricky mimo od aktuálnej hodnoty práce. Toto bolo evidentné v dobrovoÂľníckych systémoch spracovaniach údajov ako BOINC a tieĹľ pri vyuĹľívaní tradièných MPP [13]. Plánovaè ako taký, pouĹľíva korekèný faktor trvania na kompenzovanie hocijakej chyby v odhade, zaloĹľený na histórii vypoèítaných úloh.

V tejto èasti meriame dopad pouĹľitia DCF na rozpätie chýb odhadu porovnaním CS2_WF2_WS2_JC1 s CS2_WF2_WS2_JC2.

Nech f je èiniteÂľ chyby taký, Ĺľe odhadovaná uĹľívateÂľova práca na jednotku je daná aktuálnou prácou delenou f. KeĂŻ f = 1, odhad uĹľívateÂľa zodpovedá aktuálnemu presne. KeĂŻ f > 1, potom odhad uĹľívateÂľa podceòuje mnoĹľstvo reálnej práce.

Pozorujeme, Ĺľe spoèiatku, keĂŻ odhad zodpovedá skutoènosti, potom ako postup s DCF (keĂŻ je nastavený k vyrovnaniu hocijakej chyby) tak aj postup bez DCF (keĂŻ je vĹľdy nastavený na 1) majú identický výkon v zmysle straty (vid obrázok 6). Pre vyššie chybové èinitele, postup s DCF znaène zaostáva za postupom, ktorý ho vynecháva. Strata pre DCF ostáva pozoruhodne konštantná bez ohÂľadu na èiniteÂľ chyby, kým strata pre postup bez DCF rýchlo stúpa. V skutoènosti, strata dosahuje takmer 1, keĂŻ je odhad práce 4 krát menší neĹľ skutoèná. PokiaÂľ ide o rýchlosÂť konvergencie k správnemu DCF, po podrobnej kontrole krivky našej simulácie sme zistili, Ĺľe DCF konverguje priamo k správnej hodnote po poèiatoènom volaní práce. (Pre struènosÂť ukazujeme len obrázok pre stratu; všetky ĂŻalšie hodnoty pre neèinnosÂť, narušenie podielu, a monotónnosÂť projektu boli nulové.)

Obrázok 6. Dokonèenie jednotky

6 Umiestnenie

Plánovaè klienta bol zrealizovaný v C++ a rozmiestnený na asi milióne hostiteÂľov cez Internet [6, 3]. Jedno z primárnych hodnotení pre èinnosÂť v reálnych nastaveniach je spätná väzba od uĹľívateÂľov o postupoch plánovania. UĹľívatelia majú niekoÂľko spôsobov priamo alebo nepriamo monitorovaÂť plánovanie klienta, vrátane schopnosti zaznamenaÂť aktivity plánovaèa klienta s jednoduchým oznaèením ladenia, alebo hodnotou kreditu im prideleného. (Všeobecne, projekty priznajú len kredit za prácu vyhotovenú pred uzávierkami.) Od zavedenia postupov zodpovedajúcich CS2_WF2_WS2_JC2, poèet sÂťaĹľností poslaných BOINC vývojárom bol zníĹľený na asi jednu za mesiac. Tieto sÂťaĹľnosti sa prièítajú najmä názorovým rozdielom ako by mal BOINC plánovaè pracovaÂť, a nie zvlášÂť podstatné pre hodnotenie èinnosti ako je definovaná v èasti 4.

7 Súvisiace práce

Dvaja autori tohto èlánku nedávno podrobne opísali rovnaké postupy plánovania v [14]. Ale tam bolo malé hodnotenie èinnosti, pretoĹľe študujú. Mimo tejto práce, výpoètové mrieĹľky [10, 11] sú najbliĹľšie hlavnej èasti skúmania týkajúceho sa dobrovoÂľných výpoètov, a plánovanie v nestálosti a rôznorodosti bolo vyšetrené intenzívne v oblasti skúmania mrieĹľky [4, 5, 8, 9]. Avšak je veÂľa dôvodov preèo tieto stratégie sú neaplikovateÂľné na dobrovoÂľné výpoèty.

Prvý, rozvrhovacie algoritmy a postupy èasto predpokladajú, Ĺľe práca môĹľe byÂť viazaná na zdroje samotné, èo v dobrovoÂľných výpoètoch je vylúèené bezpeènostnými bránami a NAT - prekladmi sieÂťových adries. V dôsledku toho plán urèený postupom pre prostredia mrieĹľky nemôĹľe byÂť úspešne rozvinutý, pretoĹľe zdroje sú nedosiahnuteÂľné zo servera priamo.

Druhý, v dobrovoÂľných systémoch spracovania údajov sú viaceré faktory (a èasto rádovo) viac nestále a rôznorodé neĹľ grid systémy, a teda èasto vyĹľadujú nový súbor stratégií pre riadenie zdrojov a plánovanie.

Koneène, podÂľa našej znalosti, práca predstavená tu je prvá prípad, kde plánovanie pre dobrovoÂľný výpoèet sa deje v mieste zdrojov samotných, a kde plánovaè je hodnotený s novým súborom metriky, menovite stratou spôsobenou zmeškaním uzávierky, neèinnosÂťou, narušením podielu, a monotónnosÂťou.

8 Zhrnutie

V nasledujúcom sú hlavné závery z našich simulaèných výsledkov a analýz:

1. Plánovanie CPU (CPU scheduling): EDF simulácia má èasto za následok 10% zlepšenie výkonu detekciou a vèasným zabránením moĹľného zmeškania uzávierky.

2. Privolanie práce (Work fetch): Privolávanie práce zaloĹľené na dlhodobom dlhu a CPU naplnenia je lepšie ako privolávanie práce proporcionálne podÂľa podielu zdrojov. Zdokonalenie pouĹľitia niekdajšieho postup zlepšuje stratu o takmer 90% a narušenie podielu o takmer 50% zabránením privolania práce od projektov s nedostaèujúcimi uzávierkami.

3. Odosielanie práce (Work send): Simulácia strany servera k urèeniu dopadu nových úloh na existujúcu náplò práce klienta je kritická, keĂŻ veÂľkosÂť jednotiek má vysokú premenlivosÂť (smerodajná odchýlka väèšia neĹľ 10 násobok priemernej hodnoty práce na jednotku), keĂŻ klienti majú veÂľký zásobník práce, a keĂŻ sa klienti pripájajú relatívne zriedkavo.

4. Odhad èasu dokonèenia práce (Job completion time estimation): KeĂŻ odhad práce uĹľívateÂľa na jednotku je vypnutý faktorom 2 alebo väèším, udrĹľiavanie korekèného faktora trvania pre kompenzovanie tohto rozdielu je podstatné. Inak dosahuje strata èasto takmer 1.

Literatúra

[1] Distributed.net. www.distributed.net.

[2] XtremLab. http://xtremlab.lri.fr.

[3] D. Anderson. Boinc: A system for public-resource computing and storage. In Proceedings of the 5^th IEEE/ACM International Workshop on Grid Computing, Pittsburgh, USA, 2004.

[4] N. Andrade, W. Cirne, F. Brasileiro, and P. Roisenberg. OurGrid: An Approach to Easily Assemble Grids with Equitable Resource Sharing. In Proceedings of the 9th Workshop on Job Scheduling Strategies for Parallel Processing, June 2003.

[5] F. Berman, R. Wolski, S. Figueira, J. Schopf, and G. Shao. Application-Level Scheduling on Distributed Heterogeneous Networks. In Proc. of Supercomputing ’96, Pittsburgh, 1996.

[6] The berkeley open infrastructure for network computing. http://boinc.berkeley.edu/.

[7] Catalog of boinc projects. http://boinc-wiki.ath.cx/index.php?title=Catalog_of_BOINC_Powered_Proje%cts.