¹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.