Martin Lísal září 2003
PARALELNÍ POČÍTÁNÍ Úvod do MPI
1
1
Co je to paralelní počítání?
Paralelní počítání je počítání na paralelních počítačích či jinak řečeno využití více než jednoho procesoru při výpočtu (viz. obr. 1).
2
Proč potřebujeme paralelní počítače? • Od konce 2. světové války dochází k bouřlivému rozvoji počítačových simulací (computational science). Počítačové simulace řeší problémy, které teoretická věda (theoretical science) nedokáže vyřešit analyticky či problémy, které jsou obtížné nebo nebezpečné pro experimentální vědu (experimental science). Jako příklad uveďme proudění okolo trupu letadla, které teoretická věda dokáže popsat parciálními diferenciálními rovnicemi; ty ale nedokáže analyticky řešit. Dalším příkladem je určení vlastností plazmy. Jelikož plazma existuje při vysokých teplotách, je experimentální měření většiny jejich vlastností obtížné či přímo nemožné. Počítačové simulace vyžadují náročné numerické výpočty, které se v současnosti neobejdou bez nasazení paralelizace. • Vývoj procesorů naráží (či v budoucnu narazí) na svůj materiálový limit t.j. vývoj procesorů nepůjde zvyšovat do nekonečna. (To pull a bigger wagon, it is easier to add more oxen than to grow a gigantic ox.) • Cena nejvýkonějších (advanced) procesorů na trhu obvykle roste rychleji než jejich výkon. (Large oxen are expansive.)
3
Problémy spojené s vývojem paralelního počítání • Hardware: v současné době lze konstruovat paralelní počítače mající společnou (sdílenou) paměť pro maximálně asi 100 procesorů. Trendem je tedy spojení jednoprocesorových či několikaprocesorových počítačů do clusteru pomocí rychlé komunikační sítě tzv. switche. Pozornost v 2
oblasti hardwaru se proto převážně zaměřuje na vývoj switchů, které umožňují rychlost meziprocesorové komunikace srovnatelnou s rychlostí komunikace mezi procesorem a vnitřní pamětí počítače. • Algoritmy: bohužel se ukazuje, že některé algoritmy používané na jednoprocesorových počítačích nelze dobře paralelizovat. To vede k nutnosti vytvářet zcela nové paralelní algoritmy. • Software: existují prostředky pro automatickou paralelizaci jakými jsou např. paralelní kompilátory [High Performance Fortran (HPF) Standard] či paralelní numerické knihovny. Platí (a pravděpodobně dlouho bude platit), že nejlepší paralelizace je ta, kterou si uděláme sami.
4
Kdy se vyplatí paralelizace?
Zrychlení výpočtu paralelizací lze odhadnout pomocí Amdahlova pravidla: P 100 − P + (1) n kde P je část programu, kterou lze paralelizovat a n je počet použitých procesorů. Amdahlovo pravidlo nám říká, kolik procent výpočtového času bude trvat paralelizovaný program oproti stejnému programu spuštěnému na jednoprocesorovém počítači. Uveďme si jednoduchý ilustrativní příklad. Představme si, že máme sečíst 1 000 000 000 prvků vektoru a. Načtení prvků trvá 8% celkového výpočtového času, vlastní výpočet součtu trvá 90% celkového výpočtového času a tisk trvá 2% celkového výpočtového času. Je zřejmé, že jen výpočet součtu lze paralelizovat t.j. P = 90% (viz. obr. 2). V případě použití n = 10 procesorů dostaneme z Amdahlova pravidla výsledek 19% t.j. zrychlení výpočtu paralelizací přibližně 5-krát. Z Amdahlova pravidla a uvedeného příkladu plynou dva závěry: (i) neplatí přímá úměra mezi počtem procesorů a urychlením výpočtu (”užití 10 procesorů neznamená urychlení výpočtu 10-krát”) a (ii) pro limitní případ n → ∞ je urychlení výpočtu konečné a rovno 100/(100 − P ).
3
5
Závisí způsob paralelizace výpočtů na architektuře paralelních počítačů?
Způsob paralelizace výpočtů bohužel závisí na architektuře paralelních počítačů. V současnosti se nejvíce používají dva typy architektur: (i) paralelní počítače se sdílenou pamětí (shared memory) a (ii) paralelní počítače s distribuovanou pamětí (distributed memory); viz. obr. 3. Z hlediska způsobu paralelizace je výhodnější architektura se sdílenou pamětí, neboť sdílení a výměna informací mezi procesory během výpočtu se děje přes sdílenou (společnou) paměť. Paralelizace na ”shared-memory” počítačích se provádí pomocí tzv. OpenMP. OpenMP je seznam direktiv, které se vkládají na místa, které chceme paralelizovat. Jinými slovy říkáme počítači ”kde a co” paralelizovat. Uveďme si jako příklad paralelizaci cyklu (do) pomocí OpenMP: !$OMP PARALLEL DO do i = 2, n b(i) = (a(i) + a(i-1)) / 2.0 end do !$OMP END PARALLEL DO Direktiva před začátek cyklu, !$OMP PARALLEL DO, říká: ”paralelizuj cyklus”, zatímco direktiva na konci cyklu, !$OMP END PARALLEL DO, říká: ”ukonči paralelizaci cyklu”.1 Paralelní počítače se sdílenou pamětí jsou oproti paralelním počítačům s distribuovanou pamětí dražší a počet procesorů sdílející jednu paměť je v současnosti omezen maximálně asi na 100. Proto se běžněji setkáváme s ”distributed-memory” počítači. ”Distributed-memory” počítače mají fyzicky oddělené paměti a komunikace (sdílení dat) mezi procesory zajišťuje switch. Paralelizace na ”distributed-memory” počítačích je obtížnější než paralelizace na ”shared-memory” počítačích, neboť musíme zajistit a pracovat s předáváním informací (message passing) mezi procesory během výpočtu. Na paralelních počítačích s distribuovanou pamětí se používají dva systémy: (i) Parallel Virtual Machine (PVM) vhodný pro heterogenní clustery a (ii) 1
Jelikož direktivy OpenMP začínají ”!” a ten se ve FORTRANu90 interpretuje jako začátek komentářového řádku, lze programy s direktivami OpenMP spouštět bez problému na jednoprocesorových počítačích.
4
Message Passing Interface (MPI) vhodný pro homogenní clustery. PVM a MPI je knihovna příkazů pro FORTRAN, C a C++, jež umožňují předávání informací mezi procesory během výpočtu. Komunikace představuje časovou ztrátu, o kterou se sníží zrychlení výpočtu paralelizací dané Amdahlovým pravidlem. Čas komunikace (overhead) jako funkce množství předávané informace je znázorněn na obr. 4. Z obr. 4 je patrno, že čas komunikace závisí na latenci (času, který potřebuje procesor a switch k ”navázání komunikace”) a dále, že ”overhead” roste s množstvím předávané informace mezi procesory. Z obr. 4 plynou následující zásady, které bychom měli dodržovat při parelelizaci na počítačích s distribuovanou pamětí: (i) přenášet co nejméně informací a (ii) komunikovat co nejméně.
5
Obrázek 1: Schema (a) jednoprocesorového a (b) paralelního počítače typu výpočtový cluster; paměť (memory), procesor (CPU).
Obrázek 2: Schema (a) sériového a (b) paralelního programu (běžícího na 4 procesorech). S1 a S2 jsou částí programu, které nelze paralelizovat a P je paralelizovatelná část programu.
Obrázek 3: Schema paralelního počítače (a) se sdílenou pamětí (shared memory) a (b) s distribuovanou pamětí (distributed memory).
6
Obrázek 4: Čas komunikace (overhead) versus množství předávané informace mezi procesory.
7
Obrázek 1 (M. Lísal, 1. Týden)
(a) Jednoprocesorový počítač
memory
CPU (b) Paralelní počítač typu výpočtový cluster
memory
memory
memory
CPU
CPU
CPU
Obrázek 2 (M. Lísal, 1. Týden)
(a) Sériový program
(b) Paralelní program
a.out S1
S1
P
S2
P
S1
P
S2
S1
P
S2
S1
P
S2
S2
Obrázek 3 (M. Lísal, 1. Týden)
(a) Paralelní počítač se sdílenou pamětí (shared memory)
(b) Paralelní počítač s distribuovanou pamětí (distributed memory)
switch ~ komunikace (shared) memory
CPU CPU
CPU
CPU
memory memory memory memory
CPU
CPU
CPU
CPU
čas komunikace (overhead)
Obrázek 4 (M. Lísal, 1. Týden)
latence
množství přenášené informace
