====== PDP - Vyřešené zkouškové příklady za 8 bodů ====== ====== Vnořování ====== ===== Vnoření Qn do M(2^k,2^k) ===== 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: [[par_zkouska_2011-06-30|2011-06-30]], [[par_zkouska_2014-01-20|2014-01-20]] - za 6b // ==== Řešení ==== :!://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: :?: {{:škola:předměty:mi-par:get_thumbnail.jpg?200|}} **JDU:** Opravdu to pravidlo funguje? (bez záruky, třeba neumím počítat)\\ V Q_4 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 Q_4 vrací špatný výsledek a u Q_6 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 \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}}} . Horní mez, je pro Q_{2k} (sudá dimenze) vždy polovina strany adekvátní mřížky, tedy \frac {2^k} {2} = 2^{k-1} . 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 Q_{2k}) líšícími se v i-tém bitu v tom vnoření v M. Při load = 1 se dil = \frac{2^k}{k} Mapování se nazývá Mortonova křivka, přednáška 5 / slajd 30 (2015). {{:škola:předměty:mi-par:mortonova-krivka-q_2k-do-m_k_k.png?500|}} ====== Základní paralelní algoritmy ====== ===== Paralelní prefixový součet na PRAM ===== PPS na EREW PRAM, p, lokální operace trvají čas 1, paměťové čas d > 1. Dokažte správnost. Odvoďte T(n,p), E(n,p). ★ //Bylo ve zkoušce: [[.:par_zkouska_2013-01-30|2013-01-30]], [[.:par_zkouska_2013-12-20|2013-12-20]], [[.:par_zkouska_2012-01-17|2012-01-17]]6b, část řešení [[.:par_zkouska_2013-01-09|2013-01-09]] a [[par_zkouska_2015-01-06|2015-01-06 (za 6b)]] // ==== Řešení ==== :!://Viz skripta CZ [2006] str. 99 nebo EN [2009] str. 93// [[https://edux.fit.cvut.cz/courses/MI-PAR.2/_media/lectures/mi-par2014-prednaska7-fundamental.pdf|mi-par2014-prednaska7-fundamental.pdf]] slide 5 p=N: 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; } {{.:vyřešené_příklady:pps_pram.png?200|}} __Důkaz správnosti:__ Výpočet je založen na tom, že v paralelním kroku j sdílená paměťová bunka M[k] naakumulovala sumu hodnot M[k - 2^{j+1}+1, ..., k-1, k] * v kroku 0 (první krok, jen indexovaný od 0): obsahuje M[k, k-1] * v kroku 1: obsahuje M[k, k-1, k-2, k-3] * ... Elementární krok pro j=0 platí Indukční krok: Nechť platí pro j-1, ukážu, že platí pro j\\ => na začátku kroku j-1 je tedy v M[k, k-1, ... , k-2^{j-1} + 1] v 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]\\ => M[k] + M[k-2^{j-1}] = M [k, k-1 , ... , k - 2^{j-1} + 1, k-2^{j-1}, ... , k - 2^j + 1] \\ => což je stav na začátku fáze j => cbd. __Škálovatelnost:__ Pro p probíhá výpočet takto: - Procesory si rozdělí čísla do intervalů S_i o počtu prvků N \over p. Každý P_i provede prefixový součet ve svém intervalu. Každý interval se zredukuje na 1 číslo. - Provede se paralelní prefixový součet nad p čísly. - Každý P_i pošle výsledek PPS procesoru P_{i+1}, každý P_{i+1} přijme výsledek od P_i - Přičte ke všem hodnotám ve svém intervalu a zapíše vše do M. 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) C(N,p) = O(N + p \cdot \log p) E(N,p) = \Omega(\frac{N}{N + p \cdot \log p}) (Celkový paralelní čas T(N,p) 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 SF CBT_log(p) ===== Segmentový PPS na nepřímém CBT_{log(p)}, SF, dokázat korektnost, spočítat T(n,p). ★ //Bylo ve zkoušce: [[par_zkouska_2012-01-24|2012-01-24]] a [[par_zkouska_2012-12-18|2012-12-18]] a [[par_zkouska_2013-01-02|2013-01-02]]// ==== Řešení ==== 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 CBTlog p se chová takto: {{:škola:předměty:mi-par:screen_shot_2014-12-30_at_16.47.31.png?nolink&300|}}{{:škola:předměty:mi-par:screen_shot_2014-12-30_at_16.47.33.png?nolink&300|}} 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). T(n,p) = O(n/p + log p) Binární operace pro segmentaci, kterou je nahrazena původní asociativní operace, má přesně tento předpis: {{:škola:předměty:mi-par:screen_shot_2014-12-30_at_16.47.50.png?nolink&300|}} 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.) {{:škola:předměty:mi-par:screen_shot_2014-12-30_at_17.20.00.png?nolink&500|}} 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í. ====== Kolektivní komunikační algoritmy ====== ===== Multicast na 2D mřížce ve WH síti ===== Uvažujte 2-D mřížku M(z_{x},z_{y}) s plně duplexními linkami a 1-port. procesory, jejichž směrovače realizují WH XY směrování. Odvoďte spodní mez \rho_{MC} na počet kroků pro multicast ze zdroje v obecném uzlu s a s cílovou skupinou uzlů S. Pak obecně popište krokově opt. algoritmus pro tento problém a dokažte jeho korektnost. Poté aplikujte tento algoritmus na M(5,5) na obrázku. (pozn.: obrázek = mřížka 5x5, zvýrazněný 1 zdrojový a několik cílových uzlů). ★ //Bylo ve zkoušce: [[.:par_zkouska_2014-01-13|2014-01-13]], [[.:par_zkouska_2012-01-03|2012-01-03]], [[.:par_zkouska_2013-01-09|2013-01-09]] (s YX směrováním), [[.:par_zkouska_2013-01-23|2013-01-23]], [[.:par_zkouska_2015-02-05|2015-02-05]] a [[.:par_zkouska_2016-01-15|2016-01-15]]// ==== Řešení ==== :!://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: 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 Kde \mathcal{M} 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: \left|\mathcal{M}\right|=7 , tedy \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}} . :!: 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 {{:škola:předměty:mi-par:mc2dmwh.png?600|}} Jiný pohled na krokování algoritmu: {{https://i.imgur.com/7nGkbwX.png?600|}} 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. ===== AAB na 2D toroidu, SF, všeportový, nekombinující ===== Odvoďte **spodní meze** na počet kroků \rho_{AAB}(K(z_1,z_2)) a na komunikační zpoždění \tau_{AAB}(K(z_1,z_2), \mu) pro **nekombinující vysílání všichni všem (AAB)** na **vše-portovém plně-duplexním 2-D toroidu** K(z_1,z_2), 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 \mu mezi 2 uzly ve vzdálenosti //d// trvá t(d, \mu) = t_s + \mu d t_m. Popiště co nejlepší algoritmus pro tuto komunikační operaci za těchto podmínek. **Odvoďte** jeho **počet kroků** r_{\rm AAB}(K(z_1,z_2)) a **časovou složitost** t_{\rm AAB} (K(z_1,z_2), \mu) a vyslovte tvrzení o jeho optimalitě. ==== Řešení ==== //[11. přednáška 14/15, slajdy 19-21]// Spodní meze: Nechť N=z_1 z_2. \rho = \left\lceil{N - 1\over d}\right\rceil ... 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//. \\ \tau = \rho * (t_s +\mu t_m) ... 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 d = 4 větví o délkách l = \left\lceil{N - 1\over d}\right\rceil. Všechny paralelní ''OAB'' skončí současně, až zpráva dojde na konec větve; tedy po //l// krocích. r_{\rm AAB} = \left\lceil{N - 1\over 4}\right\rceil t_{\rm AAB} = (t_s + \mu t_m) * \left\lceil{N - 1\over 4}\right\rceil 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 2D toroidu ===== OAS na toroidu K(z_1, z_2), 1-port, WH, kombinující, bod (a_1,a_2), 1 paket velikosti \mu , t=t_s + d \cdot t_d + \mu t_m. Efektivnost algoritmu, \rho, \tau, r , t, porovnat optimalitu. ==== Řešení ==== OAS -> jeden uzel rozesílá z_1 \cdot z_2 - 1 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í => \rho_{OAS} (K(z_1,z_2)) = \log (z_1 z_2) \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 Základní kámen je OAS na 1D toroidu T(z) \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} 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 \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) r_{OAS} = \log z Algoritmus pro 2D toroid se skládá z fáze - OAS v řádku se zdrojem => každému uzlu pošlu informaci pro celý sloupec \right t_1 = (\log z_1) t_s + (z_1-1)t_d + (z_1 z_2 -1)\mu t_m - OAS ve sloupcích paralelně \right t_2 = (\log z_2) t_s + (z_2-1)(t_d + \mu t_m) 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 r_{OAS} = \log z_1 + \log z_2 = \log (z_1 \cdot z_2) => algoritmus je co do počtu kroků asymptoticky optimální. Z hlediska časové složitosti je také optimální (\tau_{OAS} = t_{OAS} ) JDU: ad fáze 1 v 2D toroidu: součet u \mu t_m mi přijde nějaký divný. Vyšlo mi z_1z_2-z_2. V kroku pošlu vždy \frac{z_1z_2}{2}, \frac{z_1z_2}{4}, ... 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: t_{OAS}(K(z1), z2\cdot\mu) = t_s \cdot \lceil \log (z1) \rceil + (t_d + z_2 \mu t_m) (z_1 - 1) * \lceil \log (z1) \rceil určuje, kolik kroků potřebuju na rozeslání informace v z1 * z_2 \mu \t_m mi říká, že každému uzlu v řádku posílám z_2 paketů velikosti \mu * (z_1 - 1) je počet uzlů, kterým to v řádku posílám. ===== Optimální algoritmus pro OAB na M(z1, z2), 2-port fullduplex, WH ===== 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. ==== Řešení ==== 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 t_d s excentricitou místo uvedené sumy. {{.:vyřešené_příklady:oab_na_m1.png|}} **Algoritmus:** - 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. - na každou stranu se rekurzivně opakuje tentýž mechanizmus **Časy:** \\ 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 Součet sumy při t_d: 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} Z toho čas: t = log_3z(t_s +\mu t_m) + \frac{z-1}{2} t_d **Tento výsledek využijeme pro OAB na 2D mřížce:** - v 1. kroku pošle zdrojový uzel zprávu do všech ostatní sloupců t_1 = log_3z_1(t_s +\mu t_m) + \frac{z_1-1}{2} t_d - v další fázi se provede OAB ve všech sloupcích zároveň t_2 = log_3z_2(t_s +\mu t_m) + \frac{z_2-1}{2} t_d 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 r_{OAB} = log_3(z_1z_2) Protože se počet informovaných uzlů v každém kroku maximálně ztrojnásobí (díky 2-port), \rho_{OAB} = log_3(z_1 z_2) a \tau_{OAB} = \rho_{OAB}(t_s + \mu t_m)+exc(s, M(z1,z2))td ===== OAB ve všeportovém 2D toroidu K(z,z), WH===== 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. ==== Řešení ==== :!:// Viz skripta CZ [2006] str. 177 nebo 10. přednáška 2014/2015, slajdy 29–32// === Algoritmus === Optimální algoritmus pro tuto situaci je **zobecněná diagonála** a funguje optimálně pro K(5^k, 5^k). Probíhá ve třech fázích: - **Fáze 1:** Zdrojový uzel doručí 1 paket do každého řádku, v \normalsize \lceil \log_5 n \rceil krocích; - Rozděl **K(n,n)** do **5 horizontálních pásů** přibližně stejné šířky. - 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í**. - Proveď rekurzivně totéž v každém horizontálním pásu. - **Fáze 2:** Seřaď pakety na //hlavní diagonálu// paralelně ve všech řádcích v 1 kroku. - **Fáze 3:** Diagonální uzly informují zbývající uzly, v \normalsize \lceil \log_5 n \rceil krocích; - 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. - 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í**. - Proveď totéž rekurzivně v každém diagonálním pásu. {{https://i.imgur.com/kpgghKc.png?600|}} === Složitost === 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: \rho_{OAB} = log_5 z^2 \\ \tau_{OAB} = \rho_{OAB}(t_s + mt_m) + zt_d Použije se algoritmus **zobecněná diagonála**, taky jsem si dovolil předpokládat, že z = 5^k. 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. r_{OAB} = log_5 z + 1 + log_5 z = log_5 z^2 + 1 - součet kroků první, druhé a třetí fáze -> algoritmus je krokově optimální t_{OAB} je trošku horší, sčítaní vypadá asi takhle: 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 Součet řady u t_d vyjde \frac{z - 1}{2} (viz [[https://www.fit-wiki.cz/%C5%A1kola/p%C5%99edm%C4%9Bty/mi-par/principy_%C5%99e%C5%A1en%C3%AD_%C3%BAloh?&#sou%C4%8Det_%C5%99ady|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 = \log_5 z*(t_s + t_m) + \frac{z - 1}{2}*t_d. 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): + t_s + {z \over 2}t_d + t_m \\ což je ta prostřední fáze. Ve té nejhůře posíláme na vzdálenost z \over 2 . Tedy celkem: t_{OAB} = (log_5 z^2 + 1)(t_s + t_m) + ({3z \over 2}-1)t_d - algoritmus je asymptoticky časově optimální Pětina v součtu pro t 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 t_d). 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. ===== Počet kroků AAS na mřížce ===== Určete dolní mez počtu kroků pro AAS na mřížce WH, plně duplexní, bez kombinování paketů. [[https://edux.fit.cvut.cz/courses/MI-PAR.2/_media/lectures/mi-par2014-prednaska11-kko2.pdf| mi-par2014-prednaska11-kko2.pdf]] slide 24 ==== Řešení ==== :!: 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 \lceil \frac N 2 \rceil \cdot \lfloor \frac N 2 \rfloor 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ů: \displaystyle \varrho_{AAS}(G)=\frac { \lceil \frac N 2 \rceil \lfloor \frac N 2 \rfloor } {bw_e} Pro mřížku M(z_1, z_2, ..., z_k) s N uzly je bisekční šířka pro max_i z_i sudé rovna: \displaystyle \prod_{i=1}^k \frac {z_i} {max_i (z_i)} Počet uzlů je: \prod_{i=1}^k z_i. \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 Pro simplexní linky je to dvojnásobek. Další možnost, jak \varrho 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 \varrho_{AAS}=\lceil \frac {N-1} k \rceil kroků. Je zřejmé, že první odhad je vyšší, proto ho použijeme. ---- Tu stejnou úvahu lze provést pro hyperkrychli Q_n.\\ Jedna varianta:\varrho_{AAS}=N-1\\ Druhá varianta:\varrho_{AAS} = \frac {\frac {2^n \cdot 2^n} 4} {2^{n-1}} = 2^{n-1} = \frac N 2\\ První varianta je vyšší a tedy lepší. ---- ==== Řešení 2 ==== 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) \rho_{AAS}^N (G) = \frac{1}{2m} ( \sum_{u \neq v} dist_G(u,v) ) 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 z1 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 z1. 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 z2, zdrojové uzly budou všechny, které mají v z2 nižší souřadnice než počáteční uzel hrany, ale v z1 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 zd nejprve vynásobíme všechny dimenze nižší než d, krát souřadnici ad, pak souřadnici od konce (zd - ad) 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: \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) Součiny můžeme vytknout před všechny součty kromě prvního, z nějž potřebují znát d: \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) Nyní si všimneme, že z řady n součtů nakonec používáme proměnnou jen ze součtu přes ad. 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: \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) To už vypadá lépe. Počet hran v n-rozměrné mřížce je: m = \sum_{d=1}^n (z_d - 1) \prod_{i=1, i \neq d}^n z_i A tedy náš závěr: \rho_{AAS}^N (G) = \frac{1}{2m} ( \sum_{u \neq v} dist_G(u,v) ) = = \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)} = = \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)} **Příklad pro 2-D mřížku M(2,3).** \rho_{AAS}^{2*3} (M(2,3)) = \frac{9*(1*1) + 4*(1*2 + 2*1)}{7} \approx 3,57 ====== Lineární algebra ====== ===== Transpozice na 2D mřízce, SF ===== Transpozice matice n\times n na M\left(\sqrt{p},\sqrt{p}\right) , WH, XY směrování, všeportová. ==== Řešení ==== **Algoritmus** {{:škola:předměty:mi-par:transpozice-matice-na-m-sf.png?450|}} 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. 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) E\left(N,p\right)=\Theta\left(\frac{1}{\sqrt{p}}\right)=o\left(1\right)\,\Rightarrow\,\psi_{2}\left(N\right)=1 Důvody pro špatnou škálovatelnost jsou stejné jako u tohoto příkladu pro WH mřížku (viz příklad níže). ===== Transpozice matice na 2D mřížce ===== Transpozice matice n×n na M(\sqrt p, \sqrt p), WH, XY směrování, všeportová. ★ //Bylo ve zkoušce: [[par_zkouska_2013-01-16|2013-01-16]], [[.:par_zkouska_2014-01-20|2014-01-20]]// ==== Řešení ==== :!://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 \sqrt p - 1 kroků {{:škola:předměty:mi-par:wh_2d_m.png|}} Časová složitost je tedy shora omezená transpozicí 1. řádku na 1. sloupec. \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} Transpozice lokální submatice: T_2(n^2, p) = O \left( { \frac{n^2}{p}} \right) s = \sqrt p -1 + \sqrt p - 2 + ... + 1 = {{\sqrt p - 1 + 1} \over 2} (\sqrt p - 1) = {\sqrt p \over 2} (\sqrt p -1) T(n^2, p) = (\sqrt p - 1)(t_s + \sqrt p t_d + {n^2 \over p} t_m) + \mathcal{O} \left ( {n^2 \over p}\right ) SU(n^2) = O(n^2) \\ E(n^2,p) = { {n^2} \over {(\sqrt p -1 )(p \cdot t_s + p^{3/2} t_d + n^2 t_m) + O(n^2) } } \approx { {n^2} \over {p \sqrt p t_s + p^2 t_d + n^2 \sqrt p t_m + n^2} } \approx \\ \approx \frac{ n^2 }{ n^2 \left( \frac{p \sqrt p}{n^2} t_s + \frac{p^2}{n^2} t_d + \sqrt p t_m + 1 \right) } = \left | p \ll n^2 \right | = O \left ( {1\over \sqrt p t_m } \right ) = O \left ( {1 \over \sqrt p} \right ) Pro libovolné p konstantní je E = O(1) -> 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: \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) * výpočty: \mathcal{O} \left ( {n^2 \over p}\right ) {{tag>škola s_řešením zkoušky}} x