1. přednáška - Složitost a škálovatelnost paralelních algoritmů
Paralelní počítač
Paralelní počítač je skupina propojených výpočetních prvků (uzlů), které komunikují a
spolupracují, aby rychleji vyřešily velké a náročné výpočetní úloh
Paralelní čas T(n, p)
Čas, který uplynul od začátku paralelního výpočtu až do okamžiku, kdy poslední procesor skončil
výpočet
Sekvenční spodní mez SLK
Teoretická spodní hranice časové komplexity (matematicky dokázaná) algoritmu řešícího K
Sekvenční horní mez SUK
Časová složitost (v nejhorším případě) nejrychlejšího známého algoritmu řešícího K
Paralelní zrychlení S(n, p)
S (n, p) =
SU(n)
T(n, p)
≤p
Spodní mez na paralelní čas L(n,p)
L(n, p) =
SL(n)
p
Paralelní cena
C (n, p) = p * T (n, p)
Paralelní práce W(n,p)
Pro synchronní systém:
Nechť τ = T (n, p) a pi = počet procesorů aktivních v kroku i ∈ {1, ..., τ }paralelního výpočtu. Pak:
W (n, p) = p1 + p2+ ... + pτ Pro asynchronní systém:
Nechť T i ≤ T (n, p) =počet kroků provedených procesorem i ∈ {1, ..., p}během paralelního
výpočtu. Pak:
W (n, p) = T 1 + T 2+ ... + T p Paralelní efektivnost E(n,p)
E (n, p) =
SU(n)
C(n, p)
Izoefektivní funkce ψ1
1
Je­li dána konstanta 0 < E0 < 1, pak izoefektivní funkce ψ1 je taková asymptoticky
minimální funkce, že ∀np = Ω( ψ1(p) ): E(np, p) ≥ E0
Lidsky: Říká nám jak nejmíň musí růst velikost problému s množstvím procesorů, aby byla
zachována efektivita.
Izoefektivní funkce ψ2
Je­li dána konstanta 0 < E0 < 1, pak izoefektivní funkce ψ2 je taková asymptoticky
maximální funkce, že ∀pn =Ο( ψ2(n) ): E(n, pn) ≥ E0
Lidsky: Říká kolik procesorů bude ještě dostatečně efektivních na dané velikosti problému.
Superlineární zrychlení
Situace, při níž je zrychlení výpočtu při přidání více procesorů lepší jak lineární. Dva hlavní
důvody:
● Rozložením stavového prostoru se nějakému procesoru může dostat část prostoru s
řešením hned v prvních krocích algoritmu
● HW charakteristiky paralelního počítače ­ jednomu procesoru by se problém nevešel do
paměti a k výpočtu by se musel přičíst čas swapování, kdežto souhrnná kapacita
paralelního počítače může problém načíst celý
Amdahlův zákon
S (n, p) ≤ fs + 11− f s , kde fs= přirozená sekvenční část
p
Izoefektivní funkce ψ3 ψ3(n) je asymptoticky minimální funkce taková, že:
∀ p = Ω( ψ3(n) ) & p = O(pt) : T(n; p) = O(Tmin)
pt je nejmensi pocet procesoru, pro ktere T(n; pt) = absolutne minimalni cas Tmin.
2
2. přednáška - Paralelní architektury a výpočetní modely
Taxonomie z hlediska propojovacích sítí
Multiprocesorové systémy se sdílenou pamětí
(a) multiprocesorová sběrnice
(b) křížový přepínač
(c) nepřímá propojovací sít' (MIN)
Multiprocesorové systémy s distribuovanou pamětí
(a) 2­D mřížka multiprocesorových sběrnic
(b) křížový přepínač
(c) vicestupňová nepřímá propojovací sít' (MIN)
(d) přímá propojovací sit'
RAM
(Neomezený) počet paměťových buněk.
Všechny instrukce trvají jednotkový (konstantní) čas bez ohledu na délku operandů.
Časová složitost algoritmu = # provedených instrukcí.
Prostorová složitost algoritmu = # použitých pamět'ových buněk.
PRAM
(Neomezený) # procesorů RAM
(Neomezený) # sdílených pamět'ových buněk
Každý Pi má vlastní lokální (soukromou) pamět' a zná svůj index i.
Každý Pi může přistupovat do kterékoli buňky sdílené paměti v konstantním čase
Operace:
● Čtení buňky sdílené paměti (READ, krátce R).
● Lokální operace (LOCAL, krátce L).
● Zápis do buňky sdílené paměti (WRITE, krátce W).
Výpočetní síla
PRAM podmodel A je výpočetně silnější než podmodel B, psáno A ≥ B, jestliže jakýkoliv algoritmus
napsaný pro B poběží beze změny na A s tímtéž paralelním časem, předpokládáme­li stejné
architektonické parametry.
3
Lemma 2
Priority ≥ Arbitrary ≥ Common ≥ CREW ≥ EREW.
Plně paralelní algoritmy
PRAM(n; p) algoritmus A je plně paralelní, jestliže
1. T (n, p) = O(1) 2. C(n, p) = O(SU(n)) ⇔ p = O(SU(n)) Simulace velkých PRAM na malých PRAM téhož typu
Necht' A je PRAM(n; p) algoritmus s časem t = T (n, p) necht' p′ < p .Pak A lze simulovat pomocí PRAM
(n, p′) algoritmu na PRAM téhož typu v čase T (n, p′) = O(tp/p′) Simulace PRAM s velkou pamětí na PRAM s malou pamětí
Necht' A je PRAM(n, p) algoritmus s časem t a necht' m < n . Pak A lze simulovat PRAM
(m, max(p, m)) algoritmem na PRAM téhož typu v čase t′ = O(tn/m). Předpokládáme, že simulující procesory mají lokální
paměti dostatečně veliké pro uložení sdílených dat.
Simulace silnějšího PRAM na slabším c.1
Uvažujeme Prioritní­CRCW s prioritním systémem založeným jednoduše na indexování: procesory s nižším
indexem mají vyšší prioritu. Jeden krok Prioritního­CRCW PRAM(n, p) algoritmu lze simulovat pomocí
EREW­PRAM(np, p) algoritmu v O(log p) krocích.
Asynchronní PRAM (APRAM)
●
●
●
●
●
●
Procesory pracují asynchronně, neexistují centrální hodiny.
Operace globální čtení, globální zápis, lokální ­ jako PRAM.
Je nutná explicitní synchronizace: bariérová synchronizace.
Doba přístupu do sdílené paměti není jednotková.
APRAM výpočet = posloupnost globálních fází, ve kterých procesory pracují asynchronně,
oddělených bariérovou synchronizací.
Dva procesory nemohou přistupovat do téže buňky sdílené paměti v téže globální fázi, pokud jeden
z nich zapisuje.
4
4. přednáška - Propojovací sítě paralelních počítačů
Stupeň uzlu u : degG(u) = počet sousedů uzlu u
Množina stupňů grafu G : deg(G) = {degG(u); u ∈ V (G)} Maximální stupeň grafu G : Δ(G) = max(deg(G)) Minimální stupeň grafu G : δ(G) = min(deg(G)) k­regulární graf G : Δ(G) = δ(G) = k Řídký graf: |E(G)| = O(|V (G)|) (stupně uzlů jsou omezeny konstantou)
Hustý graf: |E(G)| = ω(|V (G)|)(stupně uzlů jsou rostoucí funkcí |V (G)| ) Izomorfismus:
Dva grafy G=(V,E) a G'=(V',E') se stejným počtem uzlů i hran jsou izomorfní, jestliže existuje
bijektivní 1­1 zobrazení ƒ : V → V' tak, že platí: <x,y> ∈ E(G) ⇔ <ƒ(x), ƒ(y)> ∈ E'(G').
Automorfismus fix me!
Automorfismus je izomorfní zobrazení grafu G na sebe sama.
Automorfismus grafu G=(V,E) je každý izomorfismus G s G, tedy jestliže existuje bijektivní
zobrazení ƒ : V → V tak, že platí: {x,y} E, právě když {ƒ(x), ƒ(y)} E.
Automorfismus grafu je bijekce, ktera zachovava sousednost a vzdalenost uzlu. (Tak casto rika
Tvrdik)
Sjednocení grafů
G1 ⋃ G2 = (V (G1) ⋃ V (G2), E(G1) ⋃ E (G2)) Kartézský součin G = G1 × G2 : V (G) = {(x, y); x ∈ V (G1), y ∈ V (G2)} E(G) = {< (x1, y), (x2, y) >; < x1, x2 >∈ E(G1)} ⋃ {< (x, y1), (x, y2) >; < y1, y2 >∈ E(G2)} Průměr grafu:
diam(G) = maxu;v distG(u; v) = maxu exc(u) cili minimalni cesta mezi nejvzdalenejsimi
uzly, cili maximalni excentrita uzlu v grafu
Uzlově symetricky graf:
∀u1, u2 ∈ V (G) ∃ automorfismus f, takovy ze f(u1) = u2 Důkaz, ze Qn je vyvazeny bipartitni graf
Q1 je vyvazeny bipartitni graf, Qn je kartezsky součin Q1^n.
Binární hyperkrychle dimenze n, Qn
V(Qn) = ℬn
5
E(Qn) = {<x, negi(x)>; x ∈ V(Qn), 0 ≤ i < n}
|V(Qn)| = 2n
|E(Qn)| = n*2n­1
Definujte n­rozmerna mrizka M(Z1,...,Zn)
V = {(a1, a2,..., an), 0 <= ai < zi | 1 <= i <= n}
E = {((a1, a2, … ai, … an),(a1, a2, … ai+1, … an)) 0<= ai < zi­1}
|V(M(...))| = Π i=1..n zi
|E(M(...))| = Σ i=1..n (zi ­ 1) Π j=1..n,j!=i zj
n­rozměrný toroid dimenzí z1, z2,.., zn, K(z1, z2,.., zn)
V(K(...)) = V(M(..)) ­ jako u mřížky
E(K(...)) = {<(.., ai, ),(.., ai ⊕zi1, ..)>; 0 ≤ ai < zi}
|E(K(...))| = n * Π i=1..n zi
Zabalený motýlek dimenze n, wBFn
V(wBFn) = {(i, x); 0 ≤ i < n ⋀ x ∈ ℬn}
E(wBFn) = {<(i, x), (i ⊕n 1, x)>, <(i, x), (i ⊕n 1, negi(x))> | (i, x) ∈ V(wBFn)}
|V(wBFn)| = n*2n
|E(wBFn)| = n*2n+1
Obyčejný motýlek dimenze n, oBFn
V(oBFn) = {(i, x); 0 ≤ i ≤ n ⋀ x ∈ ℬn}
E(oBFn) = {<(i, x), (i + 1, x)>, <(i, x), (i + 1, negi(x))> | i < n}
|V(oBFn)| = (n+1)*2n
|E(oBFn)| = n*2n+1
Definujte k­arni Delta neprima sit s N vstupy
Banyan 2x2:
switch s 2 vstupy a 2 výstupy
Banyan NxN MIN:
existuje jedinečná cesta mezi dvojicí vstup­výstup
K­ární delta MIN:
Banyan NxN MIN s logk N stupni N/k přepínačů k × k , N = kn Není to spíše?: Banyan MINs N × N skladajcí se ze stupňů N/k prepínačů k × k
Ve skripte to jinak, a se pouziva tam log
Vyraz prumeru n­rozmerneho oBFn
2*n: n pohybů po lineárním poli + n pohybů po hyperkrychli
Hyperstrom
6
hyperstrom je stromový graf, ve kterém má každý uzel m rodičů
a k potomků (stupeň je m + k), kromě uzlů:
bez rodičů ­ kořeny (stupeň k)
bez potomků ­ listy (stupeň m)
Tlusté stromy
počet linek vedoucích nahoru ke kořenu se rovná součtu počtů linek od potomků
Odvodit vztah pro počet hran v zabaleném motýlku wBF.
počet uzlů je n*2n, každý uzel má stupeň 4.Počet hran je tedy 4*n*2n, ale takhle by byla každá
hrana započítána 2x, čili se to ještě podělí dvěma. Vychází to na 2*n*2n = n*2n+1
Dokažte, že n-rozměrná mřížka M(z1, z2, … zn) je bipartitní.
barvím uzly podle lichosti součtu adres v dimenzích (0..zi­1), je zřejmé, že lichý uzel má
všechny sousedy sudé a naopak (vzdálenost 1 kroku změní lichost)
dokažte, že libovolná 1D kružnice je uzlově symetrická
Najdu libovolný automorfismus. Např. přečíslujeme vrcholy, tak že je posuneme o jeden.
důkaz kolik hran se nachází v n rozměrném toroidu
Stejná myšlenka jako u wBF ­ každý uzel má stupeň 2n, uzlů je Πni=1zi , čili součin a po vydělení
dvěma kvuli duplicitním započítaným hranám dá n*Πni=1zi
počet hran v n-rozměrné mřížce: odvození
­ budeme odebírat hrany z toroidu
­ počet uzlů v toroidu je Πni=1zi , počet hran n*Πni=1zi
­ v mřížce máme pro každou dimenzi 2 okrajové uzly (začátek a konec), ze kterých na rozdíl od
toroidu nevychází hrana, a mají tedy o 1 nižší stupeň, než kdyby byla dimenze toroidální
­ kolik je takových uzlů? ­> každý okrajový uzel pro příslušnou dimenzi se jednoduše násobí
velikostmi zi ostatních dimenzí, na těch je totiž okrajovost v aktuální dimenzi nezávislá
­ takto to sečteme pro všechny dimenze, a pro přehlednost vytkneme celkový počet uzlů
­ tedy: 2*(Πni=1zi)*∑ni=11/zi , a ještě vyhodíme duplicity: (Πni=1zi)*∑ni=11/zi
­ vypočetli jsme tedy počet rozdílových hran mezi mřížkou a toroidem stejných parametrů, takže
finální vzoreček může vypadat takhle:
(Πni=1zi)*(n ­ ∑ni=11/zi)
­ výhoda obecnosti:
­­ dá se z toho vykoukat “rekurzivita”: pokud odebereme dimenzi, stačí jí dát velikost 1, a
vzoreček se sám upraví pro mřížku o (n­1) dimenzích
7
­­ nemusíme si pamatovat počet hran v hyperkrychli, protože Q je M(2,2,2,...):
(Πni=12)*(n ­ ∑ni=11/2) = 2n*(n ­ n/2) = 2n*n/2 = 2n­1*n
8
5. přednáška - Vnořovaní a simulace
Vnoření G → H
Vnoření zdrojového grafu G = (V (G), E(G)) do cílové sítě H = (V (H), E(H)) je dvojice zobrazení
(φ, ξ) , kde:
φ : V (G) → V (H) ξ : E(G) → P (H) a
P (H) = množina všech cest sítě H
...čili zobrazení množiny vrcholů grafu G na množinu vrcholů grafu H a zobrazení množiny hran
grafu G na množinu cest grafu H (jednu hranu z grafu G lze namapovat na cestu v grafu H o
délce větší než 1 hrana).
Uzlové zatížení
Zatížení cílového uzlu v ∈ V (H) : load(v) = |{u ∈ V (G); φ(u) = v}| … čili počet uzlů z grafu G, které jsem namapoval na uzel v ∈ V (H) . Zatížení vnoření (φ, ξ) :
load(φ, ξ) = max load(v) v ∈ V (H) … čili maximální uzlové zatížení v daném vnoření.
Průměrné zatížení vnoření (φ, ξ) … aritmetický průměr přes všechna vnoření.
Vnoření (φ, ξ) má stejnoměrné zatížení, pokud je průměrné zatížení přibližně rovno
maximálnímu.
Expanze vnoření
expanze vnoření je poměr velikosti cílového grafu (počet uzlů) ku velikosti zdrojového grafu
vexp(φ, ξ) =
|V (H)|
|V (G)|
…čili většinou poměr procesorů ku procesům.
Dilatace
Dilatace zdrojové hrany e ∈ E(G) : dil(e) = len(ξ(e)) ...čili na jak dlouhou cestu v H se zobrazí hrana z G
9
Dilatace vnoření je maximální ze všech dilatací v daném vnoření
Průměrná dilatace je aritmetický průměr přes všechny dilatace v daném vnoření
Vnoření má stejnoměrnou dilataci, pokud je průměrná dilatace přibližně rovna maximální.
Linkové a uzlové zahlcení
Linkové zahlcení cílové linky e2 ∈ E(H) :
ecng(e2) = |{e1 ∈ E (G); e2 ⊆ ξ(e1)}| …čili kolik namapovaných cest sdílí danou hranu.
Linkové zahlcení vnoření (φ, ξ) : maximální zahlcení v celém vnoření
Uzlové zahlcení cílového uzlu u2 ∈ V (H) :
ncng(u2) = |{e1 ∈ E (G); u2 ⊆ ξ(e1)}| ...čili kolik namapovaných cest sdílí daný uzel.
Grafy G a H jsou quasiisometricke, pokud existuji vnoreni G → H i H → G s konstantnimi
hodnotami meritek vnoreni
Grafy G a H jsou výpočetně ekvivalentní sítě, pokud G dokáže simulovat H s konstantním
zpomalením a naopak.
quasiisometrie implikuje vypocetni ekvivalentnost, nikoli naopak
Hyperkubicky algoritmus v Qn je normalni, jestlize
v jakemkoli kroku algoritmu jsou pouzity pouze hrany jedne dimenze hyperkrychle
a jestlize v po sobe jdoucich krocich jsou pouzivany po sobe jdouci dimenze.
10
6. přednáška - Směrování, techniky přepínání a zablokování
klasifikace SA
komunikace jeden­jednomu, jeden­mnoha, všichni­všem
komunikace jeden-jednomu
jedna komunikující dvojice, více dvojic, permutační směrování
základní dimenze návrhu komunikace v propojovacích sítích
topologie ­ jak jsou uzly propojené
směrovací alg. ­ trasa ze zdroje do cíle
řízení toku ­ přidělování omezeného množství sdílených prostředků
architektura směrovače
HW koprocesor
top­level:
vnitřní vstupní (injekční) a výstupní (ejekční) kanály ­ na sběrnici
vnější vstupní a výstupní kanály
struktura směrovače: přepínač, box pro směrování a řízení toku, vše propojeno kanály
struktura kanálu: fronty zpráv, linkové kontroléry, komunikační médium (kabel)
vnitřní kanály:
1­portový procesor (1 injekční, 1 ejekční kanál)
k­portový procesor (k injekčních, k ejekčních kanálů)
vše­portový procesor (# injekčních/ejekčních = # vnějších kanálů)
přepínač propojuje vstupní kanály na výstupní
fronta ­ FIFO paměť pro jednotky komunikace, na vstupech nebo výstupech nebo obojí
směrovost kanálů ­ jednosměrné, poloduplexní, plně duplexní
jednotky komunikace
zpráva ­> paket ­> flit ­> fit
zpráva ­ proměnná délka
paket ­ pevná délka, směrovací info, hlavičkové flity (cíl. adr., pořad. č.)
flit ­ přenos několik cyklů
fit ­ atomická jednotka, přenos 1 fyz. linka / 1 cyklus
směrovací algoritmus
směrovací relace (množina výstupních kanálů) + výběrová fce (výběr 1 položky z toho)
směrovací rozhodnutí
distribuované (inkrementální) směrování ­ směrovače počítají z cílových adres v hlavičkách
zdrojové ­ zdrojový uzel určí úplnou trasu, směrovač jen čte a zkracuje řetěz tranzitních adres
­ křižovatkové pro mřížky/toroidy ­ hlavička = směrovka + adresa jejího uzlu
hybridní (vícefázové) ­ zdroj předpočítá mezilehlé uzly, přesné mezitrasy dělají směrovače
11
adaptivita
žádná, pseudo, plná
deterministické směr. alg. ­ pořád ta samá trasa
datově necitlivé ­ výběrová fce necitlivá ke stavu sítě, výběr volných kanálů náhodně/cyklicky
adaptivní ­ snaha vybrat nejméně zahlcený směr (+ bez poruch)
­ používá info o stavu kanálů (délky front, historie atp.)
používá se distribuované adaptivní směrování
minimalita
minimální:
alias lačné, přímé, přírustkové, po nejkr. trase (algoritmy)
každé směrovací rozhodnutí přivádí paket blíže k cíli
hrozí deadlock
např. deterministické, datově necitlivé
neminimální:
alias nelačné, nepřímé, obcházecí, nepřírustkové
paket může být poslán dále od cíle
hrozí livelock
např. plně adaptivní
implementace SA
požadavek na rychlost, čili HW řešení při distr. směrování
konečný automat nebo směrovací tabulky
směrovací tabulky:
1 položka ­> celá trasa u zdrojového nebo výstupní kanál u distr. s.
statické nebo dynamicky udržované
nevýhodou velké paměťové nároky závislé na velikosti sítě
=> proto: intervalové směrování ­ k výst. kanálu interval cílových adres
metrika časové složitosti komunikačních operací
rychlost, šířka a zpoždění kanálu
zpoždění startovní, směrovací, přepínací, zákl. síťové, zákl. komunikační, celkové síťové
šířka kanálu definuje velikost fitu
zpoždění kanálu je mezi sousedními směrovači
směrovací zp. je čas výpočtu směrovacího rozhodnutí
přepínací zp. je jak dlouho směrovači trvá přenos ze vstupu na výstup
přepínání kanálů (circuit switching)
­ vyslána směrovací sonda, která rezervuje trasu, ukládána v každém směrovači, když je na
konci tak ACK flit zpět
­ super je to, že sonda spolu se směrovači vytvoří fyzický obvod (HW, vodič), kde je využita
plná přenosová rychlost ­ datové bity zprávy se nikde na cestě neukládají, žádné omezení na
délku
12
­ výhodné pro dlouhé ne příliš časté zprávy
p = velikost směrovací sondy (ve flitech)
přepínání ulož-pošli-dál (store-and-forward)
“přepínání paketů, packet switching”
­ jednoduché, ukládá se celý paket a posílá se po s. rozhodnutí (hop), směrován individuálně
­ obsazen nejvýše 1 kanál, velké fronty (kapacitně)
­ požadavek na minimální směrování a malý průměr sítě, také na omezenou velikost paketu
průřezové přepínání (virtual cut-trough)
­ zprávy v paketech a směrovače mají fronty pro celé pakety
­ hlavičkový flit nečeká na zbytek a prořízne se dál hned jak je učiněno s. rozhodnutí a výstupní
kanál volný, to samé dělají další datové
­ fronty podél trasy blokovány
­ pokud hlavička nemůže pokračovat, datové flity se postupně dotahují a uvolňují tak kanály
červí přepínání (wormhole)
“a tlačím tam tu jitrnici” :)
­ jde o posouvání řetězu paketů coby flitů po trase přesně jako u bezkonfliktního VCT
­ ale směrovače nemají fronty pro celé pakety, jen pro 1..několik flitů => levná technologie
­ problém: pokud hlavička nemůže pokračovat obsazeným kanálem, celý řetěz stojí =>
zamrznutí a nasnadě i deadlock
deadlock
= statické zablokování
cyklus závislostí na prostředcích (řetěz požadavků)
efekt sněhové koule: deadlock se šíří čím je větší, kdykoli agent (­paket) potřebuje prostředek
(­kanál) z tohoto cyklu, je automaticky zablokován také
řešení deadlocku
­ detekce a zotavení: teprve až se to po**** tak se něco dělá, síť je potřeba zotavit
­ prevence: konzervativní přidělování všech prostředků najednou, jejich malé využití, např. v CS
­ vyhnutí se zablokování: postupné přidělování, vždy po každém přidělení musí být deadlock
vyloučen
13
vyhnutí se zablokování
Deterministicka smerovaci funkce R na grafu G: pro kazdy vstupni uzel u ∈ V (G) , pro kazdy
jeho vstupni kanal c1 a pro kazdy cilovy uzel d, smerovaci funkce R urci vystupni kanal c2 =
R(u;c1; d).
Graf kanalovych zavislosti Z = Z(G, R) uzly jsou kanaly c
i site G
hrany < c1, c2 > ∈ Z ⇔ R muze smerovat paket z kanalu c1 do kanalu c2
nemuze dojit k zablokovani iff tento graf je acyklicky
Korektni graf: Souvisly graf je korektni, pokud lze uvalenim orientace na jeho hrany
zkonstruovat graf G’ ktery ma pouze 1 koren a je acyklicky (neexistuji orientovane kruznice)
Legalni orientovane trasy
pro smerovani Up*/Down*: trasy skladajici se z 0 nebo vice hran smerem nahoru a pote 0 nebo
vice hran smerem dolu
další vysvětlivky:
přenos zprávy velikosti ᵬ (mí) (počet fitů) na vzdálenost ᵬ (delta) (počet mezilehlých hran)
ts­ zpoždění nutné pro přípravu celé komunikace
tr ­ čas nutný pro směrovací rozhodnutí
tm ­ zpoždění na lince mezi dvěma uzly
tw ­ zpoždění na uzlu (čas nutný pro přesunutí dat z vstupních portů na výstupní)
14
7. přednáška - Základní paralelní algoritmy: PPS, PJ a ETT
Nepřímý strom
Vstupní data pouze v listech, vnitřní uzly pouze počítají.
Eulerovská kružnice
Eulerovská kružnice grafu G je kružnice, která prochází každou hranou G právě jednou.
Eulerovský graf
Graf G je eulerovský, má­li každý jeho uzel sudý stupeň.
Eulerovský strom
Neorientovaný strom může být transformován na eulerovský, je­li každá jeho hrana nahrazena
dvojicí anti­paralelních hran.
15
8. přednáška - Paralelní řadící algoritmy
Nepřímé řadící sítě
●
Řadící síť' = sít' složená ze sloupců komparátorů
(jako MIN).
●
●
●
●
●
●
Komparátor = HW implementace operace C&E
(vzestupně, sestupně)
Nesetříděná (neseřazená) vstupní posloupnost X = [x1,..., xn] je permutována na
setříděnou výstupní posloupnost (klesající, rostoucí, bitonickou) Y = [y1,...., yn].
Statická řadící sít' = HW implementace datově necitlivého řadícího alg.
Počet // C&E kroků = hloubka řadící sítě = délka nejdelší cesty ze vstupu na výstup.
Je­li N > # vstupních vodičů ­> operace Sluč­a­Rozděl (Merge­and­Split, M&S).
Přímé řadící sítě
● C&E operace mezi dvojicí procesorů:
● Topologie: mřížky, toroidy, hyperkrychle,
hyperkubické sítě
● Přímý řadící alg. = posloupnost dokonalých párování procesorů (perfect matchings)
odvozených z jejich lineárního očíslování.
● Výběr vhodného očíslování procesorů má vliv na složitost C&E řazení pro danou topologii
(podobně jako u PPS algoritmu).
● Příklady číslování:
●
●
●
1 dokonalé párování se skládá z [p/2] disjunktních dvojic procesorů
Datově necitlivé řazení: způsob párování nezávisí na vstupních datech.
Triviální spodní mez na složitost C&E řazení: průměr grafu
Datově necitlivé řazení
Necht' f = monotónně rostoucí funkce na lineárně uspořádané množině S,
čili ∀ x, y ∈ S; x <= y ⇔ f (x) <= f (y) pak X­>Y => f(X)­>f(Y), ‘­>’ je komparátor
­ důkaz indukcí:
16
­ základní krok: (x,y)­>(min(x,y),max(x,y)) =>
(f(x),f(y))­>(min(f(x),f(y)),max(f(x),f(y))) =
(f(min(x,y)),f(max(x,y)))
­ indukční krok: nese­li určitý vodič v řadící síti hodnotu xi, když je na vstupu posloupnost
X, pak tentýž vodič nese hodnotu f(xi), když je na vstupu f(X)
Lemma 0-1
Jestliže datově necitlivý řadící algoritmus dokáže setřídit (seřadit) libovolnou binární vstupní
posloupnost, pak dokáže setřídit libovolnou vstupní posloupnost.
bitonicka posloupnost posloupnost je bitonicka, pokud obsahuje prave 1 udoli a prave 1 vrchol
nezavisle na rotaci
udoli = prvek ktery je mensi nez oba jeho sousedi. Vrchol analogicky naopak
17
9. přednáška Permutace v ortogonálních a hyperkubických sítích
Úplná permutace
Každý uzel vyšle a přijme právě 1 paket.
Neúplná permutace
Každý uzel vyšle nebo přijme nejvýše 1 paket.
Náhodná permutace
Každý procesor si volí náhodně 1 cíl → 1 uzel se může stát cílem pro více než 1 paket.
On-line směrování
Permutace není globálně známá, každý procesor zná pouze svůj paket.
Off-line směrování
Permutace je známá dopředu, protože se provádí jedna a tatáž opakovaně → vyplatí se
předpočítat si časově anebo paměťově optimální směrování.
Permutace otočení
πr : un−1… u0 → u0… un−1 Permutace prohození
πt : un−1… ukuk−1… u0 → uk−1… u0un−1… uk , je­li n = 2k πt : un−1… uk+1ukuk−1… u0 → uk−1… u0ukun−1… uk+1 , je­li n = 2k + 1 Permutace bitový posun (přeložení) o w
πpw : un−1… u0 → un−1… u0 XOR wn−1… w0 pro daný n­bitový řetězec
wn−1… w0
Binární doplněk
πd : un−1… u0 → un−1… u0 Cyklický (aritmetický) posun o δ πs δ : u → u ⊕N δ , u, δ ∈ {0, …, N − 1} 18
з
Zhušťovací (packing) neúplná permutace
Směřování paketů z libovolné podmnožiny vstupů M do prvních m = |M| výstupních uzlů tak,
že relativní pořadí paketů se nezmění. Relativní pořadí paketů můžeme vypočítat pomocí
PPS. Opakem zhušťování je zřeďování.
Monotónní permutace
Monotónní permutace je každá permutace, kde nedochází ke změně pořadí paketů mezi vstupy
a výstupy. Libovolná monotónní permutace je složením zhušťovací a zřeďovací permutace.
19
20
10. přednáška - Kolektivní komunikační algoritmy I
Typy KKO:
● vysílání jeden­všem (OAB)
● vysílání skupině (MC)
● rozesílání jeden­všem (OAS)
● vysílání všichni­všem (AAB)
● rozesílaní všichni­všem (AAS)
Parametry modelů KKO:
● Počet portů: 1­portový, vystupně všeportový, nebo všeportový model
● Smerovost kanalu: simplexní, poloduplexní, nebo plne­duplexní
● Technika prepínaní: uloz­a­posli­dal (SF) nebo cerví (WH) prepínaní
● Moznosti manipulace se zpravami: kombinujcí nebo nekombinujcí model
● Velikost vyslane zpravy/paketu: μ
Parametry pro měření komunikační složitosti:
● Časová složitost kolektivní operace XXX:
● Model konstantního času: počet kroků (kol): spodní mez ρxxx (G) , horní mez
rxxx(G) ○ SF sítě: 1 krok = množina souběžných hopů mezi sousedy.
○ WH sítě: 1 krok = množina současně použitých linkově disjunktních cest.
● Model lineárního času: komunikační zpoždění v sekundách: spodní mez τ xxx(G) ,
horní mez txxx(G) ●
●
●
Komunikační operace: celkový počet hopů (SF) či paketo­hran (WH). Spodní mez
ηxxx(G) , horní mez hxxx(G) .
Požadavky na velikost pomocných front uvnitř směrovačů β :
○ vztahuje se většinou pouze na SF sítě, WH směrovače mívají β = 0 . Komunikační efektivnost: efektivní kolektivní komunikační algoritmy by měly
○ plně využívat propustnost (bisekční/sít'ovou) sítě = být schopný využít všech
použitelných kanálů a front během celé operace.
○ eliminovat redundantní komunikaci
■ podmínka NODUP = NO­DUPlication,
■ podmínka NOHO = NO­node­Hears­its­Own­information
21
Download

1. přednáška - Složitost a škálovatelnost paralelních