Pro sudé n=2k popište algebraicky vnoření n-rozměrné hyperkrychle Qn do 2-D mřížky M(2^k,2^k) založené na Peano indexování ( čili mapování binárních n-bitových řetězců na dvojice souřadnic [x,y]). Vyslovte tvrzení o optimalitě dilatace tohoto vnoření a toto tvrzení dokažte.

★ Bylo ve zkoušce: 2011-06-30, 2014-01-20 - za 6b

Viz přednáška 5/2012, slide 30 nebo skripta EN [2009] str. 67 nebo CZ [2006] str. 85

Tady bylo celkem 8bodů, z toho spodní mez vnoření 2b., horní mez vnoření 2b., algebraický popis vnoření 2b. a správně nakreslené schéma vnoření pomocí Peanovy křivky taky za 2b. Cokoli mimo (omáčka) 0b.

Ten algebraický popis jsem zapsal jako: Může to někdo komentovat? Co to má znamenat? A proč tam není i 011 → 1,1?

000 -> 0,0
001 -> 0,1
010 -> 1,0

s tím, že jsem tam pak vyznačil, že se vpravo opakují jedničky a nuly periodicky a vlevo se taky něco opakovalo, z čehož sem vyvodil, že by k tomu šlo sestrojit nějaký obecný pravidlo.

Pravidlo:

JDU: Opravdu to pravidlo funguje? (bez záruky, třeba neumím počítat)
V <math>Q_4</math> je uzel 15 (1111) úplně vpravo dole a má souřadnice (3,3). Dle vzorce, který jde i = 0,1,2 (n/2 == 2). Součet první souřadnice tedy vrací 1*1 + 1*2 +1*4 = 7 a NE 3.
Je třeba jen upravit mez v součtu na (n/2)-1. Tak, jak je to teď, to pro <math>Q_4</math> vrací špatný výsledek a u <math>Q_6</math> už adresovaný bit ani neexistuje.

Spodní mez na dilataci spočítáme dle věty 10 (průměrový argument, přednáška 5, slajd 10) jako poměr průměrů sítí (do/z resp. procesory/procesy) tedy pro tento konkrétní případ

<math> \text{dil}\left(\varphi,\xi\right)\geq\left\lceil \frac{\text{diam}\left(H\right)}{\text{diam}\left(G\right)}\right\rceil =\left\lceil \frac{\left(2^{k}-1\right)+\left(2^{k}-1\right)}{2k}\right\rceil =\left\lceil \frac{\cancel{2}\left(2^{k}-1\right)}{\cancel{2}k}\right\rceil =\underline{\underline{\frac{2^{k}}{k}}} </math>.

Horní mez, je pro <math>Q_{2k} </math> (sudá dimenze) vždy polovina strany adekvátní mřížky, tedy <math> \frac {2^k} {2} = 2^{k-1} </math>. Asi mu to takle nebude stačit, takže to chce ještě nakreslit schéma toho peano vnoření a ukázat na něm jak roste dilatace mezi uzly (původně sousedními v <math>Q_{2k}</math>) líšícími se v i-tém bitu v tom vnoření v M.

Při <math>load = 1</math> se <math>dil = \frac{2^k}{k}</math>

Mapování se nazývá Mortonova křivka, přednáška 5 / slajd 30 (2015).

PPS na EREW PRAM, <math>p<n</math>, lokální operace trvají čas 1, paměťové čas <math>d > 1</math>. Dokažte správnost. Odvoďte <math>T(n,p)</math>, <math>E(n,p)</math>.

★ Bylo ve zkoušce: 2013-01-30, 2013-12-20, 2012-01-176b, část řešení 2013-01-09 a 2015-01-06 (za 6b)

Viz skripta CZ [2006] str. 99 nebo EN [2009] str. 93

mi-par2014-prednaska7-fundamental.pdf slide 5

<math>p=N</math>:

for i=0 ... N-1 do_in_parallel
  y_i = M[i];
 
for j=0 ... ⌈log N⌉-1 do sequentially 
{
  for i = 2^j ... N-1 do_in_parallel
    y_i += M[i - 2^j];
 
  for i = 2^j ... N-1 do_in_parallel
    M[i] = y_i;
}

Důkaz správnosti:

Výpočet je založen na tom, že v paralelním kroku <math>j</math> sdílená paměťová bunka <math>M[k]</math> naakumulovala sumu hodnot <math>M[k - 2^{j+1}+1, …, k-1, k]</math>

• v kroku 0 (první krok, jen indexovaný od 0): obsahuje <math>M[k, k-1]</math>
• v kroku 1: obsahuje <math>M[k, k-1, k-2, k-3]</math>
• …

Elementární krok pro <math>j=0</math> platí

Indukční krok: Nechť platí pro <math>j-1</math>, ukážu, že platí pro <math> j</math>
⇒ na začátku kroku <math>j-1</math> je tedy v <math>M[k, k-1, … , k-2^{j-1} + 1]</math>

v <math>M[k - 2^{j-1}] = M [k^* - 2^{j-1}, k^* - 2^{j-1} - 1 , … , k^* - 2^{j-1} - 2^{j-1} + 1 = k-2^{j} + 1]</math>
⇒ <math>M[k] + M[k-2^{j-1}] = M [k, k-1 , … , k - 2^{j-1} + 1, k-2^{j-1}, … , k - 2^j + 1]</math>
⇒ což je stav na začátku fáze <math> j</math> ⇒ cbd.

Škálovatelnost:

Pro <math>p<N</math> probíhá výpočet takto:

1. Procesory si rozdělí čísla do intervalů <math>S_i</math> o počtu prvků <math>N \over p</math>. Každý <math>P_i</math> provede prefixový součet ve svém intervalu. Každý interval se zredukuje na 1 číslo.
2. Provede se paralelní prefixový součet nad <math> p</math> čísly.
3. Každý <math>P_i</math> pošle výsledek PPS procesoru <math>P_{i+1}</math>, každý <math>P_{i+1}</math> přijme výsledek od <math>P_i</math>
4. Přičte ke všem hodnotám ve svém intervalu a zapíše vše do M.

<math>T(N,p) = \underbrace{\left ({N \over p} \cdot d + {N\over p} - 1 + d \right )}_{1.} + \underbrace{\log p \cdot (d + d)}_{2.} + \underbrace{d}_{3.} + \underbrace{ {N \over p } + {N \over p } \cdot d}_{4.} = \underbrace{ O({N \over p })}_{1.} + \underbrace{O(\log p)}_{2.} + \underbrace{O(1)}_{3.} + \underbrace{ O({N \over p })}_{4.} = O(\frac{N}{p} + \log p)</math>

<math>C(N,p) = O(N + p \cdot \log p)</math>

<math>E(N,p) = \Omega(\frac{N}{N + p \cdot \log p})</math>

(Celkový paralelní čas <math>T(N,p)</math> je stejný jako u paralelní redukce. Z toho plyne, že PPS má stejnou škálovatelnost jako paralelní redukce.) - tohle do zkoušky nepsat, pokud to rovnou nedokážete

(UPDATE:) U PPS chybi lokalni operace (musi ty nactena cisla jeste secist, nicmene pozdeji se to zanedba

(UPDATE2:) Když jsme u toho, tak ten PPS by měl trvat ještě o d více, protože operace čtení dvou čísel bude některým procesorům trvat 2d, protože je to Exclusive Read a některé buňky se budou snažit číst dva procesory najednou. Tzn. 2d + 1 + d = 3d + 1

RE:UPDATE2: To nečtou 2 najednou, ale v jednom kroku levou hodnotu a v druhym pravou. Ale jo, měly by to být 2 čtení, lokální součet a zápis.

RE:UPDATE: Žádné dvě čtení tam nebudou, stačí se podívat na algoritmus. Vždy z paměti čte pouze nové číslo, předchozí, které sice uložil do sdílené paměti si sám nechal a nepotřebuje ho znovu číst. Takže nedojde ani ke dvoum čtení ze sdílené paměti, ani ke kolizi, protože každé číslo čte ze sdílené paměti max 1 procesor.

Segmentový PPS na nepřímém <math>CBT_{log(p)}</math>, SF, dokázat korektnost, spočítat <math>T(n,p)</math>.

★ Bylo ve zkoušce: 2012-01-24 a 2012-12-18 a 2013-01-02

scripta [CZ] - str. 103

prednasky [2012] - pr. 7 slide 8-9

Kouzlo SPPS spočívá v tom, že je algoritmicky úplně stejný jako PPS, jen s upravenou operací. Algoritmus (S)PPS na nepřímém CBT_{log p} se chová takto:

Algoritmus se skládá z lokálního (S)PPS, pak paralelního stromového nad lokálními součty, pak lokálního dopočtu lokálních prvků. První a poslední část má složitost lineární nad poměrnou částí dat, čili O(n/p).

Časová složitost prostřední, paralelní, stromové části je dána průchodem log p úrovněmi nahoru až do kořene, odkud se spustí poslední lavina šipek dolů. Dřívější laviny šipek dolů, které se průběžně cestou nahoru spouští, skončí všechny dříve, jelikož začnou v nižší úrovni. Poslední lavina bude tedy opět průchod log p úrovněmi, dohromady tedy 2 log p = O(log p).

<math> T(n,p) = O(n/p + log p) </math>

Binární operace pro segmentaci, kterou je nahrazena původní asociativní operace, má přesně tento předpis:

Pravý sloupeček zajistí, že cokoli přijde do prvku na začátku segmentu jej nezmění. Levý sloupeček řeší součet uvnitř segmentu. Levá dolní buňka zajišťuje, že souvislá řada od začátku segmentu je již definitní (|) a nezmění se, ani když přijde hodnota z předchozího segmentu.

Aby byl SPPS v této formě funkční za použití standardního PPS algoritmu, musí být zajištěno, že nová binární operace je asociativní. Tvrdíme, že asociativní je za podmínky, že byla asociativní operace původní. Tvrzení dokážeme úplnou tabulkou:

(Testovaná upravená operace je tu místo pruhu nad označena pruhem pod.)

Podíváme se na poslední dva sloupečky. Je vidět, že se rovnají právě za podmínky, že původní operace plus v kruhu je asociativní. Tím je tvrzení dokázáno a příklad snad kompletní.

Uvažujte 2-D mřížku <math>M(z_{x},z_{y})</math> s plně duplexními linkami a 1-port. procesory, jejichž směrovače realizují WH XY směrování. Odvoďte spodní mez <math>\rho_{MC}</math> na počet kroků pro multicast ze zdroje v obecném uzlu <math>s</math> a s cílovou skupinou uzlů <math>S</math>. Pak obecně popište krokově opt. algoritmus pro tento problém a dokažte jeho korektnost. Poté aplikujte tento algoritmus na <math>M(5,5)</math> na obrázku. (pozn.: obrázek = mřížka 5×5, zvýrazněný 1 zdrojový a několik cílových uzlů).

★ Bylo ve zkoušce: 2014-01-13, 2012-01-03, 2013-01-09 (s YX směrováním), 2013-01-23, 2015-02-05 a 2016-01-15

Viz skripta CZ [2006] str. 179 | přednáška 10 [2015/16], slide 37

1) Vytvořím si lexikograficky uspořádanou posloupnost cílových uzlů. Pokud mame XY smerovani, radime uzly podle YX. (Pozn. by turambar: pozor na to, je to sice asi jasný, ale jak řadíme je klíčové pro to, aby to bylo bezkolizní a krokově optimální, mně to v tom sledu během písemky nedocvaklo a řadil jsem po řádcích, výsledek - 6 stržených bodů) (Pozn. by vlasaj: mně dokonce strhl všech 8 bodů za řazení po řádcích, jinak bylo prý vše dobře, ale není to pak optimální. Takže fakt bacha!)

DM: Říct, že řadíme uzly podle YX je zavádějící - řadíme normálně podle XY, když máme XY směrování, ale s tím, že X označuje SLOUPEC. Ono i v tom směrování se napřed směruje do správného sloupce (podle souřadnice X), až pak do řádku.

2) Uspořádanou posloupnost rozdělím na 2 poloviny

• a) je-li zdrojový (vysílající) uzel v dolní polovině, pošle zprávu poslednímu prvnímu uzlu v horní polovině
• b) je-li zdrojový uzel v horní polovině, pošle zprávu prvnímu poslednímu uzlu z dolní poloviny
• Pozn.: Takto to sice je napsano i ve slajdech (10/37), ale imho to neodpovida obrazku na stejnem slajdu (stejny jako obrazek zde).

3) Totéž schéma se aplikuje na obě poloviny

Spodní mez na počet kroků MC ve WH sítích je:

<math>r_{MC}\left(M\left(z_{x},z_{y}\right),\mathcal{M},s\right)=\rho_{MC}\left(M\left(z_{x},z_{y}\right),\mathcal{M},s\right)=\left\lceil \log\left(\left|\mathcal{M}\right|+1\right)\right\rceil </math>

Kde <math> \mathcal{M} </math> je podmnožina mřížky, kterou informujeme (vyjma zdrojového uzlu). V každém kroku se může počet uzlů maximálně zdvojnásobit. Algoritmus je krokově optimální.

V tomto konkrétním příkladu je:

<math> \left|\mathcal{M}\right|=7 </math>, tedy <math> \rho_{MC}=\left\lceil \log\left(\left|\mathcal{M}\right|+1\right)\right\rceil =\left\lceil \log\left(7+1\right)\right\rceil =\left\lceil \log\left(8\right)\right\rceil =\underline{\underline{3}} </math>.

Edit: nemá to být log(M-1)? podle obrázku, |M| = 8, takze log(8+1) = 3.1 → 4 což není pravda, Edit MPo: |M| = 7, protože jeden uzel je zdroj a ten žádnou informaci nepotřebuje. Tím je log(8) = 3 a to pravda je

Jiný pohled na krokování algoritmu:

Edit: Algoritmus upraven podle EN skript, str 159, text neodpovídal obrázkům. V CZ skriptech je zjevná chyba. Složitost algoritmu upravena podle náročnosti na hyperkrychli na str 158, měla by být stejná jako pro mřížku.

Odvoďte spodní meze na počet kroků <math>\rho_{AAB}(K(z_1,z_2))</math> a na komunikační zpoždění <math>\tau_{AAB}(K(z_1,z_2), \mu)</math> pro nekombinující vysílání všichni všem (AAB) na vše-portovém plně-duplexním 2-D toroidu <math>K(z_1,z_2)</math>, každý uzel má na počátku připraven paket o velikosti m a přepínání paketů je typu ulož-pošli-dál (SF), kde přenos paketu o velikosti <math> \mu </math> mezi 2 uzly ve vzdálenosti d trvá <math>t(d, \mu) = t_s + \mu d t_m</math>. Popiště co nejlepší algoritmus pro tuto komunikační operaci za těchto podmínek. Odvoďte jeho počet kroků <math>r_{\rm AAB}(K(z_1,z_2))</math> a časovou složitost <math>t_{\rm AAB} (K(z_1,z_2), \mu)</math> a vyslovte tvrzení o jeho optimalitě.

[11. přednáška 14/15, slajdy 19-21]

Spodní meze:

Nechť <math>N=z_1 z_2</math>.

<math>\rho = \left\lceil{N - 1\over d}\right\rceil</math> … každý uzel musí přijmout N - 1 zpráv, v každém kroku může přijmout jenom d, protože máme nekombinující model. Zde d značí stupeň uzlu v toroidu, tedy 2n. Pro dvoudimenzionální toroid d = 4.

<math>\tau = \rho * (t_s +\mu t_m)</math> … v každém kroku se přijme na každém portu jedna zpráva velikosti m.

Algoritmus:

Všechny uzly jsou kořeny OAB stromů. OAB běží paralelně, aby nedocházelo ke kolizím, tak stromy musí být časově-hranově disjunktní; na slajdech jsou označovány TADT. Navrhneme strom OAB tak, aby v každé vzdálenosti od kořene měla každá hrana jinou orientaci. Teorie pak tvrdí, že v topologii 2D toroidu jsou libovolná dvě přeložení takového stromu TADT.

V každém uzlu koření jedna kopie broadcastovacího stromu a všechny uzly vyšlou současně svou hodnotu po d portech. Zprávy ze všech zdrojů jsou tedy ve stejných hloubkách svých stromů a díky vlastnosti TADT nenastanou kolize.

Každý strom se skládá z <math>d = 4</math> větví o délkách <math>l = \left\lceil{N - 1\over d}\right\rceil</math>. Všechny paralelní OAB skončí současně, až zpráva dojde na konec větve; tedy po l krocích.

<math>r_{\rm AAB} = \left\lceil{N - 1\over 4}\right\rceil</math>

<math>t_{\rm AAB} = (t_s + \mu t_m) * \left\lceil{N - 1\over 4}\right\rceil</math>

Algoritmus je časově optimální.

2. možnost řešení:

Najdeme dvě hranově disjunktní Hamiltonovské kružnice. Každý uzel rozdělí svůj paket na poloviny. Jednu polovinu pošle po jedné Hamiltonovské kružnici (oběma směry), druhou polovinu pošle po druhé Hamiltonovské kružnici (oběma směry). každá polovina putuje oběma směr, tj. stačí jí dojít jen do půlky kružnice. Počet kroků i čas vyjdou stejně.

OAS na toroidu <math>K(z_1, z_2)</math>, 1-port, WH, kombinující, bod <math>(a_1,a_2)</math>, 1 paket velikosti <math> \mu </math>, <math>t=t_s + d \cdot t_d + \mu t_m</math>. Efektivnost algoritmu, <math>\rho</math>, <math>\tau</math>, <math> r </math>, <math> t</math>, porovnat optimalitu.

OAS → jeden uzel rozesílá <math>z_1 \cdot z_2 - 1</math> zpráv, ostatní 1 paket přijímají, jedná se o WH ⇒ spodní mez není citlivá na vzdálenost.

Počet kroků je omezen počtem uzlů, počet informovaných uzlů se každým krokem nejlépe zdvojnásobí ⇒ <math>\rho_{OAS} (K(z_1,z_2)) = \log (z_1 z_2)</math>

<math>\tau_{OAS} = \rho_{OAS} \cdot t_s + exc(G,a) \cdot t_d + \lceil {(z_1 \cdot z_2 - 1) \over d } \rceil \cdot t_m</math>

Základní kámen je OAS na 1D toroidu T(z)

<math>\begin{array}{rrl} t_{OAS} = & & t_s + {z \over 2} \cdot t_d + \mu \cdot {z \over 2} \cdot t_m
& + & t_s + {z \over 4} \cdot t_d + \mu \cdot {z \over 4} \cdot t_m
& & \ \ …
& + & t_s + 1 \cdot t_d + \mu \cdot 1 \cdot t_m
\end{array} \:\: \log z \mbox{ kroku}</math>

<math> s = {z \over 2} + {z \over 4} + …. + {z \over z} = z \left ( {1 \over 2} + {1 \over 4} + …. + {1 \over z} \right ) = z \cdot {1 \over 2} \cdot \frac{ \frac{z-1}{z} }{ \frac{1}{2} } = z-1</math>

<math>\right t_{OAS} = \log z \cdot t_s + (z-1)(t_d) + (z-1)(\mu t_m) = \log z \cdot t_s + (z-1)(t_d + \mu t_m)</math>

<math>r_{OAS} = \log z</math>

Algoritmus pro 2D toroid se skládá z fáze

1. OAS v řádku se zdrojem ⇒ každému uzlu pošlu informaci pro celý sloupec <math>\right t_1 = (\log z_1) t_s + (z_1-1)t_d + (z_1 z_2 -1)\mu t_m</math>
2. OAS ve sloupcích paralelně <math>\right t_2 = (\log z_2) t_s + (z_2-1)(t_d + \mu t_m)</math>

<math>t_{OAS} = t_1 + t_2 = \log (z_1 z_2) t_s + (z_1 + z_2 - 2)t_d + (z_2(z_1+1) - 2)\mu t_m</math>

<math>r_{OAS} = \log z_1 + \log z_2 = \log (z_1 \cdot z_2)</math>

⇒ algoritmus je co do počtu kroků asymptoticky optimální. Z hlediska časové složitosti je také optimální (<math>\tau_{OAS} = t_{OAS} </math>)

JDU: ad fáze 1 v 2D toroidu: součet u <math> \mu t_m</math> mi přijde nějaký divný. Vyšlo mi <math>z_1z_2-z_2</math>. V kroku pošlu vždy <math>\frac{z_1z_2}{2}</math>, <math>\frac{z_1z_2}{4}</math>, … Od toho se pak odvíjí i případná chybovost dalších rovnic. Logicky v první dimenzi posílám všechana data, ale ty, co budu ve 2. dimenzi posílat já, neposílám.

JBL: Pokud bych měl vyjít ze slidů, předn. 10, 47/49, pak by krok 1 pravděpodobně měl bejt: <math>t_{OAS}(K(z1), z2\cdot\mu) = t_s \cdot \lceil \log (z1) \rceil + (t_d + z_2 \mu t_m) (z_1 - 1)</math>

• <math> \lceil \log (z1) \rceil</math> určuje, kolik kroků potřebuju na rozeslání informace v z1
• <math> z_2 \mu \t_m</math> mi říká, že každému uzlu v řádku posílám <math>z_2</math> paketů velikosti <math>\mu</math>
• <math> (z_1 - 1) </math> je počet uzlů, kterým to v řádku posílám.

Napište optimální algoritmus pro OAB na M(z1, z2), 2-port fullduplex, WH. Určete spodní meze počtu kroků a časovou složitost.

Základem je OAB na lineárí mřížce M(z). Ideální případ je pokud je zdroj uprostřed mřížky.
Edit: Nejsem si jistý zda by předpoklad zdroje uprostřed mřížky prošel. Pro případ náhodného umístění zdroje je nutné v rovnicích níže počítat u členu <math>t_d</math> s excentricitou místo uvedené sumy.

Algoritmus:

1. Zdrojový uzel rozdělí svůj interval na třetiny, tu ve které se nachází si ponechá a do zbylých odešle zprávu.
2. na každou stranu se rekurzivně opakuje tentýž mechanizmus

Časy:

<math>
t =
= t_s + \frac{z}{3}t_d + \mu t_m
+ t_s + \frac{z}{9}t_d + \mu t_m
+ …
+ t_s + 1 t_d + \mu t_m</math>

Součet sumy při <math>t_d</math>:

<math>s = z(\frac{1}{3} + \frac{1}{9} + … + \frac{1}{z}) = z (a_1 . \frac{1-q^n}{1-q}) = z (\frac{1}{3} . \frac{1-\frac{1}{3}^{log_3{z}}}{1-\frac{1}{3}}) = z (\frac{1}{3} . \frac{1-3^{-log_3{z}}}{\frac{2}{3}}) = z (\frac{1}{3} . \frac{1-z^{-1}}{\frac{2}{3}}) = z (\frac{1}{3} . \frac{1-\frac{1}{z}}{\frac{2}{3}}) = z (\frac{1}{3} . \frac{\frac{z}{z}-\frac{1}{z}}{\frac{2}{3}}) = z (\frac{1}{3} . \frac{\frac{z - 1}{z}}{\frac{2}{3}}) = \frac{1}{3} . \frac{z - 1}{\frac{2}{3}} = \frac{1}{3} . \frac{3(z - 1)}{2} = \frac{z-1}{2}</math>

Z toho čas: <math>t = log_3z(t_s +\mu t_m) + \frac{z-1}{2} t_d </math>

Tento výsledek využijeme pro OAB na 2D mřížce:

1. v 1. kroku pošle zdrojový uzel zprávu do všech ostatní sloupců <math>t_1 = log_3z_1(t_s +\mu t_m) + \frac{z_1-1}{2} t_d </math>
2. v další fázi se provede OAB ve všech sloupcích zároveň <math>t_2 = log_3z_2(t_s +\mu t_m) + \frac{z_2-1}{2} t_d </math>

<math>t_{OAB} = t_1+t_2 = log_3(z_1z_2)(t_s +\mu t_m) + \frac{z_1 + z_2-2}{2} t_d</math>

<math>r_{OAB} = log_3(z_1z_2)</math>

Protože se počet informovaných uzlů v každém kroku maximálně ztrojnásobí (díky 2-port), <math>\rho_{OAB} = log_3(z_1 z_2)</math> a <math>\tau_{OAB} = \rho_{OAB}(t_s + \mu t_m)+exc(s, M(z1,z2))td</math>

Odvoďte spodní meze na počet kroků, na součet délek použitých cest a na komunikační časovou složitost operace vysílání jeden-všem (OAB) ve vše-portovém 2-D toroidu K(z,z) s červím přepínáním (WH), jestliže zdrojový uzel má adresu [a1, a2] a vysílá paket o velikosti m. Předpokládejte, že přenos paketu o velikosti na vzdálenost d trvá čas t(d,µ)=ts+dtd+µtm. Popište co nejefektivnější OAB algoritmus za těchto podmínek. Odvoďte jeho počet kroků, součet délek použitých cest a komunikační zpoždění a porovnáním se spodními mezemi vyhodnoťte jeho optimalitu.

Viz skripta CZ [2006] str. 177 nebo 10. přednáška 2014/2015, slajdy 29–32

Optimální algoritmus pro tuto situaci je zobecněná diagonála a funguje optimálně pro <math>K(5^k, 5^k)</math>. Probíhá ve třech fázích:

1. Fáze 1: Zdrojový uzel doručí 1 paket do každého řádku, v <math>\normalsize \lceil \log_5 n \rceil</math> krocích;
   1. Rozděl K(n,n) do 5 horizontálních pásů přibližně stejné šířky.
   2. Pošli paket ze zdrojového pásu do všech ostatních 4 pásů v 1 kroku pomocí hranově disjunktních cest použitím XY směrování.
   3. Proveď rekurzivně totéž v každém horizontálním pásu.
2. Fáze 2: Seřaď pakety na hlavní diagonálu paralelně ve všech řádcích v 1 kroku.
3. Fáze 3: Diagonální uzly informují zbývající uzly, v <math>\normalsize \lceil \log_5 n \rceil</math> krocích;
   1. Rozděl rekurzivně K(n,n) do 5 diagonálních pásů přibližně téže šíře. Hlavní diagonála je uprostřed prvního z nich.
   2. V 1 kroku každý uzel na hlavní diagonále informuje 4 uzly na středních diagonálách ostatních 4 pásů tak, že všechny 4 cesty jsou po dvojicích hranově disjunktní.
   3. Proveď totéž rekurzivně v každém diagonálním pásu.

Na poloze zdroje nezáleží, je to uzlově symetrický graf, takže si to můžu představit tak, že zdroj je uprostřed a nic se nestane. V každém kromu se může počet informovaných uzlů nejlépe zpětinásobit:

<math>\rho_{OAB} = log_5 z^2
\tau_{OAB} = \rho_{OAB}(t_s + mt_m) + zt_d</math>

Použije se algoritmus zobecněná diagonála, taky jsem si dovolil předpokládat, že <math>z = 5^k</math>. Nicméně počítal jsem tam s logaritmama, ne s k tak by to mělo vyjít i obecně, jen se tam všude budou objevovat horní meze.

<math>r_{OAB} = log_5 z + 1 + log_5 z = log_5 z^2 + 1</math> - součet kroků první, druhé a třetí fáze → algoritmus je krokově optimální

<math>t_{OAB}</math> je trošku horší, sčítaní vypadá asi takhle:

<math>t_{OAB} =
t_s + {2 \over 5}z*t_d + t_m +
t_s + {2 \over 25}zt_d + t_m +
+ … +
t_s + 2t_d + t_m</math>

Součet řady u <math>t_d</math> vyjde <math>\frac{z - 1}{2}</math> (viz Principy řešení úloh - součty řad, je to tam vyřešeno i s obrázkem přímo pro tuto řadu), tedy celkově první fáze = <math>\log_5 z*(t_s + t_m) + \frac{z - 1}{2}*t_d</math>.

to je první fáze, třetí trvá stejně - opět dělíme na pětiny, tentokrát ale diagonální pruhy. Zajímavé je, že i vzdálenost na kterou posíláme pakety se mění stejně, takže stačí započítat první fázi 2x (klidně si to zkuste pro 25*25 toroid fakt to vyjde :)). Nakonec ještě přičteme prostřední fázi (posun na diagonály po první fázi):

<math>+ t_s + {z \over 2}t_d + t_m \\</math>

což je ta prostřední fáze. Ve té nejhůře posíláme na vzdálenost <math>z \over 2</math> . Tedy celkem:

<math>t_{OAB} = (log_5 z^2 + 1)(t_s + t_m) + ({3z \over 2}-1)t_d</math> - algoritmus je asymptoticky časově optimální

Pětina v součtu pro <math>t </math> je tam proto, že se to rekurzivně opakuje na pětkrát menším prostoru a to v obou fázích (pokaždé jsou ty pruhy pětinové jak ty horizontální tak ty vertikální, proto mi tam na pětinu vždy klesá vzdálenost mezi uzly <math>t_d</math>).

Ještě k tomu součtu délek použitých cest. Podle mě to bude diamm(K(z,z)) průměr grafu. Což je stejné jako spodní mez.

Určete dolní mez počtu kroků pro AAS na mřížce WH, plně duplexní, bez kombinování paketů.

mi-par2014-prednaska11-kko2.pdf slide 24

EDIT: Podle mě to není pravda. Ta bisekční šířka souvisí jen se spodní mezí na čas a ne na počet kroků. (viz slidy přednáška 11 slide 25).

EDIT2: Souhlasím s EDIT. Vzoreček, z kterého níže uvedené řešení vychází, je nesmysl. Pokud by platil, pak by to znamenalo, že podle přednášky 11 a slidu 25 je tau rovno 0 (protože oba členy napravo by byly přibližně rovny). Nabízím ještě níže druhé řešení, budu rád, když se jej někdo chytne a případně doplní.

Celkový počet kroků je dán propustností sítě a záleží na bisekční šířce. Pokud si představíme síť rozdělenou na 2 poloviny, pak v každé z nich je N/2 uzlů. Každý posílá zprávu každému uzlu v druhé polovině a naopak ⇒ po hranách spojujících tyto dvě poloviny musí projít <math>\lceil \frac N 2 \rceil \cdot \lfloor \frac N 2 \rfloor</math> zpráv každým směrem.

WH přepínání je necitlivé na vzdálenost, můžeme tedy předpokládat, že zprávu lze doručit z první poloviny do druhé v 1 kroku. Počet zpráv, které lze přenést v 1 kroku, je pak dán bisekční šířkou.

Počet kroků: <math>\displaystyle \varrho_{AAS}(G)=\frac { \lceil \frac N 2 \rceil \lfloor \frac N 2 \rfloor } {bw_e} </math>

Pro mřížku <math>M(z_1, z_2, …, z_k)</math> s N uzly je bisekční šířka pro <math>max_i z_i</math> sudé rovna: <math>\displaystyle \prod_{i=1}^k \frac {z_i} {max_i (z_i)}</math>

Počet uzlů je: <math>\prod_{i=1}^k z_i</math>.

<math>\displaystyle \varrho_{AAS}=\frac {\frac 1 4 \cdot {\prod_i z_i \cdot \prod_i z_i} } {\prod_i \frac {z_i} {max_i (z_i)}} = \frac {max_i (z_i) \cdot \prod_i (z_i)} 4</math>

Pro simplexní linky je to dvojnásobek.

Další možnost, jak <math>\varrho</math> odhadnout, je tato: libovolný uzel může v 1 kroku přijmout max k zpráv, kde k je portovost uzlu. Celkem jich ale musí přijmout N-1. Potřebuje tedy min <math>\varrho_{AAS}=\lceil \frac {N-1} k \rceil</math> kroků.

Je zřejmé, že první odhad je vyšší, proto ho použijeme.

Tu stejnou úvahu lze provést pro hyperkrychli <math>Q_n</math>.
Jedna varianta:<math>\varrho_{AAS}=N-1</math>
Druhá varianta:<math>\varrho_{AAS} = \frac {\frac {2^n \cdot 2^n} 4} {2^{n-1}} = 2^{n-1} = \frac N 2</math>
První varianta je vyšší a tedy lepší.

Počet kroků lze odvodit ze síťové propustnosti. Každý uzel musí svůj paket dopravit do každého jiného uzlu. Proto vezmu součet vzdáleností z každého uzlu do všech ostatních uzlů. Tento mohu vydělit všemi hranami, které mám pro tento účet k dispozici, což je m hran obousměrně, čili 2m: (viz přednášky 11, slide 24)

<math> \rho_{AAS}^N (G) = \frac{1}{2m} ( \sum_{u \neq v} dist_G(u,v) ) </math>

Abychom mohli sečíst všechny vzdálenosti mezi uzly v obecné mřížce, musíme se na problém podívat z hlediska hran, přes které při měření budeme chodit. Představme si potrhlé malé zeměměřiče, kteří běhají s dlouhatánskými krejčovskými metry a natahují je oboustranně mezi každé dva uzly, a to tak, že cestou od nižšího (z hlediska souřadnic) do vyššího vždy pomocí XYZ směrování. My se pak na situaci podíváme a posčítáme, kolik těch metrů leží v které hraně. Tím získáme hledaný součet všech vzdáleností.

Pro jednoduchost budeme měřit pouze vzdálenosti z nižšího do vyšších uzlů, a výsledek pak vynásobíme dvěma.

Zjistíme, že metry procházející hranou ve směru z₁ mohly přijít jedině z uzlů, které leží v řadě směrem k nižším souřadnicím od nižšího uzlu této hrany. Je to proto, že zatím nedošlo k jinému směrování než v dimenzi z₁. Konce těchto metrů mohou ležet jedině směrem k vyšším souřadnicím od vyššího uzlu této hrany, ale ve zbývajících n-1 dimenzích mohou být kdekoli, protože tam teprve směrování bude probíhat.

Podíváme-li se na hranu ve směru z₂, zdrojové uzly budou všechny, které mají v z₂ nižší souřadnice než počáteční uzel hrany, ale v z₁ mohou mít libovolnou souřadnici, protože tam již směrování proběhlo. Pro cíle platí totéž, co v minulém odstavci, s tím, že cílové souřadnice ve zbývajících n-2 dimenzích mohou být libovolné.

Ukáže se, že pro každou hranu v z_d nejprve vynásobíme všechny dimenze nižší než d, krát souřadnici a_d, pak souřadnici od konce (z_d - a_d) krát všechny dimenze vyšší než d.

To celé provedeme pro každou hranu v dimenzi a pro všechny dimenze a všechno sečteme a na závěr vynásobíme dvěma, protože chceme oba směry:

<math> \sum_{u \neq v} dist_G(u,v) = 2 \sum_{d=1}^n \sum_{a_1=1}^{z_1} \sum_{a_2=1}^{z_2} \cdots \cdots \sum_{a_d=1}^{z_d-1} \cdots \cdots \sum_{a_{n-1}=1}^{z_{n-1}} \sum_{a_n=1}^{z_n} (\prod_{i=1}^{d-1} z_i) a_d(z_d - a_d) (\prod_{i=d+1}^{n} z_i) </math>

Součiny můžeme vytknout před všechny součty kromě prvního, z nějž potřebují znát d:

<math> \sum_{u \neq v} dist_G(u,v) = 2 \sum_{d=1}^n (\prod_{i=1, i \neq d}^{n} z_i) \sum_{a_1=1}^{z_1} \sum_{a_2=1}^{z_2} \cdots \cdots \sum_{a_d=1}^{z_d-1} \cdots \cdots \sum_{a_{n-1}=1}^{z_{n-1}} \sum_{a_n=1}^{z_n} a_d(z_d - a_d) </math>

Nyní si všimneme, že z řady n součtů nakonec používáme proměnnou jen ze součtu přes a_d. Ostatní tedy můžeme transformovat v součin přes dimenze, které nejsou d. Takový součin už ale jednou máme, tak jej jen umocníme na druhou:

<math> \sum_{u \neq v} dist_G(u,v) = 2 \sum_{d=1}^n (\prod_{i=1, i \neq d}^{n} z_i^2) \sum_{a_d=1}^{z_d-1} a_d(z_d - a_d) </math>

To už vypadá lépe. Počet hran v n-rozměrné mřížce je:

<math> m = \sum_{d=1}^n (z_d - 1) \prod_{i=1, i \neq d}^n z_i </math>

A tedy náš závěr:

<math> \rho_{AAS}^N (G) = \frac{1}{2m} ( \sum_{u \neq v} dist_G(u,v) ) = </math>

<math> = \frac{2 \sum_{d=1}^n (\prod_{i=1, i \neq d}^{n} z_i^2) \sum_{a_d=1}^{z_d-1} a_d(z_d - a_d)}{2 \sum_{d=1}^n (\prod_{i=1, i \neq d}^n z_i) (z_d - 1)} = </math>

<math> = \frac{\sum_{d=1}^n (\prod_{i=1, i \neq d}^{n} z_i^2) \sum_{a_d=1}^{z_d-1} a_d(z_d - a_d)}{\sum_{d=1}^n (\prod_{i=1, i \neq d}^n z_i) (z_d - 1)} </math>

Příklad pro 2-D mřížku M(2,3).

<math> \rho_{AAS}^{2*3} (M(2,3)) = \frac{9*(1*1) + 4*(1*2 + 2*1)}{7} \approx 3,57 </math>

Transpozice matice <math> n\times n </math> na <math> M\left(\sqrt{p},\sqrt{p}\right) </math>, WH, XY směrování, všeportová.

Algoritmus

Obrázek: Transpozice matice na SF 2-D mřížce. Všechny submatice v řádcích jsou současně vyslány horizontálně směrem k procesorům na hlavní diagonále, které zalomí směry těchto proudů vertikálně a každá submatice doputuje do svého cílového procesoru.

Časová složitost

Časová složitost je dána dobou, kterou potřebují na výměny schvých submatic procesory v levém dolním a pravém horním rohu mřížky plus čas na transpozice submatic lokálně v procesorech.

<math> T_{2}\left(N=n^{2},p\right)=t_{s}+2\left(\sqrt{p}-1\right)\frac{n^{2}}{p}t_{m}+\mathcal{O}\left(\frac{n^{2}}{p}\right) </math>

<math> E\left(N,p\right)=\Theta\left(\frac{1}{\sqrt{p}}\right)=o\left(1\right)\,\Rightarrow\,\psi_{2}\left(N\right)=1 </math>

Důvody pro špatnou škálovatelnost jsou stejné jako u tohoto příkladu pro WH mřížku (viz příklad níže).

Transpozice matice n×n na <math>M(\sqrt p, \sqrt p)</math>, WH, XY směrování, všeportová.

★ Bylo ve zkoušce: 2013-01-16, 2014-01-20

Viz skripta CZ [2006] strana 194 | EN skripta strana 179

Při použití XY směrování nemůže více uzlů na jedné straně diagonály na stejném řádku posílat současně ⇒ posílání se na horním řádku rozpadne do <math>\sqrt p - 1</math> kroků

Časová složitost je tedy shora omezená transpozicí 1. řádku na 1. sloupec.

<math> \begin{array}{rcll} T_1(n^2, p) & = && t_s + 2 (\sqrt p -1) t_d + {n^2 \over p} t_m
&& + & t_s + 2(\sqrt p -2) t_d + {n^2 \over p} t_m
&& + &\dots & \:\: {\sqrt p - 1 \text{ kroku}}
&& + & t_s + 2 \cdot 1 t_d + {n^2 \over p} t_m
\end{array} </math>

Transpozice lokální submatice:

<math>T_2(n^2, p) = O \left( { \frac{n^2}{p}} \right)</math>

<math>s = \sqrt p -1 + \sqrt p - 2 + … + 1 = p \ll n^2 \right | = O \left ( {1\over \sqrt p t_m } \right ) = O \left ( {1 \over \sqrt p} \right ) </math> Pro libovolné <math> p </math> konstantní je <math>E = O(1)</math> -> to plyne z toho, že komunikační složka převažuje nad výpočetní => škálovatelnost je špatná ---- EDIT: Možná by se to dalo říct hnedka, že komunikační část převažuje na výpočetní (jak se píše ve skriptech): * komunikace: <math>\left(\sqrt{p}-1\right)\left(t_{s}+\sqrt{p}t_{d}+\frac{n^{2{p}t_{m}\right)\approx\left(\sqrt{p}\right)\left(\frac{n^{2}}{p}\right)\approx\Theta\left(\frac{n^{2}}{\sqrt{p}}\right) </math>

• výpočty: <math>\mathcal{O} \left ( {n^2 \over p}\right )</math>

škola s_řešením zkoušky

x