Porozumenie a dekompozícia problému
Komunikácia a synchronizácia
Granularita, dátová závislost’
I/O, obmedzenia a nároˇcnost’, vyrovnávanie zát’aže
Paralelné a distribuované výpoˇcty
Návrh paralelných programov
M. Vagaˇc
Katedra Informatiky
Fakulta prirodných vied
Univerzita Mateja Bela
29. januára 2013
M. Vagaˇc
Paralelné a distribuované výpoˇcty
Porozumenie a dekompozícia problému
Komunikácia a synchronizácia
Granularita, dátová závislost’
I/O, obmedzenia a nároˇcnost’, vyrovnávanie zát’aže
Obsah
1
Porozumenie a dekompozícia problému
Porozumenie problému
Dekompozícia problému
2
Komunikácia a synchronizácia
Komunikácia
Synchronizácia
3
Granularita, dátová závislost’
Granularita
Dátová závislost’
4
I/O, obmedzenia a nároˇcnost’, vyrovnávanie zát’aže
I/O
Obmedzenia a nároˇcnost’ paralelného spracovania
Vyrovnávanie zát’aže
M. Vagaˇc
Paralelné a distribuované výpoˇcty
Porozumenie a dekompozícia problému
Komunikácia a synchronizácia
Granularita, dátová závislost’
I/O, obmedzenia a nároˇcnost’, vyrovnávanie zát’aže
Použitá literatúra
Ján Kollár - Metódy a prostriedky pre výkonné paralelné výpoˇcty
Blaise Barney - Introduction to Parallel Computing
(https://computing.llnl.gov/tutorials/parallel_comp/)
ˇ nanský
ˇ
Michal Cer
- Paralelné programovanie
M. Vagaˇc
Paralelné a distribuované výpoˇcty
Porozumenie a dekompozícia problému
Komunikácia a synchronizácia
Granularita, dátová závislost’
I/O, obmedzenia a nároˇcnost’, vyrovnávanie zát’aže
Automatická vs. mauálna paralelizácia
Programátor je zodpovedný za identifikovanie a implementovanie
paralelizmu
Manuálna tvorba paralelného kódu je proces cˇ asovo nároˇcný,
zložitý, náchylný na chyby a iteratívny
Množstvo nástrojov pomáhajúcich pri konverzii sériového
programu na paralelný
Paralelizácia riadená programátorom
Použitím direktív pre prekladaˇc sa urˇcí, ako paralelizovat’
Plne automatická paralelizácia
Analyzuje sa zdrojový kód a identifikujú miesta vhodné pre paralel.
Najvhodnejšími miestami pre paralelyzáciu sú cykly
Množstvo problémov (nesprávne výsledky, zníženie výkonu,
neflexibilné, obmedzené)
“Svätý grál”
M. Vagaˇc
Paralelné a distribuované výpoˇcty
Porozumenie a dekompozícia problému
Komunikácia a synchronizácia
Granularita, dátová závislost’
I/O, obmedzenia a nároˇcnost’, vyrovnávanie zát’aže
Porozumenie problému
Dekompozícia problému
Porozumenie problému
Porozumenie riešeného problému
Zodpovedanie otázky, cˇ i je možné daný problém paralelizovat’
Príklady:
Výpoˇcet energie pre rôzne stavy molekuly (nezávislost’ stavov)
Výpoˇcet Fibonacci-ho postupnosti (závislé výpoˇcty)
Identifikácia “najvyt’aženejších” miest programu
Kde sa vykonáva skutoˇcný výpoˇcet, zat’ažuje CPU
Profilovanie, analýza výkonu
Identifikácia úzkych hrdiel programu
Neprimerane pomalé cˇ asti, poškodzujúce paralelizmus (napr. IO)
Možnost’ zmeny štruktúry programu, použitia iného algoritmu
Identifikácia inhibítorov pralelizmu (napr. dátová závislost’ vo
Fibonacci-ho postupnosti)
Preskúmanie iných možných algoritmov
M. Vagaˇc
Paralelné a distribuované výpoˇcty
Porozumenie a dekompozícia problému
Komunikácia a synchronizácia
Granularita, dátová závislost’
I/O, obmedzenia a nároˇcnost’, vyrovnávanie zát’aže
Porozumenie problému
Dekompozícia problému
Dekompozícia problému
Jedným z prvých krokov je rozdelenie problému na oddelené
cˇ asti, ktoré bude možné distribuovat’ rôznym úlohám
Dekompozícia, partitioning
Dva základné spôsoby rozdelenia (dekompozície):
Doménová dekompozícia
Funkcionálna dekompozícia
Je bežné (a prirodzené) tieto dva spôsoby kombinovat’
M. Vagaˇc
Paralelné a distribuované výpoˇcty
Porozumenie a dekompozícia problému
Komunikácia a synchronizácia
Granularita, dátová závislost’
I/O, obmedzenia a nároˇcnost’, vyrovnávanie zát’aže
Porozumenie problému
Dekompozícia problému
Doménová dekompozícia
Rozdelenie dát – každá paralelná úloha pracuje s cˇ ast’ou dát
Rôzne spôsoby rozdelenia
M. Vagaˇc
Paralelné a distribuované výpoˇcty
Porozumenie a dekompozícia problému
Komunikácia a synchronizácia
Granularita, dátová závislost’
I/O, obmedzenia a nároˇcnost’, vyrovnávanie zát’aže
Porozumenie problému
Dekompozícia problému
Funkcionálna dekompozícia
Rozdelenie na základe vykonávaných výpoˇctov
Každá úloha vykonáva cˇ ast’ celkových výpoˇctov
Vhodné pre problémy, ktoré je možné rozdelit’ na rôzne úlohy
Príklady:
Modelovanie klímy (model atmosféry, pevniny, oceánov)
Modelovanie ekosystému (model rastlín, bylinožravcov, dravcov,
mrchožravcov, rozkladaˇcov)
M. Vagaˇc
Paralelné a distribuované výpoˇcty
Porozumenie a dekompozícia problému
Komunikácia a synchronizácia
Granularita, dátová závislost’
I/O, obmedzenia a nároˇcnost’, vyrovnávanie zát’aže
Komunikácia
Synchronizácia
Komunikácia
Potreba komunikácie medzi úlohami závisí od problému
Nepotreba komunikácie
Problém je možné dekomponovat’ a úlohy paralelne spustit’ bez
potreby výmeny dát
Trápny paralelizmus (Embarrassingly Parallel)
Napr. odfiltrovanie farieb obrázku – obrázok je možné rozdelit’ a
každej paralelnej úlohe dat’ len jeho cˇ ast’
Potreba komunikácie
Väˇcšina paralelných programov
Napr. výpoˇcet šírenia tepla – úloha potrebuje vediet’ teploty
vypoˇcítané úlohami pracujúcimi so susednými dátami
M. Vagaˇc
Paralelné a distribuované výpoˇcty
Porozumenie a dekompozícia problému
Komunikácia a synchronizácia
Granularita, dátová závislost’
I/O, obmedzenia a nároˇcnost’, vyrovnávanie zát’aže
Komunikácia
Synchronizácia
Komunikácia – faktory
Cena komunikácie
“Nadbytoˇcnost’” (Overhead) spojený s komunikáciou (procesor
namiesto poˇcítania komunikuje)
Komunikácia cˇ asto vyžaduje urˇcitý spôsob synchronizácie medzi
úlohami (niektoré úlohy potom cˇ akajú namiesto pracovania)
Príliš vel’a komunikácie môže zahltit’ dostupné siet’ové prostriedky
Latencia vs. šírka prenosové pásma
Latencia (latency) – cˇ as potrebný na poslanie minimálnej správy
(0 bajtov) z bodu A do bodu B (µ s)
Šírka prenosového pásma (bandwidth) – množstvo dát ktoré je
možné preniest’ za jednotku cˇ asu (MB/s)
Problém s latenciou nastáva väˇcšinou pri posielaní vel’a malých
správ (ˇcasto je výhodnejšie zabalit’ malé správy do jednej väˇcšej a
viac využit’ šírku prenosového pásma)
M. Vagaˇc
Paralelné a distribuované výpoˇcty
Porozumenie a dekompozícia problému
Komunikácia a synchronizácia
Granularita, dátová závislost’
I/O, obmedzenia a nároˇcnost’, vyrovnávanie zát’aže
Komunikácia
Synchronizácia
Komunikácia – faktory
Viditel’nost’ komunikácie
V modeli zasielania správ je komunikácia explicitná a priamo pod
kontrolou programátora
V dátovo-paralelnom modeli je komunikácia pred programátorom
cˇ asto ukrytá
Synchrónnost’ komunikácie
Synchrónna komunikácia požaduje urˇcitý spôsob súˇcinnosti
(handshaking) medzi úlohami zdiel’ajúcim dáta (blokujúca – cˇ aká
sa na ukonˇcenie komunikácie)
ˇ
Nesynchrónna komunikácia umožnuje
prenášat’ dáta nezávisle
(neblokujúca – úloha 1 odošle dáta a neˇcaká, kým ich druhá úloha
prijme – môže hned’ pokraˇcovat’)
Rozsah komunikácie – ktoré úlohy majú spolu komunikovat’
Komunikácia bod-bod (point-to-point) – jedna úloha odosielatel’a
(producenta) a jedna úloha prijímatel’a (konzumenta)
Skupinová komunikácia – zdiel’anie dát medzi viac ako dvomi
úlohami
M. Vagaˇc
Paralelné a distribuované výpoˇcty
Porozumenie a dekompozícia problému
Komunikácia a synchronizácia
Granularita, dátová závislost’
I/O, obmedzenia a nároˇcnost’, vyrovnávanie zát’aže
Komunikácia
Synchronizácia
Bariérová synchronizácia
Zvyˇcajne sa týka všetkých úloh
Každá úloha pracuje až pokial’ sa nedopracuje k bariére (tam
ostane cˇ akat’)
Úlohy sú synchronizované, ked’ sa posledná úloha dopracuje k
bariére
M. Vagaˇc
Paralelné a distribuované výpoˇcty
Porozumenie a dekompozícia problému
Komunikácia a synchronizácia
Granularita, dátová závislost’
I/O, obmedzenia a nároˇcnost’, vyrovnávanie zát’aže
Komunikácia
Synchronizácia
Zámok / Semafór
Týka sa l’ubovol’ného množstva úloh
Ochránenie prístupu ku globálnym dátam
Len jedna úloha môže v danom cˇ ase vlastnit’ zámok/semafór
Prvá úloha získajúca zámok/semafór ho nastaví. Táto úloha
môže nasledne pracovat’ s chráneným dátam
Ostatné úlohy sa môžu pokúsit’ získat’ zámok/semafór – musia
však poˇckat’, pokial’ ho neuvolní úloha, ktorá ho vlastní
Môže byt’ blokujúca/neblokujúca
M. Vagaˇc
Paralelné a distribuované výpoˇcty
Porozumenie a dekompozícia problému
Komunikácia a synchronizácia
Granularita, dátová závislost’
I/O, obmedzenia a nároˇcnost’, vyrovnávanie zát’aže
Komunikácia
Synchronizácia
Princíp semafóru (Dijkstra)
Poˇcítadlo (celé kladné cˇ íslo)
Je možné vykonávat’ len operácie cˇ akania (P, wait,
dekrementácia) a signálu (V, signal, post, inkrementácia)
Operácia cˇ akania (P, wait, dekrementácia)
Ak je hodnota 0, vlákno je uspaté a nebude pokraˇcovat’
Ak je hodnota väˇcšia ako 0, tak je hodnota dekrementovaná
Operácia signálu (V, signal, post, inkrementácia)
Ak sú nejaké vlákna (na tomto semafóre) uspaté, jedno z nich je
prebudené
V opaˇcnom prípade zvýš hodnotu o 1
Binárny semafór – len hodnoty 1 a 0 (najbežnejší typ)
Šˇcítací (alebo všeobecný) semafór – väˇcší rozsah hodnôt
(zriedkavejšie)
M. Vagaˇc
Paralelné a distribuované výpoˇcty
Porozumenie a dekompozícia problému
Komunikácia a synchronizácia
Granularita, dátová závislost’
I/O, obmedzenia a nároˇcnost’, vyrovnávanie zát’aže
Komunikácia
Synchronizácia
Operácie synchrónnej komunikácie
Týka sa len úloh vykonávajúcich operácie súvisiacu s
komunikáciou
Potreba koordinácie komunikujúcich úloh (napr. aby mohla úloha
vykonat’ operáciu poslania dát, musí dostat’ potvrdenie, že je ok
posielat’ dáta)
M. Vagaˇc
Paralelné a distribuované výpoˇcty
Porozumenie a dekompozícia problému
Komunikácia a synchronizácia
Granularita, dátová závislost’
I/O, obmedzenia a nároˇcnost’, vyrovnávanie zát’aže
Granularita
Dátová závislost’
Granularita (Zrnitost’)
Pomer vel’kosti výpoˇctu a komunikácie
Doby výpoˇctu sú zvyˇcajne oddelené od doby komunikácie
pomocou synchronizaˇcných udalostí
Klasifikácia podl’a množstva komunikácie medzi úlohami:
Jemnozrnný (Fine-grain) paralelizmus
Hrubozrnný (Coarse-grain) paralelizmus
Výber závisí od konkrétneho algoritmu a hardvérového prostredia
M. Vagaˇc
Paralelné a distribuované výpoˇcty
Porozumenie a dekompozícia problému
Komunikácia a synchronizácia
Granularita, dátová závislost’
I/O, obmedzenia a nároˇcnost’, vyrovnávanie zát’aže
Granularita
Dátová závislost’
Jemnozrnný paralelizmus
Medzi jednotlivými komunikáciami sa vykoná relatívne málo
výpoˇctov
Malý pomer výpoˇctu ku komunikácii
Pomáha použitie vyrovnávania zát’aže
Nadbytoˇcnost’ komunikácie a málo možností na zlepšenie výkonu
Ak je granularita príliš jemnozrnná, je možné že nadbytoˇcnost’
komunikácie a synchronizácie úloh trvá dlhšie ako samotný
výpoˇcet
M. Vagaˇc
Paralelné a distribuované výpoˇcty
Porozumenie a dekompozícia problému
Komunikácia a synchronizácia
Granularita, dátová závislost’
I/O, obmedzenia a nároˇcnost’, vyrovnávanie zát’aže
Granularita
Dátová závislost’
Hrubozrnný paralelizmus
Medzi jednotlivými komunikáciami sa vykoná relatívne vel’a
výpoˇctov
Vel’ký pomer výpoˇctu ku komunikácii
Viac možností na zlepšenie výkonu
ˇ
Tažšie
efektívne použit’ vyrovnávanie zát’aže
M. Vagaˇc
Paralelné a distribuované výpoˇcty
Porozumenie a dekompozícia problému
Komunikácia a synchronizácia
Granularita, dátová závislost’
I/O, obmedzenia a nároˇcnost’, vyrovnávanie zát’aže
Granularita
Dátová závislost’
Dátová závislost’
Medzi príkazmi programu existuje závislost’, ak poradie
vykonania príkazov ovplyvní výsledok programu
Ak rôzne úlohy pracujú s tým istým miestom dát, hovoríme o
dátovej závislosti
Obzvlášt’ dôležité sú dátové závislosti v cykle (cykly sú
najbežnejším ciel’om paralelizácie)
Ako sa postarat’ o dátové závislosti
Pri použití distribuovanej pamäti – na synchronizaˇcných miestach
posielat’ dotknuté dáta
Pri použití zdiel’anej pamäti – synchronizovat’ read/write operácie
medzi jednotlivými úlohami
M. Vagaˇc
Paralelné a distribuované výpoˇcty
Porozumenie a dekompozícia problému
Komunikácia a synchronizácia
Granularita, dátová závislost’
I/O, obmedzenia a nároˇcnost’, vyrovnávanie zát’aže
Granularita
Dátová závislost’
Dátová závislost’
Príklad dátovej závislosti v cykle:
Závislost’ medzi príkazmi v rôznych iteráciách
Na výpoˇcet hodnoty a[i ] je potrebná hodnota a[i − 1]; dátová
závislost’ a[i ] od a[i − 1]
ˇ ak úloha 1 vypoˇcítala a[i − 1] a úloha 2 poˇcíta a[i ]?
Co
(zdiel’aná/distrubuovaná pamät’)
for (i=start;i<end;i++)
a[i] = a[i-1] * 2;
Príklad dátovej závislosti nezávislej od cyklu:
Závislost’ medzi príkazmi v tej istej iterácii
Hodnota y závisí od toho, cˇ i bolo x prenesené medzi úlohami
(distribuovaná pamät’), alebo od toho ktorá úloha posledná
zapísala x (zdiel’aná pamät’)
x=2; .. y = 2*x;
x=4; .. y = 3*x;
M. Vagaˇc
// uloha1
// uloha2
Paralelné a distribuované výpoˇcty
Porozumenie a dekompozícia problému
Komunikácia a synchronizácia
Granularita, dátová závislost’
I/O, obmedzenia a nároˇcnost’, vyrovnávanie zát’aže
I/O
Obmedzenia a nároˇcnost’ paralelného spracovania
Vyrovnávanie zát’aže
I/O
Problémy vstupov/výstupov
I/O operácie sa vo všeobecnosti v parallelizme považujú za
spomal’ovaˇce
V prostredí zdiel’ania súborového systému medz úlohami môže
nastat’ vzájomné prepisovanie súborov
Odporúˇcania
Obmedzit’ použitie I/O operácií
Zvážit’ možnost’ použitia paralelného súborového systému (GPFS,
Lustre, PVFS/PVFS2, PanFS, HP SFS)
Uprednostnit’ zápisu viac dát naraz pred viacnásobným zápisom
kúskov dát
Obmedzit’ I/O na jednu úlohu a potom použit’ paralelnú
komunikáciu na distribuovanie dát ostatným úlohám (napr. 1.
úloha naˇcíta dáta, rozpošle paralelným úlohám, nakoniec zozbiera
výsledky a len ona ich zapíše)
Podl’a možnosti používat’ lokálny súborový systém
M. Vagaˇc
Paralelné a distribuované výpoˇcty
Porozumenie a dekompozícia problému
Komunikácia a synchronizácia
Granularita, dátová závislost’
I/O, obmedzenia a nároˇcnost’, vyrovnávanie zát’aže
I/O
Obmedzenia a nároˇcnost’ paralelného spracovania
Vyrovnávanie zát’aže
Amdahlov zákon
Možné zrýchlenie programu je dané množstvom kódu (P), ktorý
je možné paralelizovat’:
zrychlenie = 1−1 P
Ak nie je možné paralelizovat’ žiadny kód: P = 0, zrychlenie = 1
Ak je možné paralelizovat’ celý kód: P = 1, zrychlenie = ∞
Ak je možné paralelizovat’ 50% kódu, tak P = 0.5, zrychlenie = 2
(nový kód pobeží 2x rýchlejšie)
M. Vagaˇc
Paralelné a distribuované výpoˇcty
Porozumenie a dekompozícia problému
Komunikácia a synchronizácia
Granularita, dátová závislost’
I/O, obmedzenia a nároˇcnost’, vyrovnávanie zát’aže
I/O
Obmedzenia a nároˇcnost’ paralelného spracovania
Vyrovnávanie zát’aže
Amdahlov zákon
Použitím N procesorov (P - paralelná cˇ ast’, S - sériová cˇ ast’):
1
zrychlenie = P +
S
N
Je zrejmé, že škálovatel’nost’ paralelizmu má obmedzenia
Niektoré problémy však rastúcou vel’kost’ou vykazujú väˇcší výkon
(problémy, pri ktorých s rastúcou vel’kost’ou rastie cˇ as
paralelného vykonávania sú škálovatel’nejšie)
N
10
100
1000
10000
100000
P=0.5
1.82
1.98
1.99
1.99
1.99
P=0.9
5.26
9.17
9.91
9.91
9.99
P=0.99
9.17
50.25
90.99
99.02
99.90
M. Vagaˇc
Paralelné a distribuované výpoˇcty
Porozumenie a dekompozícia problému
Komunikácia a synchronizácia
Granularita, dátová závislost’
I/O, obmedzenia a nároˇcnost’, vyrovnávanie zát’aže
I/O
Obmedzenia a nároˇcnost’ paralelného spracovania
Vyrovnávanie zát’aže
Zložitost’
Vo všeobecnosti sú paralelné aplikácie zložitejšie (viac inštrukcií
vykonávaných súˇcasne, prenos dát medzi nimi)
Zložitost’ sa prejaví z pohl’adu programátora prakticky v celom
vývojovom cykle:
Návrh
Implementácia
Hl’adanie chýb
Optimalizácia
Správa
Dodržiavat’ správne zásady vývoja softvéru je kl’úˇcové
M. Vagaˇc
Paralelné a distribuované výpoˇcty
Porozumenie a dekompozícia problému
Komunikácia a synchronizácia
Granularita, dátová závislost’
I/O, obmedzenia a nároˇcnost’, vyrovnávanie zát’aže
I/O
Obmedzenia a nároˇcnost’ paralelného spracovania
Vyrovnávanie zát’aže
Prenositel’nost’
Vd’aka štandardizovanému API (MPI, Posix Threads, OpenMP)
nie je prenositel’nost’ až tak problematická
Všetky problémy s prenositel’nost’ou sériových programov sa
však týkajú aj paralelného programovania
Rôzne implementácie štandardov sa líšia v mnohých detailoch
Operaˇcné systémy predstavujú kl’úˇcovú otázku pri prenositel’nosti
Hardvérové architektúry majú rôzne vlastnosti a môžu mat’ vplyv
na prenositel’nost’
M. Vagaˇc
Paralelné a distribuované výpoˇcty
Porozumenie a dekompozícia problému
Komunikácia a synchronizácia
Granularita, dátová závislost’
I/O, obmedzenia a nároˇcnost’, vyrovnávanie zát’aže
I/O
Obmedzenia a nároˇcnost’ paralelného spracovania
Vyrovnávanie zát’aže
Požiadavky na zdroje
Väˇcšie požiadavky na zdroje (aby sa daná úloha vykonala v
kratšom cˇ ase, je potrebných viac výpoˇctových zdrojov)
Pamät’ová nároˇcnost’ môže byt’ vyššia (podporné knižnice,
subsystémy)
Krátko trvajúce paralelné programy môžu byt’ v koneˇcnom
dôsledko neefektívnejšie ako sériové (cena spustenia
paralelného prostredia, vytvorenia úloh, atd’.)
M. Vagaˇc
Paralelné a distribuované výpoˇcty
Porozumenie a dekompozícia problému
Komunikácia a synchronizácia
Granularita, dátová závislost’
I/O, obmedzenia a nároˇcnost’, vyrovnávanie zát’aže
I/O
Obmedzenia a nároˇcnost’ paralelného spracovania
Vyrovnávanie zát’aže
Škálovatel’nost’
Zvyšovanie výkonu paralelného programu je výsledkom mnohých
nezávislých faktorov (samotné pridávanie výpoˇctových uzlov
cˇ asto nestaˇcí)
Algoritmy môžu obsahovat’ prirodzené obmedzenia na
škálovatel’nost’ (pridávanie výpoˇctových uzlov v urˇcitom okamihu
spôsobí zníženie výkonu)
Podstatný faktor predstavuje hardvér:
Šírka pásma pamät’ – procesor
Šírka pásma komunikaˇcnej siete
Vel’kost’ dostupnej pamäte na výpoˇctovom uzle
Rýchlost’ procesora
Pomocné knižnice a subsystémy môžu obmedzit’ škálovatel’nost’
M. Vagaˇc
Paralelné a distribuované výpoˇcty
Porozumenie a dekompozícia problému
Komunikácia a synchronizácia
Granularita, dátová závislost’
I/O, obmedzenia a nároˇcnost’, vyrovnávanie zát’aže
I/O
Obmedzenia a nároˇcnost’ paralelného spracovania
Vyrovnávanie zát’aže
Vyrovnávanie zát’aže
Vyrovnávanie zát’aže (Load Balancing)
Rozdel’ovanie práce takým spôsobom, aby boli všetky úlohy
vyt’ažené v každom cˇ ase
Minimalizácia cˇ asu neˇcinnosti (Idle time)
Dôležitost’ vyrovnávania zát’aže (napr. pri bariérovej
synchronizácii budú všetky úlohy cˇ akat’ na tú najpomalšiu)
M. Vagaˇc
Paralelné a distribuované výpoˇcty
Porozumenie a dekompozícia problému
Komunikácia a synchronizácia
Granularita, dátová závislost’
I/O, obmedzenia a nároˇcnost’, vyrovnávanie zát’aže
I/O
Obmedzenia a nároˇcnost’ paralelného spracovania
Vyrovnávanie zát’aže
Docielenie vyrovnanej zát’aže
Rovnomerné rozdelenie práce všetkým úlohám
Prácia s poliami/maticami – ak každá úloha robí podobnú cˇ inost’,
rovnomerne rozdelit’ dáta úlohám
Cykly – ak je práca vykonaná v každej iterácii podobná,
rovnomerne rozdelit’ iterácie medzi úlohy
V heterogénnom prostredí (rôzne hardvérové konfigurácie)
mysliet’ na to, že rovnako nároˇcnú úlohu budú rôzne konfigurácie
vykonávat’ rôzne dlhý cˇ as
Dynamické pridel’ovanie práce
Niektoré triedy problémov vedú aj po rovnomernom rozdelení dát
k nevyrovnanej zát’aži (napr. pri práci s pol’om – niektoré úlohy
budú mat’ cˇ ast’ pol’a s hodnotami, iné so samými 0)
Plánovaˇc so zásobníkom úloh – ked’ je nemožné predvídat’
množstvo práce pre každú úlohu (alebo sa mení)
Možná potreba návrhu algoritmu dynamicky reagujúceho na
nerovnomernost’ zát’aže priamo v kóde
M. Vagaˇc
Paralelné a distribuované výpoˇcty
Download

Paralelné a distribuované výpocty