1/19
Vzory v paralelismu
Obecnější aplikované úvahy o paralelizaci
část II
Petr Holub
hopet@ics.muni.cz
Laboratoř pokročilých síťových technologií
PV197
2009­12­14
2/19
Vzory v paralelismu
Volba vzorů
3/19
Vzory v paralelismu
Paralelismus úloh
Dekompozice podle úloh
potřeba vygenerovat dostatečné množství úloh
Řešení závislostí:
odstranitelné závislosti
1 int ii=0, jj=0;
3 for (int i=0; i<N; i++) {
ii = ii+1;
5 d[ii] = dlouhy_vypocet(ii);
jj = jj+i;
7 a[jj] = jiny_dlouhy_vypocet(jj);
}
1 for (int i=0; i<N; i++) {
d[i] = dlouhy_vypocet(i);
3 a[i*(i+1)/2] = jiny_dlouhy_vypocet(i*(i+1)/2);
}
rozdělitelné závislosti: lokální výpočet + redukce
jiné typy závislostí: řešení sdílením dat
4/19
Vzory v paralelismu
Paralelismus úloh
Plánování úloh:
statické: vygenerování úloh na počátku (např. paralelizace smyček
předem dané velikosti)
dynamické
dynamické generování úloh do centrální fornty
work stealing
Idiomatické typy:
embarrassingly parallel tasks
úlohy nad replikovanými daty (1. vykopírování dat do lokálních
proměnných, 2. výpočet, 3. seskládání výsledků)
Příklady:
zpracování obrazu: pokud je zpracování pro oblasti nezávislé na okolí
raytracing, PET: dekompozice na jednotlivé paprsky
molekulová dynamika: dekompozice na jednotlivé atomy při výpočtu
příspěvků sil; dvouelektronové integrály u kvantových metod
5/19
Vzory v paralelismu
Rozděl a panuj
Klasický přístup pro rekurzivní úlohy
Problém se sekvenční režií dělení na podúlohy
S(P) =
Ttot(1)
Ttot(P)
=
1
 + 1-
P
kde  = Tserial
Ttot(1)
.
20.00
18.00
16.00
14.00
12.00
10.00
8.00
6.00
4.00
2.00
0.00
Speedup
1
2
4
8
16
32
64
128
256
512
1024
2048
4096
8192
16384
32768
65536
Number of Processors
Amdahl's Law
Parallel Portion
50%
75%
90%
95%
Zdroj: http://en.wikipedia.org/wiki/File:AmdahlsLaw.svg
Příklady: mergesort, diagonalizace matic (hledání vlastního vektoru a
vlastních hodnot ­ hledání matice Q takové že QT
 T  Q je
diagonální), rychlá multipólová metoda (FMM)
6/19
Vzory v paralelismu
Geometrická dekompozice
Hledání geometrického dělení zpracovávaných dat
data dělitelná na velké množství nezávislých segmentů
řešení hranic mezi segmenty ­ ghost boundary
Příklad ­ vedení tepla:
U
t
= 
2
U
x2
ukp1[i] = uk[i] + (dt/(dx*dx))*(uk[u+1] + uk[u-1] - 2*uk[i]);
7/19
Vzory v paralelismu
Geometrická dekompozice
Příklad ­ násobení matic:
Kroky:
rozklad dat
poměr mezi množstvím vyměňovaných dat a všech dat
dělení matice na 4ks: sloupce (5N 2) vs. čtverce (2N)
výměna dat před novým krokem výpočtu
výpočet na vlastním segmentu
8/19
Vzory v paralelismu
Geometrická dekompozice
Rozložení úloh přes procesory:
minimalizace režie výměn dat
efektivita využití úloh (např. při eliminacích matic mohou procesory
hladovět  cyklické přidělování bloků)
1D dekompozice:
dekompozice přiřazení (j mod 4)
9/19
Vzory v paralelismu
Geometrická dekompozice
2D dekompozice:
dekompozice přiřazení (i mod 2,j mod 2)
10/19
Vzory v paralelismu
Geometrická dekompozice
Maskování latence komunikace ­ překryv komunikace a výpočtu
1. neblokující volání zahajující komunikaci (distribuci ghost boundary)
2. výpočet vnitřních prvků
3. čekání na dokončení komunikace
4. výpočet hodnot okrajových prvků, závisejících na ghost boundary
Příklady pro MPI:
MPI_Isend(), MPI_Irecv()
MPI_Wait()
11/19
Vzory v paralelismu
Rekurzivní pohled na data
Pohled na data, kde nejde přímočaře použít přístup rozděl a panuj z
povahy algoritmu
Příklad: les stromů (každý uzel si drží svého předchůdce, kořen je sám
sobě předchůdcem), hledáme pro každý uzel kořen
sekvenčně: z každého kořene provedeme DFS ­ O(N)
Paralelně:
zavedeme si pro každého předchůdce-předchůdce
výpočet opakujeme až do konvergence
postupujeme na všech N uzlech paralelně
celkově O(N log N), ovšem při paralelním provedení efektivně jen
O(log N)
Zhoršení celkové složitosti je pro tuto dekompozici typické
Potřeba sdílet výsledky po každém kroku (lockstep) (podpora např. v
řadě SIMD strojů a High-Performance Fortranu)
12/19
Vzory v paralelismu
Rekurzivní pohled na data
Kroky:
13/19
Vzory v paralelismu
Rekurzivní pohled na data
Pohled na data, kde nejde přímočaře použít přístup rozděl a panuj z
povahy algoritmu
Příklad: les stromů (každý uzel si drží svého předchůdce, kořen je sám
sobě předchůdcem), hledáme pro každý uzel kořen
sekvenčně: z každého kořene provedeme DFS ­ O(N)
Paralelně:
zavedeme si pro každého předchůdce-předchůdce
výpočet opakujeme až do konvergence
postupujeme na všech N uzlech paralelně
celkově O(N log N), ovšem při paralelním provedení efektivně jen
O(log N)
Zhoršení celkové složitosti je pro tuto dekompozici typické
Potřeba sdílet výsledky po každém kroku (lockstep) (podpora např. v
řadě SIMD strojů a High-Performance Fortranu)
14/19
Vzory v paralelismu
Rekurzivní pohled na data
Součty pre xů
potřebujeme sečíst pro n-tý prvek všech 1 až n předchůdců
opět rekurzivní zdvojování
1 for all k in parallel {
temp[k] = next[k];
3 while(temp[k]) {
x[temp[k]] = x[k] + x[temp[k]];
5 temp[k] = temp[temp[k]];
}
7 }
15/19
Vzory v paralelismu
Rekurzivní pohled na data
Co se děje:
16/19
Vzory v paralelismu
Pipeline
... známe z procesorů
Příklady: obecně pravidelné zpracování
pipeline instrukcí
pipeline na úrovni paralelizace smyček (vektorové stroje)
zpracování signálů sérií ltrů
rozdělení gra ckého zpracování na ,, ltry``
vyjádření závislostí na n předchozích krocích
17/19
Vzory v paralelismu
Pipeline
Efektivita:
počet fází pipeline (škálovatelnost)
rovnoměrnost výpočetní náročnosti fází
plnění a dojíždění pipeline vs. celkový běh
průtok dat vs. latence zpracování
napojování pipeline, resp. vytvoření co nejdelší pipeline
všechny prvky by měly projít pravidelně stejnou sérií zpracování
Reprezentace toku dat
sdílená paměť, soubory ­ uspořádaná fronta pro každou fázi
distribuovaná paměť ­ bu erované zasílání zpráv
v případě vyšší latence přenosu zpráv možno agregovat více požadavků
(prodlužuje naplnění pipeline)
agregace dat, pokud jich každá fáze potřebuje více (dtto)
Chyby ve zpracování
separátní komponenta sbírající informace chybách
18/19
Vzory v paralelismu
Pipeline
Plánování úloh
možnost/nutnost slučování fází: využívání cache, registrů
možnost paralelizace uvnitř fází
možnost více instancí jedné fáze
pokud nevadí přeuspořádání
Příklady:
zpracování dat ve frekvenční doméně ­ DFT
provedení DFT/FFT
aplikace jednotlivých ltrů
inverzní DFT/FFT
např. zpracování telemetrických dat z Hubblova teleskopu, z radarů
AWACS
častá implementace v HW ­ zpracování signálů v reálném čase
zpracování HTTP požadavků ­ ltrování Java Servlety
19/19
Vzory v paralelismu
Událostmi řízená paralelizace
Nepravidelná a asynchronní obdoba pipeline
Nepravidelné rozdělené a zpracování vstupů ­ nevhodné pro
SIMD/SIMT
Problém přeuspořádání událostí
Obecné komunikační schéma s možností deadlocků