IB109 Návrh a implementace paralelních systémů
Analytický model paralelních programů
Jiří Barnat
Analytický model paralelních programů
Vyhodnocování sekvenčních algoritmů
• Časová a prostorová složitost
• Funkce velikosti vstupu
Vyhodnocování paralelních algoritmů
• Paralelní systém = algoritmus + platforma
• Složitost
o Přínos paralelismu
• Přenositelnost
• . ..
V této kapitole
• Jak posuzovat výkon paralelních algoritmů a systémů
IB109 Návrh a implementace paralelních systémů: Analytický model paralelních programů
str. 2/35
Režie (overhead) paralelních programů
IB109 Návrh a implementace paralelních systémů: Analytický model paralelních programů
str. 3/35
Režie (overhead) paralelních programů
N-násobné zrychlení
• S použitím r?-násobných HW zdrojů, lze očekávat r?-násobné zrychlení výpočtu.
• Nastává zřídka z důvodů režií paralelního řešení.
• Pokud nastane, je jeho důvodem často neoptimální řešení sekvenčního algoritmu.
Důvody
• Režie - interakce, prostoje, složitost paralelního algoritmu Nerovnoměrné zvyšování HW zdrojů
Zvýšení počtu procesorů nepomůže, pokud aplikace není závislá na čistém výpočetním výkonu
IB109 Návrh a implementace paralelních systémů: Analytický model paralelních programů
str. 4/35
Režie (overhead) paralelních programů
Komunikace
• Cena samotné komunikace.
• Příprava dat k odeslání, zpracování přijatých dat.
Prostoje (Lelkování, Idling)
• Nerovnoměrná zátěž na jednotlivá výpočetní jádra. 9 Čekání na zdroje či data.
• Nutnost synchronizace asynchronních výpočtů.
Větší výpočetní složitost paralelního algoritmu
• Sekvenční algoritmus nejde paralelizovat (DFS postorder).
• Typicky existuje vícero paralelních algoritmů, je nutné charakterizovat, čím se platí za paralelismus.
IB109 Návrh a implementace paralelních systémů: Analytický model paralelních programů
str. 5/35
Metriky výkonosti
IB109 Návrh a implementace paralelních systémů: Analytický model paralelních programů
str. 6/35
Otázky
• Jak měřit výkon/kvalitu paralelního algoritmu?
• Podle čeho určit nejlepší/nejvhodnější algoritmus pro danou platformu?
Čas výpočtu - sekvenční algoritmus
• Doba, která uplyne od spuštění výpočtu do jeho ukončení, o T s
Čas výpočtu - paralelní algoritmus
• Doba, která uplyne od spuštění výpočtu do doby, kdy skončí poslední z paralelních výpočtů.
• Zahrnuje distribuci vstupních i sběr výstupních dat.
• T p
IB109 Návrh a implementace paralelních systémů: Analytický model paralelních programů
Celková režie paralelismu (Total overhead)
Celková režie:
• Označujeme Tq
9 Veškeré elementy způsobující režii paralelního řešení.
9 Celkový čas paralelního výpočtu bez času potřebného pro výpočet problému optimálním sekvenčním řešením.
• Paralelní a sekvenční algoritmy mohou být zcela odlišné.
• Sekvenčních algoritmů může existovat víc.
• 7~s čas výpočtu nejlepšího sekvenčního algoritmu (řešení).
Funkce celkové režie
• Jaký je čas výpočtu jednotlivých procesů?
9 Doba od skončení výpočtu jednoho procesu do skončení celého paralelního výpočtu se považuje za režii (idling).
• T0 = pTP - Ts
IB109 Návrh a implementace paralelních systémů: Analytický model paralelních programů
str. 8/35
Zrychlení (Speed-up)
Základní přínos paralelizace
o Problémy jdou vždy řešit sekvenčním algoritmem.
• Paralelizací lze dosáhnout pouze zrychlení výpočtu.
• Ostatní výhody jsou diskutabilní a těžko měřitelné.
Základní míra účinnosti samotné paralelizace
• Poměr časů potřebných k vyřešení úlohy na jedné procesní jednotce a p procesních jednotkách.
o Uvažuje se vždy čas nejlepšího sekvenční algoritmu.
• V praxi se často (a nesprávně) používá čas potřebný
k vyřešení úlohy paralelním algoritmem spuštěném na jedné procesní jednotce.
IB109 Návrh a implementace paralelních systémů: Analytický model paralelních programů
str. 9/35
Teoretická hranice zrychlení
o S použitím p procesních jednotek je maximální zrychlení p.
Super-lineární zrychlení
• Jev, kdy zrychlení je větší jak p.
Pozorování
o Zrychlení lze měřit i asymptoticky.
Příklad - sčítání n čísel s použitím n procesních jednotek.
• Sekvenčně je potřeba 0(r?) operací, čas 0(r?)
• Paralelně je potřeba 0(r?) operací, ale v čase Q(log n)
• Zrychlení S = 0(^)
IB109 Návrh a implementace paralelních systémů: Analytický model paralelních programů
str. 10/35
Super-lineárnř zrychlení
Falešné super-lineární zrychlení
• Uvažme datovou distribuci na 2 procesní jednotky, a operaci kvadratickou ve velikosti dat.
2
• Zrychlení S = -Ay^ — 4 pri použití 2 procesních jednotek.
V 2 )
• Problém - neuvažován optimální sekvenční algoritmus.
Skutečné super-lineární zrychlení
o Větší agregovaná velikost cache pamětí.
• Při snížení množství dat na jeden procesní uzel se účinnost cache pamětí zvýší.
• Výpočet je na ^ datech víc jak p-krát rychlejší.
Super-lineární zrychlení v závislosti na instanci problému
• Průzkumová dekompozice úlohy při hledání řešení. Paralelní verze může vykonat menší množství práce.
• V konkrétní instanci lze paralelní prohledávání simulovat i sekvenčním algoritmem, obecně ale nelze.
IB109 Návrh a implementace paralelních systémů: Analytický model paralelních programů str. 11/35
Amdahlův zákon
Otázka
• Jaké je největší možné zrychlení systému, pokud se paralelizací urychlí pouze část výpočtu?
Amdahlův zákon
(1-P)+
sP
9 P - podíl systému, který je urychlen paralelizací
• Sp - zrychlení dosažené paralelizací nad daným podílem
Příklad
• Paralelizací lze urychlit 4-násobně 30% kódu, tj. P = 0.3 a SP = 4.
• Maximální celkové zrychlení Smax je
1 1 1
5     =_=_=_= 1 29
max    (i_0.3) + ^3     0.7 + 0.075 0.775
IB109 Návrh a implementace paralelních systémů: Analytický model paralelních programů
str. 12/35
Fakta
• Pouze ideální paralelní systém s p procesními jednotkami může dosahovat zrychlení p.
• Část výpočtu prováděná na jednom procesoru je spotřebována režií. Procesor nevěnuje 100% výkonu řešení problému.
Efektivita
• Lze definovat jako podíl zrychlení S vůči počtu jednotek p.
_ S _ Ts/Tp Ts
•E=^= - T
P P PTP
9 Zrychlení je v praxi < p, efektivita v rozmezí (0,1 o " Podíl času, po který jednotka vykonává užitečný kód."
IB109 Návrh a implementace paralelních systémů: Analytický model paralelních programů
str. 13/35
Efektivita - příklady
Příklad 1
• Jaká je efektivita sčítání n čísel na n procesorech? •5 = 6(4^)
• E = 0(f) = 0(7^)
Příklad 2
• Na kolik se zkrátí 100 vteřinový výpočet při použití 12 procesorů při 60% efektivitě?
• E =
o 0.6 =
100
12x
X =
100 0.6*12
» x = 13.88
IB109 Návrh a implementace paralelních systémů: Analytický model paralelních programů
str. 14/35
Cena
Cena řešení problému na daném paralelním systému
• Součin počtu procesních jednotek a doby paralelního výpočtu: C = p x T p
• Označována také jako "množství práce", které paralelní systém vykoná, nebo jako "pTp produkt".
9 Alternativně lze použít pro výpočet účinnosti (E = ^-).
Cenově optimální paralelní systém
o Cena sekvenčního výpočtu odpovídá nejlepšímu T5.
o Paralelní systém je cenově optimální, pokud cena řešení roste asymptoticky stejně rychle jako cena sekvenčního výpočtu.
• Cenově optimální systém musí mít efektivitu rovnou 0(1). Příklad
• Sčítání n čísel na n procesorech
• C = Q(nlog n), není cenově optimální
IB109 Návrh a implementace paralelních systémů: Analytický model paralelních programů str. 15/35
Cena - příklad
• Uvažme n procesorový systém, který třídí (řadí) seznam n čísel v čase (log n)2
9 Nejlepší sekvenční algoritmus má 7~s = nlog n
• S = —— E =
log n ' log n
% C — n(log n)2
9 Není cenově optimální, ale pouze o faktor log n
9 Uvažme, že v praxi p << n (p je mnohem menší než n)
• TP = n(log n)2/p a tedy S = ^
• Konkrétně: n = 210, log n = 10 a p = 32     S = 3.2
• Konkrétně: n = 220, /o# n = 20 a p = 32     S = 1.6
• Závěr: cenová optimalita je nutná
IB109 Návrh a implementace paralelních systémů: Analytický model paralelních programů
str. 16/35
Vliv granularity na cenovou optimalitu
IB109 Návrh a implementace paralelních systémů: Analytický model paralelních programů
str. 17/35
Vliv granularity na cenovou optimalitu
Tvrzení
• Volbou granularity lze ovlivnit cenu paralelního řešení. Pozorování
• V praxi p << n, přesto navrhujeme algoritmy tak, aby granularita byla až na úrovni jednotlivých položek vstupu, tj. předpokládáme p — n.
Deškálování (scale-down)
• Uměle snižujeme granularitu (vytváříme hrubší úlohy). 9 Snižujeme overhead spojený s komunikací.
• Může ovlivnit cenu a cenovou optimalitu.
IB109 Návrh a implementace paralelních systémů: Analytický model paralelních programů
str. 18/35
Vliv granularity na cenovou optimalitu
Příklad 1)
• Sčítání n čísel na p procesorech (r? = 16, p = 4)
• Mapování (/ modp), tj. (r?/p) čísel na 1 procesor.
• Simulace prvních logp kroků stojí {n/p)logp operací, tj. proběhne v čase Q((n/p)log p).
Následně simulace původního algoritmu probíhá lokálně v paměti jednoho procesoru, tj. v čase 0(r?/p).
• Celkový Tp je Q{{n/p)log p)
9 Cena C = Q(nlogp), tj. není cenově optimální o Původní Tp bylo Q(log n), změna o faktor ^(^-^)
IB109 Návrh a implementace paralelních systémů: Analytický model paralelních programů
str. 19/35
Vliv granularity na cenovou optimalitu
Příklad 2)
9 Sčítání n čísel na p procesorech (r? = 16, p = 4)
o Necht n a p jsou mocniny dvojky (r? a p jsou soudělné)
• Mapování (/ mod p)
o Každá jednotka nejprve sečte data lokálně v čase 0(r?/p)
• Problém redukován na sčítání p čísel na p procesorech o Celkový Tp je 0(r?/p + /og" p)
• Cena C = 0(r? + plogp),
• Cenově optimální, pokud n > p log p (cena C = 0(r?))
IB109 Návrh a implementace paralelních systémů: Analytický model paralelních programů
str. 20/35
Škálovatelnost paralelních programů
IB109 Návrh a implementace paralelních systémů: Analytický model paralelních programů
str. 21/35
Škálovatelnost paralelních programů
Fakta
9 Programy jsou testovány na malých vstupních datech na systémech s malým počtem procesních jednotek.
• Použití deškálování zkresluje měření výkonu aplikace.
• Algoritmus, který vykazuje nejlepší výkon na testovaných datech, se může ukázat být tím nejhorším algoritmem, při použití na skutečných datech.
Odhad výkonu aplikace nad reálnými vstupními daty a větším počtu procesních jednotek je komplikovaný.
Škálovatelnost
9 Zachování výkonu a efektivity při zvyšování počtu procesních jednotek a zvětšování objemu vstupních dat.
Závěr
• Je třeba uvážit analytické techniky pro vyhodnocování výkonu a škálová ní.
IB109 Návrh a implementace paralelních systémů: Analytický model paralelních programů str. 22/35
Charakteristiky škálovánŕ- Efektivita
Efektivita paralelních programů:
E = S = T s = 1 P     pTP     1 + Ij
Celková režie (To)
• Přítomnost sekvenční části kóduje nevyhnutelná. Pro její vykonání je třeba čas ŕser/a/. Po tuto dobu jsou ostatní procesní jednotky nevyužité.
• To > (P - l)tser/a/
• Tq roste minimálně lineárně vzhledem k p, často však i asymptoticky více.
Úloha konstantní velikosti (7~s fixní)
• Se zvyšujícím se p, efektivita nevyhnutelně klesá.
9 Nevyhnutelný úděl všech paralelních programů.
IB109 Návrh a implementace paralelních systémů: Analytický model paralelních programů str. 23/35
Charakteristiky škálovánŕ- Příklad
Problém
• Ukol: Sečíst n čísel s využitím p procesních jednotek, o Uvažme cenově optimální verzi algoritmu.
. Tp = (i + logp).
• Lokální operace stojí 1, komunikace 2 jednotky času.
Charakteristiky řešení
• TP = %+2logp
• E =
^ I 2plog p n
IB109 Návrh a implementace paralelních systémů: Analytický model paralelních programů
str. 24/35
Při zachování T$
o Rostoucí počet procesních jednotek snižuje efektivitu.
Při zachování počtu procesních jednotek
• Rostoucí 7~s (velikost vstupních dat) má tendenci zvyšovat efektivitu.
Škálovatelné systémy
• Efektivitu lze zachovat při souběžném zvyšování 7~s a p.
• Zajímáme se o poměr, ve kterém se Í5 a p musí zvyšovat, aby se zachovala efektivita.
• Lim menši pomer
IB109 Návrh a implementace paralelních systémů: Analytický model paralelních programů
str. 25/35
Izoefektivita jako metrika škálování
Vztahy
• T p
• S =
• E =
= Ts+T0(W,p)
p
T$ _ pT$
TP - Ts+T0(W,p)
S = TS P
W - velikost vstupních dat
TS+T0(W,P) - l+T0(W,p)/Ts
Konstantní efektivita
• Efektivita je konstantní, pouze pokud To{W,p)/7~s je konstantní.
• Úpravou vztahu pro efektivitu: T s — jz^To{W, p).
• Při zachování míry efektivity lze E/(l — E) označit jako konstantu K.
Funkce izoefektivity (stejné efektivity)
Ts = KT0(W,p)
IB109 Návrh a implementace paralelních systémů: Analytický model paralelních programů
str. 26/35
Izoefektivita jako metrika škálování
Funkce izoefektivity
Ts = KT0(W,p)
Pozorování
9 Při konstantní efektivitě, lze 7~s vyjádřit jako funkci p 9 Vyjadřuje vztah, jak se musí zvýšit T§ při zvýšení p
• Nižší funkce říká, že systém je snáze škálovatelný
• Isoefektivitu nelze měřit u systémů, které neškálují
IB109 Návrh a implementace paralelních systémů: Analytický model paralelních programů
str. 27/35
Izoefektivita jako metrika škálování- příklad
Příklad
• Součet n čísel na p procesorech
• E =
l+(2plogp)/n l+T0(W,p)/Ts
• T0 = 2p log p
• Funkce izoefektivity: T$ = K2p log p
• Funkce izoefektivity: 0(p log p)
Při zvýšení procesních jednotek z p na p' se pro zachování efektivity musí zvětšit velikost problému o faktor (p' log p')/(plog p).
IB109 Návrh a implementace paralelních systémů: Analytický model paralelních programů
str. 28/35
Cenová optimalita a izoefektivita
Optimálni cena
• Pro cenově optimální systémy požadujeme pTp — 0(7"s).
• Po dosazení ze základních izo vztahů dostáváme: TS + T0(W, p) = G{TS)
Cenová optimalita může být zachována pouze pokud:
• režie je nejvýše lineární vůči složitosti sekvenčního algoritmu, tj. funkce T0{W,p) G 0{TS)
o složitost sekvenčního algoritmu je minimálně tak velká jako režie, tj. funkce 7~s G Q(Tq( w, p))
IB109 Návrh a implementace paralelních systémů: Analytický model paralelních programů
str. 29/35
Spodní odhad na izoefektivitu
Izoefektivita
• Čím nižší/menší funkce, tím lepší škálovatelnost.
• Snaha o minimálni hodnotu izofunkce.
Sublineární izoefektivita
• Pro problém tvořený N jednotkami práce je optimálni cena dosažitelná pouze pro maximálně N procesních jednotek.
o Přidáváním dalších jednotek vyústí v idling některých jednotek a snižování efektivity.
• Aby se efektivita nesnižovala musí množství práce růst minimálně lineárně vzhledem k p.
Funkce izoefektivity nemůže být sublineární.
IB109 Návrh a implementace paralelních systémů: Analytický model paralelních programů
str. 30/35
Minimální doba výpočtu
Otázka
• Jaká je minimální možná doba výpočtu (Tpm) při dostupnosti dostatečného počtu procesních jednotek?
Pozorování
mm
• Při rostoucím p se Tp asymptoticky blíží k T p
• Po dosažení Tpm se Tp zvětšuje spolu s p.
Jak zjistit 7™"?
9 Necht po je kořenem diferenciální rovnice
• Dosazení po do vztahu pro Tp dává hodnotu Tp
mm
ap+2logP,
dTP
Příklad - součet n čísel p procesními jednotkami
• T p
• Po =
dp
n 2
Tpm = 2logn = Q(logn)
IB109 Návrh a implementace paralelních systémů: Analytický model paralelních programů
str. 31/35
Asymptotická analýza paralelních programů
Algoritmus	AI	A2	A3	A4
P	n2	log n	n	\fň
TP	1	n	y/ň	y/ňlog n
S	n log n	log n	y/ňlog n	y/ň
E	log n n	1	log n	1
pTP	n2	n log n	„1.5	n log n
Otázky
• Jaký algoritmus je nejlepší?
• Použily jsme vhodné odhady složitosti?
• Je dostupná odpovídající paralelní architektura?
IB109 Návrh a implementace paralelních systémů: Analytický model paralelních programů
str. 32/35
Závě
Návrh paralelních algoritmů ač složitostně neoptimálních je nedílnou a důležitou částí práce programátora paralelních aplikací.
IB109 Návrh a implementace paralelních systémů: Analytický model paralelních programů
str. 33/35
Shrnutí
IB109 Návrh a implementace paralelních systémů: Analytický model paralelních programů
str. 34/35
Co jsme se v kurzu dozvěděli
Paralelní HW platformy
9 Principy fungování HW systémů se sdílenou pamětí.
• Komunikace v systémech s distribuovanou pamětí.
Nástroje paralelního programování
• Standardy a knihovny pro implementaci paralelních aplikací.
POSIX Threads, OpenMP, MPI (OpenMPI)
• Principy fungování těchto knihoven
Lock-Free datové struktury, Kolektivní komunikace
Algoritmizace
• Principy návrhu paralelních algoritmů.
• Analytické posuzování paralelních řešení.
IB109 Návrh a implementace paralelních systémů: Analytický model paralelních programů
str. 35/35