Domov
Novinky
Projekt
Arch├şv ?l├ínkov
Optimalizácia
Návody
Gal├ęria
Stiahnite si
Odkazy
Diskusn├ę f├│rum
F├│rum - arch├şv
Vyh┬żad├ívanie
TO-DO
Kontakt

BOINC.SK


Od 1.1.2002


Astronomickř
snÝmok
d˛a

APOD






Page Rank
 
 
Hodnotenie ├Ęinnosti pl├ínovac├şch postupov pre dobrovo┬żn├şcke v├Żpo├Ęty
Derrick Kondo1 David P. Anderson2 John McLeod VII3

1INRIA, France 2University of California at Berkeley, U.S.A. 3Sybase 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


Parameter

Hodnota

Trvanie

100 dni

Delta

60 sekúnd

Tabu┬żka 1. Parametre simula├Ęného programu.


Parameter

Hodnota

podiel zdrojov

100

medza latencie

9 dní

odhad FLOPs úlohy

1,3.1013 (3,67 hodín na ur├Ęenom 3GHz hostite┬żovi)

priemer FLOPs úlohy

1,3.1013 (3,67 hodín)

std dev (smerodajná odchýlka) FLOPs

0

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.


Parameter

Hodnota

Po├Ęet CPU

2

priradená rýchlos┬Ł CPU vo FLOPS

1.109

podiel ├Ęasu k dispozícii

0,8

λavail

1,000

interval pripojenia ConnectionInterval

0

Tabu┬żka 3. Parametre hostite┬ża.


Parameter

Hodnota

Perióda plánovania CPU

60 minút

Základná zásoba WorkBufMinDays

0,1 d├▓a (2,4 hodiny) )

Dodato├Ęná zásoba WorkBufAdditional

0,25 d├▓a (6 hodín)

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 Pi, kde 1 ≤ i ≤ M, a ka┼żdý projekt Pi 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.


obr-1-a

(a) strata

obr-1-b

(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-2

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-3

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é.)


obr-4-a

a) strata

obr-4-b


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┬Ł.

obr-5-a

a) strata


obr-5-b

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-6


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.


PDF verziu tohoto ├Ęlánku si mô┼żete stiahnu┬Ł tu.

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 5th 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.


Vytvoril: slavko.sk [08. december 2007 15:15:40] / UpravenÚ: [10. december 2007 20:22:02] / PoŔet zobrazenÝ: [9438]