Differences

This shows you the differences between two versions of the page.

--- users:martin.kocicka:pdp:8b [2017/06/13 10:18] – vytvořeno martin.kocicka
+++ users:martin.kocicka:pdp:8b [2017/06/13 11:01] (current) – martin.kocicka
@@ Line 1: / Line 1: @@
 ====== PDP - Vyřešené zkouškové příklady za 8 bodů ======
-====== Paralelní architektury a výpočetní modely (2. přednáška)======
+====== Vnořování ======
-===== Polylogaritmicky složitá simulace prioritního CRCW PRAM na paměťovém EREW PRAM =====
-Popište polylogaritmicky složitou simulaci prioritního CRCW PRAM algoritmu na <math>\left ( p+m \right )</math> paměťovém EREW PRAM, <math>m </math> je paměťová složitost algoritmu.
-★ //Bylo ve zkoušce: [[.:par_zkouska_2012-01-10|2012-01-10]]//
-==== Řešení ====
-:!://Viz skripta
-CZ [2006] str. 45, věta 3.13;
-EN [2009] str. 27//
-Počet procesorů na <math>EREW</math> je <math>p' = max(m',p)</math>, kde <math>m' = m</math>. Navíc potřebujeme pomocné pole <math>A </math> o <math>p </math> buňkách.
-Rozlišíme operace //READ//, //WRITE// a lokální výpočet. Simulace lokálního výpočtu je pro <math>p' = max(m',p)</math> v <math>O(1)</math> krocích.
-Operace //READ// a //WRITE// řešíme takto:
-  - Chce-li procesor <math>p_{i}</math> přistupovat k <math>M[j]</math>, potom <math>p_{i}'</math> zapíše do <math>A[i]</math> dvojici <math>(j,i)</math>.
-  - Všechny procesory <math>p_{i}'</math> <math>(1\leq i \leq p)</math> setřídí pomocné pole <math>A </math> lexikograficky (pomocí algoritmu //Coelův mergesort// <math>\rightarrow O \left ( log p \right )</math> ).
-  - Každý procesor <math>p_{i}'</math> <math>(2 \leq i \leq p)</math> se podívá do <math>A[i]</math> a do <math>A[i-1]</math> a pokud mají obě dvojice stejnou první hodnotu (nebo je první hodnota u obou rovna 0), zapíše ke dvojici <math>A[i]</math> navíc hodnotu <math>s = 0</math>, jinak <math>s = 1</math>.
-  - Další kroky se liší pro //READ// a //WRITE//:
-    * //WRITE//:
-      - procesor <math>p_{i}'</math> zapíše obsah <math>A[i] = (j,k,s)</math> do <math>A[k]</math>
-      - každý procesor <math>p_{i}'</math>, který žádal o přístup k paměti přečte <math>A[i] = (j,i,s)</math>. Je-li <math>s=1</math>, vyhrál a může zapisovat.
-    * //READ//:
-      - <math>p_{i}'</math> přečte <math>A[i] = (j,k,s)</math>. Je-li <math>s=1, p_{i}'</math> přečte <math>M'[j]</math> a zapíše místo <math>s \rightarrow A[i] = (j,k,v_{j})</math>.
-      - hodnota <math>v_{j}</math> se takto distribuuje operací binárního zdvojování všem uzlům vpravo, které mají stejné <math>j</math> a nulové <math>s</math>.
-      - provede se permutace <math>A[i] = (j,k,v_{j})</math> do <math>A[k]</math>
-      - každý procesor přečte <math>A[i]</math>
-=> Složitost je daná operací řazení <math>O \left ( log p \right )</math> a distribucí přečtené hodnoty <math> O \left ( log p \right )</math>, ostatní operace mají složitost <math> O \left ( 1 \right )</math>
-**=> Jeden krok simulujeme se zpomalením** <math>O \left ( log p \right )</math>.
-===== Polylogaritmicky složitá simulace prioritního CRCW PRAM na paměťovém EREW PRAM =====
-Popište polylogaritmicky složitou simulaci prioritního CRCW PRAM algoritmu na <math>\left ( p*m \right )</math> paměťovém EREW PRAM, <math>m </math> je paměťová složitost algoritmu.
-★ //Bylo ve zkoušce: [[.:par_zkouska_2013-01-23|2013-01-23]] //
-==== Řešení ====
-:!://Viz skripta
-CZ [2006] str. 45, věta 3.11;
-EN [2010] str. 27, theorem 2.16//
-[[https://edux.fit.cvut.cz/courses/MI-PAR.2/_media/lectures/mi-par2014-prednaska2-pararch.pdf|mi-par2014-prednaska2-pararch.pdf]] slide 26
-FIXME
-===== Simulace PRAMu na PRAMu s menší pamětí =====
-PRAM(n,p) skončí výpočet <RLW>^t s p procesory za T = 3t. Za jakou dobu doběhne výpočet simulovaný na PRAM(m,p') kde m<n a odvoďte p' a T. Za jakých okolností.
-★ //Bylo ve zkoušce: [[.:par_zkouska_2014-02-12|2014-02-12]] //
-==== Řešení ====
-[[https://edux.fit.cvut.cz/courses/MI-PAR.2/_media/lectures/mi-par2014-prednaska2-pararch.pdf|mi-par2014-prednaska2-pararch.pdf]] slide 24
-FIXME
-====== Vnořování (5. přednáška)======
 ===== Vnoření Qn do M(2^k,2^k) =====
@@ Line 109: / Line 45: @@
 {{:škola:předměty:mi-par:mortonova-krivka-q_2k-do-m_k_k.png?500|}}
+====== Základní paralelní algoritmy ======
-====== Směrování, techniky přepínání a zablokování (6. přednáška)======
-===== Konstrukce směrovací funkce v obecném G =====
-Je zadán obecný jednoduchý neorientovaný souvislý N-uzlový graf G. Popište algoritmus konstrukce směrování funkce odolné vůči zablokování (deadlock-free) na přímé a propojovací síti a topologii grafu G s plně duplexními kanály a všeportovými směrovači a uzly s označením 1..n. Konstrukci popište nejprve v obecné a odvoďte důkaz okolností směrovací funkce proti zablokování a pak teprve demonstrujte na příkladu sítě na obrázku vyslovte tvrzení o minimalitě této směrovací funkce.
-★ //Bylo ve zkoušce: [[par_zkouska_2015-01-13|2015-01-13]], [[par_zkouska_2013-05-21|2013-05-21]], [[par_zkouska_2012-05-18|2012-05-18]], [[.:par_zkouska_2011-05-19|2011-05-19]]//
-==== Řešení ====
-[[https://edux.fit.cvut.cz/courses/MI-PAR.2/_media/lectures/mi-par2014-prednaska6-switching.pdf|mi-par2014-prednaska6-switching.pdf]] slide 33
-Lze použít algoritmus Nahoru* / Dolů* z přednášky 6 2015/16, slajd 33.
-V grafu bychom si průchodem do šířky od zvoleného uzlu vytvořili kostru. Všechny uzly by byly v nějaké hladině vůči kořenu. Uzly mají nějaké svoje číselné ID. Hrana, která vede mezi uzly, které nejsou ve stejné hladině, vede do uzlu, co je v nižší hladině. Hrana mezi uzly ve stejné hladině vede k uzlu s nižším id.
-Důkaz je uvedený v přednášce a nese se v tom duchu, že nad kořenem už nic není, že každý uzel má jednoznačné ID a že v grafu neexistuje orientovaná kružnice.
-Ze script: Jakmile se někdy otočíme dolů, už se nesmíme otočit nahoru. Toto pravidlo zaručí, že v grafu kanalových závislostí nemohou existovat cykly.
-:!: Dodatek by voho: Já sem jen hodím pseudokód Up*/Down*, ať ho nemusíte hledat...
-<code>
-: očísluj uzly v grafu
-: vytvoř kostru grafu G průchodem do šířky od nějakého uzlu r
-: orientuj hrany
-    a) hrany v kostře: od potomka k předkovi
-    b) zbývající hrany (mimo kostru): orientuj směrem k uzlu, který je nejblíž kořenu, pokud je takových uzlů více, potom k tomu s nižším ID
-</code>
-A ještě pár obrázků:
-) vytvoří se kostra pomocí BFS z nějakého vybraného uzlu (zde 8) (čísla u hran jsou čísla kroků, ve kterém byla do kostry přidána); pořadí expanze bylo dáno ID
-{{.:vyřešené_příklady:updown_1.png|}}
-Hrany v kostře se orientují od potomků k předkovi.
-{{:škola:předměty:mi-par:vyřešené_příklady:updown_2.jpg|}}
-Ostatní hrany se orientují od vyššího ID k nižšímu.
-{{.:vyřešené_příklady:updown_3.png|}}
-Pozn. by Štefan: ten spodní obrázek je špatně! dle českých skript str. 148 se strana orientuje směrem k uzlu blíže kořenu (tak aby případná cesta byla kratší), pokud je těchto uzlů více, pak zvolí ten s menším ID, tedy od 3 -> 5 a 10 -> 11
-Edit: Nesouhlasím se Štefanem. Česká skripta nemám a možná je v nich chyba, ale podle aktuálních slidů a podle selského rozumu je správně postup na obrázku. Orientace hran je definována takto: Je-li hloubka koncových uzlů v kostře různá, orientace je směrem k menší hloubce. Je-li stejná, orientace je k uzlu s menším ID. To je vše, žádné další kritérium tam není.
-Edit 2016: souhlasim se štefanem, zjednodušení podle logiky z editu výše = 2 body
-Směrovací funkce R je definována takto:\\
-Dovolené jsou pouze cesty, které se skládají z 0 nebo více linek směrem nahoru, následovaných 0 nebo více linkami směrem dolů. (CZ skripta 147-148)
-Ešte k tvrdeniu o minimalite: Tvrdík mi povedal, že to nie je minimálne smerovanie.
-Edit: Jasně že není minimální, nutíme směrovací funkci, aby zahazovala nelegální trasy a chodila jinudy, tím se cesta snadno prodlouží.
-**Edit: Vysledek z diskuse - obrazek neni spatne.**
-Edit2: Pokud platí směrování směrem do nižší hloubky pak je uzel 10 v hloubce 4 a uzel 11 v hloubce 3 tzn. hrana je opačně, stejně tak uzel 5 je v hloubce 1 a uzel 3 v hloubce 2 tedy opět opačně. Tedy obrázek je špatně.
-**EDIT3: Souhlas s Edit2. Obrázek možná bude fungovat, ale není vystavěn dle algoritmu z přednášek, kde se píše: "smměrem ke kořenu r pokud depthT(u) != depthT(v)"**
-EDIT4: Algoritmus dle skript neni potreba, staci popsat jak se tvori DAG z grafu.
-EDIT5: Když si obrázek překreslíte do stromu, tak to vypadá takto. Pokud zachováváme směrování k nižší hloubce, tak je 3. obrázek špatně
-EDIT5 by vd 06/16: Myslím, že slajd hovoří jasně: hrana se orientuje od větší k menší hloubce (tj. směrem ke kořenu). Pokud mají dva kořeny stejnou hloubku, hrana se orientuje směrem k uzlu s menším ID. Poslední obrázek je tedy **špatně**.
-Zde je opravený obrázek, modře je kostra grafu:
-{{https://i.imgur.com/inWJwVe.png?650|}}
-{{:škola:předměty:mi-par:smerovani_g.jpg?200|}}
-====== Základní paralelní algoritmy (7. přednáška)======
-===== Algoritmus pro očíslování listů stromu na eulerovské cestě =====
-Popište EREW PRAM algoritmus pro výpočet **pořadí listů** při průchodu do **hloubky** //n//-uzlového **stromu** //S//. Algoritmus vypočte počet listů //q// a výsledkem bude pole <math>List[1,\ldots,q]</math>. Strom //S// je reprezentován jako eulerovský, čili má <math>m = 2n - 2</math> orientovaných hran, je reprezentován **polem uzlů**, které mají odkazy na cyklické seznamy svých hran a každá hrana má odkaz na své opačně orientované **dvojče**. Předpokládejte, že je již zkonstruována **eulerovská cesta** a je uložena v **poli** <math>EA[1\ldots m]</math>, kde <math>EA[i]</math> je //i//-tá **hrana** této cesty. Odvoďte asymptotický paralelní čas <math>T(m,p)</math> pro <math>1 \leq p \leq m</math> tohoto algoritmu.
-==== Řešení ====
-=== Algoritmus ===
-Uvažujme počet hran stromu **m = 2n-2** a počet procesorů **p = m**.
-Část A:
-<code c>
-  for i in 0..m-1 do_in_parallel {
-    maList[i] = 0
-    if (EA[i].Dvojče = EA[i+1]) {
-      // Jsou-li dvě po sobě jdoucí hrany dvojčaty, musí být mezi nimi list.
-      maList[i] = 1
-    }
-  }
-</code>
-Poté provést paralelní prefixový součet hodnot //maList// ze všech procesorů do pole //X// o //m// prvcích. Hodnota //X[m-1]// je hledané //q//.
-Část B:
-<code c>
-  for i in 0..m-1 do_in_parallel {
-    if (maList[i] = 1) {
-      List[ X[i] -1 ] = EA[i].endNode
-  }
-</code>
-Stejný kód zapsaný v alternativní syntaxi:
-<code python>
-# edges - pole hran EA [pořadové číslo hrany => hrana]
-# leafs - pole listů [pořadové číslo listu => uzel]
-def countLeafs(edges) {
-    hasLeaf = array(edges.length);  # pole příznaků, zda je koncový uzel hrany list
-    leafPS = array(edges.length);   # pole hasLeaf prohnané PPS
-    for i in range(0, edges.length -1) do_in_parallel {
-        hasLeaf[i] = 0;
-        # jsou-li po sobě jdoucí hrany dvojčaty, je mezi nimi list
-        if (edges[i].sibling == edges[i+1]) {
-            hasLeaf[i] = 1;
-        }
-    }
-    doPPS(hasLeaf, leafPS);  # proveď PPS nad polem hasLeaf do pole leafPS
-    leafsCount = leafPS[-1];
-    leafs = array(leafsCount);
-    for i in range(0, edges.length -1) do_in_parallel {
-        if (hasLeaf[i] == 1) {
-            leafs[ leafPS[i] -1 ] = edges[i].endNode;
-        }
-    }
-    return leafs, leafsCount;
-}
-</code>
-Každý procesor má hodnotu //list//. Mohou to být buď jako lokální proměnné, nebo mohou být uloženy v hlavní paměti v polích o velikosti //m// (každý procesor pracuje pouze se svým prvkem pole).
-=== Složitost ===
-Máme pouze **p** procesorů a <math>\frac{m}{p}</math> hran na procesor. Celkový čas je součet časů části A, PPS a části B.
-<math>T(m,p) = \Theta\left(\frac{m}{p}\right) + \Theta\left(\frac{m}{p} + \log{}p\right) + \Theta\left(\frac{m}{p}\right)  \approx \Theta\left(\frac{m}{p} + \log{}p\right)</math>
-=== Alternativní řešení ===
-(klimic) Já bych na to šel jinak:
-  * List <=> Velikost podstromu = 1 (viz algoritmus v přednášce/skriptech)
-  * Udělám preorder číslování (viz algoritmus v přednášce/skriptech), akorát 1 dám jen hranám jdoucím do listu
-  * Zapsání výsledného pole pak bude:
-  for all xy in EA do_in_parallel:
-  {
-      if (xy.Direction = Down && SubtreeSize[y] == 1) List[y] = EA[xy].Weight;
-  }
-===== PRAM algoritmus číslování uzlů podstromu postorder =====
-**Eulerův strom a jeho reprezentaci polem, mám hotovou Eulerovu cestu.**
-★ //Bylo ve zkoušce: [[par_zkouska_2012-06-26|2012-06-26]], [[par_zkouska_2014-02-04|2014-02-04]]//
-==== Řešení ====
-<code c>
-  for každou hranu e do_in_parallel
-     if (Rank[e] < Rank[EL[e].Dvojče]) {
-        Dir[e] = F; Weight[e] = 0;
-     }; else {
-        Dir[e] = R; Weight[e] = 1;
-     }
-  call PPS na pole Weight[];
-  for každou hranu <xy> do_in_parallel
-     if (Dir[<xy>] = R) {
-        Postorder[x] = Weight[<xy>] -1;
-  }
-  Postorder[root]=n-1; /* nikdy nedochází k úpravě kořene, proto musím upravit */
-</code>
-Stejný kód v alternativní syntaxi:
-<code python>
-# eulerPath - pole EA s ukazateli na hrany v AA v pořadí Eulerovské cesty
-# postorder - pole [číslo uzlu => pořadí postorder]
-def buildPostorder(eulerPath) {
-    weights = array(eulerPath.length);
-    postorder = array( eulerPath.length/2 +1 );
-    for edge in eulerPath do_in_parallel {
-        if (edge.rank < edge.sibling.rank) {
-            # hrana jdoucí směrem od kořene
-            edge.dir = 'F'; weights[ edge ] = 0;
-        else {
-            # dvojče jdoucí směrem ke kořeni
-            edge.dir = 'R'; weights[ edge ] = 1;
-        }
-    }
-    doPPS(weights);  # proveď PPS nad polem weights
-    for edge in eulerPath do_in_parallel {
-        if (edge.dir == 'R') {
-            postorder[ edge.startNode ] = weights[ edge ] -1;
-        }
-    }
-    postorder[ROOT] = eulerPath.length/2  # kořen je posledním uzlem
-    return postorder;
-}
-</code>
-{{.:vyřešené_příklady:pram_postorder.gif?220|Průchod Postorder a PPS}}
-Vzestupná_hrana.váha = 1, sestupná_hrana.váha = 0. Řešením je spočítat PPS nad vzestupnými hranami. Hrany jsou uloženy v poli ve směru průchodu Eulerovou kružnicí. Na konci výpočtu se musí zvlášť dopočítat kořen, protože z něj nevede žádná vzestupná hrana.
-Počet kroků je odvozen v následujícím příkladu (PRAM Preorder), zde vychází stejně.
-byl příklad za 6 b. 2 za alg, 2 za čas složitost viz příklad níže a dva za popis datových struktur.
-===== EREW PRAM algoritmus pro pořadí uzlů v průchodu preorder  =====
-**Popište EREW PRAM algoritmus pro výpočet pořadí uzlů při průchodu preorder (kořen, levý, pravý) všech **<math>n </math>** uzlů eulerovského stromu **<math>T </math>**. Výsledkem bude pole **<math>PRE(1,...,n)</math>**. Eulerovský strom **<math>T</math>** má **<math>m = 2n-2</math>** hran. Předpokládejte klasický model PRAM, kde lokální operace READ a WRITE trvají čas 1.**
-==== Řešení ====
-=== Algoritmus ===
-Algoritmus pro **p = n** má následující podobu:
-<code c>
-  for all e in EA do_in_parallel {
-    if (Rank[e] < Rank[EL[e].Dvojče] {
-      Dir[e] = 'F'; Weight[e] = 1;
-    } else {
-      Dir[e] = 'R'; Weight[e] = 0;
-    }
-  }
-  call PPS nad polem Weight[];
-  for all <xy> in EA do_in_parallel {
-    if (Dir[<xy>] == 'F')
-      Preorder[y] = Weight[<xy>];
-  }
-  Preorder[root] = 0;
-</code>
-Stejný kód zapsaný v alternativní syntaxi:
-<code python>
-# eulerPath - pole EA s ukazateli na hrany v AA v pořadí Eulerovské cesty
-# preorder - pole [číslo uzlu => pořadí preorder]
-def buildPreorder(eulerPath) {
-    weights = array(eulerPath.length);
-    preorder = array( eulerPath.length/2 +1 );
-    for edge in eulerPath do_in_parallel {
-        if (edge.rank < edge.sibling.rank) {
-            # hrana jdoucí směrem od kořene
-            edge.dir = 'F'; weights[ edge ] = 1;
-        else {
-            # dvojče jdoucí směrem ke kořeni
-            edge.dir = 'R'; weights[ edge ] = 0;
-        }
-    }
-    doPPS(weights);  # proveď PPS nad polem weights
-    for edge in eulerPath do_in_parallel {
-        if (edge.dir == 'F') {
-            preorder[ edge.endNode ] = weights[ edge ];
-        }
-    }
-    preorder[ROOT] = 0;  # kořen je prvním uzlem
-    return preorder;
-}
-</code>
-Uvedený algoritmus je založený na tom, že Preorder ohodnocování uzlu je dáno počtem dopředných hran z kořene do uzlu v Eulerově cestě. Pokud mám **p < m** procesorů, každý má na starost <math>\frac{m}{p}</math> hran.
-=== Složitost ===
-<math>T_{1}(m,p) = O \left ( \frac {m}{p} \right )</math>
-<math>T_{2}(m,p) = T_{\tiny PPS} \left ( m, p \right )</math>
-<math>T_{3}(m,p) = O \left ( \frac {m}{p} \right )</math>
-Je třeba vyřešit složitost algoritmu PPS pro **m** prvků s **p** procesory na EREW PRAM. Ten probíhá v následujících 4 fázích:
-  - procesor **P<sub>1</sub>** distribuuje hodnotu **m** všem ostatním pomocí techniky binárního zdvojování (je to EREW!). Pak si procesory pole rozdělí a každý provede PS se svou částí <math>\rightarrow O \left ( log p + \frac {m}{p} \right )</math>
-  - provede se PPS na **p** číslech (každý procesor má svůj lokální PS) <math>\rightarrow O \left ( log p \right )</math>
-  - každý procesor si přečte výsledek fáze 2 procesoru <math>\normalsize p_{i-1}</math> a přičte ho ke svým lokálním hodnotám <math>\rightarrow O \left ( \frac {m}{p} \right )</math>
-<math>\rightarrow T_{\tiny PPS}(m,p) = O \left ( \frac {m}{p} + log p \right )</math>
-Výsledný celkový čas je tedy
-<math>T(m,p) = O \left ( 3 \frac {m}{p} + log p \right ) = O \left ( \frac {m}{p} + log p \right )</math>
 ===== Paralelní prefixový součet na PRAM  =====
@@ Line 479: / Line 115: @@
 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.
-===== Výpočet pořadí od konce =====
-Popište **časově optimální** paralelní algoritmus pro výpočet **pořadí od konce** prvků (//list ranking//, LR) ve **zřetězeném seznamu** o velikosti //n// na počítači CREW PRAM s //p = n// procesory. Vstupem algoritmu je zřetězený seznam ve sdílené paměti PRAM reprezentovaný pomocí **pole následníků** <math>S[1, ... , n]</math>. **Zdůvodněte**, proč je třeba CREW model. Jaká je cena <math>C(n,n)</math> tohoto algoritmu, uvažujeme-li standardní jednotkový model PRAM? Jaká je škálovatelnost tohoto algoritmu? Popište základní myšlenku **cenově optimálního** PRAM algoritmu pro LR s <math>p < n</math> procesory.
-★ //Bylo ve zkoušce: [[par_zkouska_2013-01-16|2013-01-16]] a [[par_zkouska_2012-02-03|2012-02-03]]//
-==== Řešení ====
-Přednáška 7, slide 32 [2015/16] | EN skripta, strana 104 (6.6.3)
-=== Časově optimální algoritmus ===
-Časově optimální algoritmus je popsaný v příkladu [[par_řešené_příklady_6b#algoritmus_pro_pořadí_na_zřetězeném_seznamu|Algoritmus pro pořadí na zřetězeném seznamu]] (opravdu čísluje odzadu).
-CREW je potřeba, protože více procesorů čte najednou hodnotu následníka posledního prvku. <math>C(n,p)=\theta(n.log n)</math>. Algoritmus je špatně škálovatelný, nelze rozdělit pole následníků mezi procesory, následníci uzlů nemusí být v lokální paměti a mohou být rozsypáni v pamětech ostatních procesorů.
-Edit by vd: V EN skriptech na straně 104 nahoře je psáno, že: <math> C\left(n,p\right)=\mathcal{O}\left(n*\log\left(n\right)\right) </math>
-=== Cenově optimální algoritmus ===
-Budeme mít zřetězený seznam s **n' = n/log(n)** prvky a použijeme PU pomocí **p = n/log(n)** procesorů, pak dostaneme **T(n',p) = O(logn)** a **C(n,p) = O(n)**.
-Máme seznam **L** s **n** prvky a pořídíme si <math>p = \theta (\frac{n}{\log n})</math> procesorů.
-  - Transformujeme **L** na kratší seznam **L'** velikosti <math>n' = O(\frac{n}{\log n})</math> tak, aby tato transformace měla paralelní cenu <math>\normalsize C_1(n,p) = O(n)</math>, tedy <math>\normalsize T_1(n,p) = O(log n)</math> pomocí **p** procesorů.\\ <math>C_1(n,p) = O(p \cdot \log n) = O(\frac{n}{\log n} \cdot \log n) = O(n)</math>
-  - Provedeme přeskakování ukazatelů na **L'**, a tím dosáhneme \\ <math>T_2(n',p) = O(\log n') = O(\log(\frac{n}{\log n})) = O(\log n - \log\log n) = O(\log n)</math> \\ <math>C_2(n',p) = O(n)</math>
-  - Reverzí kroků z fáze 2 restaurujeme z **L'** původní seznam **L** a vypočteme konečné pořadí pro prvky v **L - L'** s toutéž složitostí jako v kroku 1 \\ <math>T_3(n,p) = O(T_1(n,p))</math>
-Popis cenově optimálního algoritmu je špatně. Podívejte se raději do EN skript 6.6.3 strana 104. \\ Re: Myslím, že už je to správně.
-**Pozorování 6.11:** Uvažujme spojový seznam s <math> n'=\frac{n}{\log\left(n\right)} </math> prvky, nad kterým aplikujeme //pointer jumping// pomocí <math> p=\frac{n}{\log\left(n\right)} </math> procesorů. Poté <math> T\left(n',p\right)=\mathcal{O}\left(\log\left(n'\right)\right)=\mathcal{O}\left(\log\left(n\right)\right) </math> a tedy <math> C\left(n',p\right)=\mathcal{O}\left(n\right) </math>.
 ===== Segmentový PPS na nepřímém SF CBT_log(p) =====
@@ Line 543: / Line 152: @@
 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í.
-====== Řadící algoritmy (8. přednáška)======
+====== Kolektivní komunikační algoritmy ======
-===== Bitonic sort na krychli Qlogp =====
-Popište algoritmus Bitonický MergeSort na p-procesorové hyperkrychli <math>Q_{log(p)}</math>, <math>1 \leq p \leq N</math>. Odvoďte paralelní čas <math>T(N,p)</math>. Předpokládejte, že **sekvenční setřídění** //k// čísel na 1 procesoru trvá čas <math>\alpha k \log k</math> a že operace **Merge-and-Split** 2 setříděných posloupností //k// čísel provedená 2 sousedními procesory trvá čas <math>\beta k</math>. Odvoďte izoefektivní funkce <math>\psi_1(p)</math> a <math>\psi_2(N)</math>.
-Zhodnoťte jeho škálovatelnost.
-Lze udržet konstantní efektivitu při <math>p = \Theta ( \sqrt N )</math>?
-★ //Bylo ve zkoušce: [[.:par_zkouska_2012-01-03|2012-01-03]] a [[.:par_zkouska_2012-06-26|2012-06-26]] a [[par_zkouska_2013-01-02|2013-01-02]] a [[.:par_zkouska_2016-01-15|2016-01-15]] (za 10 bodů) a [[.:par_zkouska_2016-01-28|2016-01-28]] (za 10 bodů) //
-[[https://edux.fit.cvut.cz/courses/MI-PAR.2/_media/lectures/mi-par2014-prednaska8-sorting.pdf|mi-par2014-prednaska8-sorting.pdf]] slide 31
-==== Řešení ====
-:!://Viz skripta CZ [2006] str. 127//
-Algoritmus pro p = N
-<code c>
-for i=1..log N do_sequentially
-   for j=i;j>1;j-- do_sequentially
-      for all P_k do_in_parallel
-         if (k XOR 2^(i+1) == 0) {
-            CEplus(P_k, P_(k XOR 2^j))
-         }
-         else {
-            CEminus(P_k,P_(k XOR 2^j))
-         }
-</code>
-Tento algoritmus odpovídá následujícímu schématu
-{{.:vyřešené_příklady:bitonic_sort.jpg|}}
-Časová složitost je: log N fází, první trvá 1 krok, druhá 2, ..., poslední trvá log N kroků.
-Počet kroků je vysvětlen na obrázku - nejdřív jeden, pak dva, pak tři, atd. To je pro p=N, pokud je p<N, pak si musí posloupnosti ještě lokálně setřídit, poté se provádí MS.
-{{:škola:předměty:mi-par:fig37-04.jpg|}}
-pro n = 16 schématicky:
-{{http://upload.wikimedia.org/wikipedia/commons/thumb/b/bd/BitonicSort1.svg/1200px-BitonicSort1.svg.png?700}}
-=> <math>1 + 2 + 3 + ... + log N = \frac {1 + \log N} 2 \cdot \log N \approx \frac 1 2 \log^2 N = O(\log^2 N)</math>
-   * Pokud uvažujeme p < N, pak každý procesor má na starosti N/p čísel => operace CE je nahrazena operací MS (merge-split) jejíž složitost je <math>\beta \frac N p = O(\frac N p)</math>.
-   * Celkový počet kroků bude v paralelní fázi <math>\frac 1 2 \log^2 p</math>, složitost kroku pak <math>\beta \frac N p</math> => <math>\frac {\beta N}{2 p} \log^2 p</math>.
-   * Před tím je třeba data lokálně setřídit.
-<math>T(N,p) = O(\frac N p \log \frac N p) + \frac {\beta N} {2 p} \log^2 p = O(\frac N p \log \frac N p + \frac N p \log^2 p) \\
-C(N,p) = p \cdot T(N,p) \\
-E(N,p) = \frac {SU(N)}{C(N,p)} = \frac {N \log N} {N \log \frac N p + N \log^2 p} = \frac {\log N}{\log \frac N p + \log^2 p}
-</math>
-----
-<math>\psi_1(p)= ? => \forall N_p = \Omega(\psi_1(p)) : E(N_p,p) \geq E_0 \\
-\frac {\log N} {\log \frac N p + \log^2 p} = E_0 \\
-\log N = E_0 \log N + E_0 ( \log^2 p - \log p) \\
-=> \log N ( 1 - E_0) = E_0 ( \log^2 p - \log p) \\
-log N = \underbrace {\frac {E_0}{1-E_0}}_{\kappa} (\log^2 p - \log p) = \kappa ( \log^2 p - \log p) = \kappa \log p(\log p -1) \\
-N = (2^{\log p -1})^{\kappa \log p} = (\frac {2^{\log p}} {2})^{\kappa \log p} = (\frac p 2)^{\kappa \log p} </math>
-<math>\psi_1 (p) = (\frac p 2)^{\kappa \log p}</math>
-----
-<math>\psi_2 (N) = ? => \forall p = O(\psi_2 (N)) : E(N,p) \geq E_0 \\
-=> log N = \kappa (\log^2 p - \log p) = \kappa \log p (\log p - 1 )</math>
-Zajímá nás asympotické chování => -1 zanedbáme
-<math>log N = \kappa \log^2 p =>\log p = \sqrt {\underbrace{\frac 1 \kappa}_{\kappa'} \log N} \\
-p = 2^{\sqrt{(\kappa' \log N)}} = 2 ^ {\sqrt {\kappa' \log N} \cdot \frac {\sqrt{\kappa' \log N}} {\sqrt{\kappa' \log N}}} = N^{\sqrt {\frac {\kappa'} {\log N}}}
-</math>
-<math>
-\psi_2 (N) = N ^ {\sqrt {\frac {\kappa'} {\log N}}}
-</math>
-=> funkce <math>\psi_2 (N)</math> neroste příliš rychle => škálovatelnost není moc dobrá. Pro daný počet dat můžeme použít max <math>O(\sqrt N)</math> procesorů.
-Pro <math>p = \Theta(\sqrt N)</math> lze udržet konstatní efektivitu.
-V hyperkrychli spolu v každém kroku postupně komunikují dimenze a provádějí C&E (M&S) operaci:\\
-\\
-1 \\
-1 2  \\
-... \\
-1 2 ... n - 1 n \\
-Vychází to z implementace bitonic sortu na obyčejném motýlkovi, který algoritmus dokáže provádět implicitně bez jakýchkoliv simulací nebo zpomalení. Čili výše uvedené vzorce jsou platné i na hyperkrychli. Chce to tam nakreslit tu postupnou komunikaci dimenzí a myslim že OK
-Edit: K plnému počtu bodů je potřeba nakreslit, jak tento algoritmus funguje na hyperkrychli. Výše dané obrázky mohou být použity jen jako vysvětlení principu. Jako důkaz korektnosti stačí uvést, že dochází k rekurzivnímu bitonickému rozdělení (nakreslit!) a tím k setřídění.
-Edit2: **Podstatná poznámka ke škálovatelnosti**! <math>\psi_{2}(N) = N^{log^{-\frac{1}{2}} N}</math>. Funkce v exponentu je klesající k nule. Z toho plyne, že pro velká N nelze brát více než **konstrantní** počet procesorů, aby se udržela konstantní efektivnost. To znamená, že škálovatelnost je špatná. **Není pravda, co je psáno výše**, že lze udržet konstantní efektivitu při <math>p = \Theta(\sqrt{N})</math>, protože pro velká N je třeba brát <math>p = O(1)</math>.
-VasekJ: souhlas s Edit2, tady je můj důkaz:\\
-Pokud chci dokázat konstantní efektivitu <math>p = \Theta(\sqrt{N})</math> dosadím si do E(N,p) <math>\sqrt{N}</math> za <math>p</math>.
-<math>
-E(N,\sqrt{N}) = \frac {SU(N)}{C(N,p)} = \frac {\log N}{\log \sqrt N + \log^2 \sqrt N} =\frac {1}{\0,5 + 0,25 * \log N}
-</math>
-není konstantní!
-VasekJ po zk: Oproti zadání na wiki letos (2016) nechtěl zhodnocovani skalovatelnosti, konstantni efektivnost ani psi3. Je dulezite nakreslit jak vypada ten algoritmus na krychli (kde jsou ulozene vysledky), za to bral -2b.
-{{:škola:předměty:mi-par:bms-na-q-a-obfn.png?600|}}
-===== Uveďte definici 0-1 třídicí lemma a dokažte ho =====
-★ //Bylo ve zkoušce: [[.:par_zkouska_2012-01-10|2012-01-10]], [[.:par_zkouska_2013-01-30|2013-01-30]], [[.:par_zkouska_2013-12-20|2013-12-20]], [[.:par_zkouska_2014-01-06|2014-01-06]] a [[par_zkouska_2015-01-06|2015-01-06]] //
-==== Řešení ====
-:!://Viz skripta CZ [2006] str. 117 nebo ENG [2010] str. 114 nebo přednáška 8 FIT [2014/2015] slajdy 8, 9//
-:!://Pozn.: Jen pro pořádek - "Lemma 2" není žádný obecně známý název toho lemmatu. V přednáškách je to označeno jako "Lemma 2" jenom proto, že na předchozích slajdech je "Věta 1" a na následujících slajdech "Lemma 3", "Věta 4" atd. Tzn. nedává dobrý smysl to v písemce označovat jako "Lemma 2" i když formálně to je samozřejmě v pořádku.//
-**Lemma 2**
-Nechť f = monotonně rostoucí funkce na lineárně uspořádané množině S, čili <math>\forall x, y \in S ; x \leq y \Leftrightarrow f(x) \leq f(y)</math>.
-Pak:
-{{:škola:předměty:mi-par:0-1_lemma_2.png|}}
-**Důkaz. (Indukcí přes hloubku sítě.)**
-  - Samotný komparátor je datově necitlivý vzhledem k jakékoli m.r. funkci <math>f</math> (pro <math>x, y \in S</math>, komparátor vymění <math>f(x)</math> a <math>f(y)</math> jen tehdy, když vymění <math>x</math> a <math>y</math>)
-  - Indukční krok: Nese-li určitý vodič v třídící síti hodnotu <math>x_i</math>, když je na vstupu posloupnost <math>X</math>, pak tentýž vodič nese hodnotu <math>f(x_i)</math>, když je na vstupu <math>f(X)</math>.
-**0-1 Třídící Lemma**
-Jestliže **datově necitlivý třídící algoritmus** dokáže setřídit **libovolnou binární** vstupní posloupnost, pak dokáže setřídit **libovolnou** vstupní posloupnost.
-**Důkaz. (Sporem.)**
-  * Předpokládejme, že třídící síť třídí správně všechny binární posloupnosti.
-  * Předpokládejme ale, že nesetřídí správně nebinární posloupnost <math>X = [x_1, . . . , x_N]</math>. Pak existují v <math>X</math> čísla <math>x_i < x_j</math> takové, že <math>x_j</math> je na výstupu umístěn před <math>x_i</math>.
-  * Definujme
-    * <math>f(z) = 0</math>, jestliže <math>z \leq x_i</math>,
-    * <math>f(z) = 1</math>, jestliže <math>z > x_i</math>.
-  * <math>f</math> je monotonně rostoucí & <math>f(X)</math> je binární vstupní posloupnost & platí Lemma 2, pak <math>f(x_j) = 1</math> je na výstupu umístěn před <math>f(x_i) = 0</math>, je-li na vstupu <math>f(X)</math>, pak spor.
-{{:škola:předměty:mi-par:0-1_lemma.png|}}
------
-FIXME
-PS: no, to jsou moc pěkně zkopírovaný slidy. Dovedl by to někdo dovysvětlit lidsky (jednodušejš)
-**V každé části je to naprosto přímočaré, jen je třeba pochopit strukturu důkazu, co na čem závisí:**
-  * Samotný důkaz //0-1 třídícího lemmatu// je sporem, jak je napsáno výše, na vstupy aplikujeme monotónně rostoucí funkci <math>f</math> s binárním oborem hodnot, která se přes síť přenese i na výstupy.
-  * K tomu jsme použili //pomocné Lemma 2//, které je teď potřeba také dokázat - i když je intuitivní.
-    * Potřebujeme dvě pomocné věty:
-      - Vodič je datově necitlivý k <math>f</math> - triviální, hodnota se přenáší.
-      - Komparátor je datově necitlivý k <math>f</math> - to je ten důkaz ve skriptech/slidech s min, max.
-    * Důkaz //Lemmatu 2// je indukcí:
-      * Základním krokem jsou samotné vstupy v hloubce 0, kde použijeme //1. pomocnou větu//.
-      * Indukční krok znamená, že vlastnost předpokládáme u vodičů do hloubky <math>d - 1</math> (čili až k výstupům <math>(d - 1)</math>-tého sloupce komparátorů) a musíme ji dokázat i pro vodiče hloubky <math>d</math>, tzn. pro oba výstupy každého komparátoru v <math>d</math>-tém sloupci. Pro každý komparátor je dokazování stejné, protože jiná struktura tam není. Stačí tedy použít //2. pomocnou větu//.
-====== Permutace (9. přednáška)======
-===== Důkaz proveditelnosti bezkolizní monotonní permutace na oBF, algoritmus, složitost =====
-Uvažujte **WH** síť **přímý obyčejný motýlek** <math>oBF_n</math>, kde <math>2^n</math> uzlů v sloupci 0 (respektive n) jsou **vstupy** (respektive **výstupy**). Nechť <math>1 < m < 2^n</math> a <math>A = \{ a_1,a_2, ... , a_m \}</math> je uspořádaná podmnožina množiny vstupů, kde <math>0 \leq a_1 < a_2 < ... < a_m \leq 2^n - 1</math>, a <math> B = \{ b_1, b_2, ... , b_m \}</math> je uspořádaná podmnožina množiny výstupů, kde <math> 0 \leq b_1 < b_2 < ... < b_m \leq 2^n - 1</math>. Pak zobrazení <math> \pi : A \to B</math> takové, že <math> \forall i: \pi(a_i) = b_i</math>, nazveme **monotonní permutací** A na B. **Dokažte**, že každou monotonní permutaci lze na <math>oBF_n</math> realizovat **bezkolizně**. Popište **algoritmus** a odvoďte jeho počet kroků za předpokladu, že na počátku každý vstupní uzel ví, zda patří do A a při tom každý <math>a_i \in A</math> zná pouze adresu svého <math>b_i \in B</math>.
-==== Řešení ====
-//Řešení obdobného příkladu: [[par_řešené_příklady_6b#sf_obfn_monotonni_permutace|SF,oBFn monotonni permutace]].//
-Každý uzel si musí spočítat svoji cílovou polohu => k tomu se hodí použít PPS - zhušťování (operace +, každý uzel patřící do chtěné podmnožiny má váhu 1, ostatní 0).
-Permutace je potom použití zhuštění, roztažení a identity.
-K provedení PPS potřebujeme <math>$T^{BF_n}_{PPS}(N,N)=O(2n)$</math> operací; <math>N = 2^n</math>; n je hloubka sítě
-K provedení zhuštění, roztažení a identity potřebujeme vždy O(n) kroků.
-Celkem je to tedy O(5n) kroků.
-Důkaz bezkoliznosti - skripta str.161. Stručně: Jednoduchý motýlek je bezkolizní, protože pakety které by se měly srazit musí nutně směřovat na stejnou adresu. Velký motýlek obsahuje uvnitř malé motýlky se stejnou strukturou =>  podmínka musí platit i pro větší struktury.
-EDIT: důkazem zde si nejsem jistý, napsal jsem přesně to co je ve slajdech.
-Tak jak to teď je mi bylo uznáno za plný počet bodů.
-:?: Dotaz 06/2016: Má u tohoto příkladu vliv SF vs WH? Přijde mi, že je to jinak naprosto stejné jako příklad SF za 6 bodů ( [[par_řešené_příklady_6b#sf_obfn_monotonni_permutace|SF,oBFn monotonni permutace]]).
-===== Proč je permutace prohození na motýlku kolizní  =====
-Proč je permutace prohození na motýlku kolizní?
-==== Řešení ====
-:!://Viz skripta CZ [2006] str. 157, 158//
-Prohození je definováno jako:
-  - <math>\varphi (0, u_{n-1}  ...  u_{k+1} u_k u_{k-1} ... u_0) = (n, u_{k-1} ... u_0 u_k u_{n-1} ... u_{k+1}) \text{ pro } n=2k+1</math>
-  - <math>\varphi (0, u_{n-1}  ...  u_{k} u_{k-1} ... u_0) = (n, u_{k-1} ... u_0 u_{n-1} ... u_{k}) \text { pro } n=2k </math>
-Neboli vezmu polovinu řetězce (u liché délky tu menší) z konce řetězce a přesunu ji na začátek řetězce.
-Z vlastností minimálního směrování plyne, že v k-tém kroku se posune do takového uzlu, aby k-tý bit zprava byl stejný.
-Pro  <math>u = (u_{n-1} ... u_k ... u_0)</math> vypadá směrování následovně:
-<math>\\
-(0, u_{n-1} ... u_k ... u_0) \rightarrow (1,u_{n-1} ... u_k ... u_{k+1}) \rightarrow (2, u_{n-1} ... u_k ... u_{k+2} u_{k+1}) \rightarrow\\
-...\\
-\rightarrow (k, u_{n-1} ... u_k \underline{u_{n-1} u_{n-2} ... u_{k+1}}) \rightarrow (k+1, u_{n-1} ... u_k \underline{u_{n-1} ... u_{k+1}}) \rightarrow \\
-...\\
-\rightarrow (n, u_{k-1} u_{k-2} ... u_0 u_k u_{n-1} ... u_{k+1})</math>
-Všechny uzyl ve stavu <math>(0, u_{n-1} u_{n-2} ... u_{k+1} u_k\ *^k)</math> musí přejít přes hranu <math>e_k</math> mezi <math>U_k</math> a <math>U_{k+1}</math>.
-**pozn.** Vypadá to hrozně, ale vlastně se děje tohle: Postupně jdu motýlkem e-cube směrováním, které mění bity zprava doleva. Pokud jedu prohození (což je prohození polovin bitů), tak se v půlce dostanu do bodu, kdy mám u všech stejnou levou i pravou půlku bitů. Tam dojde k tý kolizi. Pokud mám motýlka 4 tak uzel 1100 (n = 2k) skončí po k krocích (v polovině) na stavu 1111.  V tomto případě k = 2. Mám tedy <math>2^k</math>.
-Těchto uzlů je <math>2^k</math> a všechny dorazí k <math>e_k</math> v <math> k </math> krocích (současně).
-Toto lze řešit za pomoci třídění
-  - Setřídit pakety na vstupech motýlku podle cílové adresy permutace
-  - Je-li to úplná permutace, provedeme identitu
-  - Pokud ne, nahradím prázdné <math>+ \infty</math> a uděláme identitu, roztažení a identitu.
-Časová složitost závisí na složitosti setřídění.
-EDIT:
-Myslím, že důkaz je zbytečně složitý a navíc klame, protože ke kolizi nedojde až po **k** krocích, ale hned v prvním. IMHO tedy stačí dokázat proč vždy dojde ke kolizi v prvním kroku (to lze snadno ukázat například pro první dva uzly 0 (0...0) a 1 (0...1)).
-JDU: Souhlasím s EDIT
-:?: Můžete to prosím vysvětlit polopatěji?
-EDIT by vd: Souhlasím s výše uvedenými edity, že ke konfliktu dojde už v nultém sloupci. Zde je obrázek konfliktu pro první dva uzly:
-{{http://i.imgur.com/pYiWh0f.png?450|}}
-Tedy oba uzly chtějí routovat v nultém kroku na nulu, což znamená, že chtějí použít stejnou hranu.
-===== Základní síťové zpoždění permutace otočení na indBFn =====
-★ //Bylo ve zkoušce: [[par_zkouska_2012-01-17|2012-01-17]]//
-Odvoďte základní síťové zpoždění permutace otočení <math>\pi_r : u_{n-1} ... u_0 \mapsto u_0 ... {u_n-1}</math> na **všeportovém WH nepřímém motýlku** <math>indBF_n</math> pro sudé <math>n=2k</math>, je-li použito **přímé on-line** směrování, čili <math>\forall u \in \{ 0,1\}^n</math> paket ze vstupu //u// je poslán nejkratší cestou na výstup <math>\pi_r(u)</math>. Komutační latence přenosu paketu o velikosti <math>\mu</math> mezi 2 uzly ve vzdálenosti //d// je <math>t(d, \mu) = t_s +d t_d + \mu t_m</math>. Popište jak zlepšit časovou složitost této permutace. \\
-{{  .:vyřešené_příklady:indbf4.gif  |indBF_4}}
-==== Řešení ====
-Jedná se o varianci na stejné téma, které je vyřešené v
-[[.:par_řešené_příklady_8b&#proč_je_kolizní_permutace_prohození_na_motýlku|tomto příkladu]].
-Nejdřív znázorníme, jak vlastně permutace bude vypadat.
-{{.:vyřešené_příklady:otoceniindbf4.png|}}
-Ke konfliktům bude docházet v první polovině přepínačů. Pak přichází nejvytíženější část (nejužší hrdlo), které nám určí, kolik komunikací bude zároveň probíhat (protože WH blokuje oproti SF celou trasu). Důležité je všimnout si, že za nejužší částí je komunikace vždy bezkonfliktní.
-Celkem tedy máme <math>2^n</math> komunikací, každá pak trvá <math>t(d, \mu) = t_s +d t_d + \mu t_m = t_s + (n+1) t_d + \mu t_m</math>. Otázka je, jaká je ta šířka úzkého hrdla, protože ta určuje, kolik komunikací může probíhat najednou (za předpokladu, že komunikují uzly s různou horní polovinou bitů, aby nenastala kolize už v první polovině grafu). A ta šířka je <math> \sqrt{2^{n}}=\sqrt{2^{2k}}=2^{k} </math> (pokud je <math>n</math> sudé, obdobně pro liché).
-Celkový vzorec (po zanedbání <math>t_s</math>, které síťové nepočítá), je: <math>t(d, \mu) = \frac{2^n * ((n+1) t_d + \mu t_m)}{2^k}</math>
-Časovou složitost lze zlepšit setříděním paketů podle cílové adresy, bude to potom trvať len log^2 N krokov.
-===== Cyklický posun na WH hyperkrychli =====
-Pro zadané přirozené číslo <math>\delta</math> a pro n-rozměrnou vše-portovou hyperkrychli Q<sub>n</sub> s plně-duplexními linkami a červím (WH) přepínáním paketů uvažujte permutaci cyklický posun <math>\pi_{\mathrm{s}}^\delta</math>, definovanou <math>\pi_{\mathrm{s}}^\delta:\, i \mapsto i\, \oplus_{2^n} \,\delta \quad \forall i \in \{0,\dots,2^n - 1\}</math>, kde <math>\delta \in \{0,\dots,2^n - 1\}</math> je konstanta a <math>\oplus_{2^n}</math> je sčítání modulo 2<sup>n</sup>. Dokažte, že e-cube směrování na Q<sub>n</sub> poskytuje pro permutaci <math>\pi_{\mathrm{s}}^\delta</math> hranově disjunktní cesty.
-★ //Bylo ve zkoušce: [[par_zkouska_2012-01-31|2012-01-31]]//
-==== Řešení ====
-<del>Nápad: Cykl. posun jsou v podstatě 2 zhuštění, tedy stačí dokázat že zhuštění je bezkolizní na Qn.</del>
-Cyklický posun je **složení* dvou operací zhuštění na stejné síti**.
-//*) V přednášce 9 [2015/16], slide 36 je uvedeno, že CP je složení **částečných** permutací... netuším, co je myšleno tím částečných.//
-Edit by kuchta: Libovolné hranově disjunktní permutační směrování na SF oBFn je ekvivaletní permutačnímu směrování s nulovým zahlcením na WH plně-duplexní všeportové <math>Q_{n}</math>.(Přednáška 9 [2015/16], slide 38) Takže imho. stačí dokázate že cyklický posun je hranově disjunktní na oBF a je to.
-Edit by vd: Souhlasím, že pokud je CP bezkolizní na přímém oBF, pak je bezkolizní i na <math>Q_{n}</math>. Nicméně si myslím, že by pak bylo nutné dokázat nejenom tu bezkoliznost na motýlkovi, ale i to, že se tato vlastnost přenáší. Proto bych řekl, že je jednodušší to rovnou dokázat na <math>Q_{n}</math>, a proto se přikláním ke správnému důkazu by plech.d.
-**Řešení by plech.d:**
-Pozor na cyklický posun, viděl jsem stejný nedostatek i v jiném příkladě tady na wiki. Nestačí tvrdit, že jsou to dvě zhušťovací permutace, a tedy že stačí dokázat bezkoliznost jedné. Z toho přeci nemusí nutně plynout, že se nemůžou srazit ty dvě zhušťovací permutace, když se vyměňují. Je potřeba indukční předpoklad rozšířit o jednu novou situaci.
-Edit by vd: Doplním jednu podstatnou vlastnost k analogii s CP na motýlkovi. Pokud jdou v motýlkovi I.) pakety křížem (inverze), pak se v hyperkrychli prohodí sousedi; II.) pokud jdou v motýlkovi rovně (identita), pak v hyperkrychli **zůstávají pakety na místě**, nic se nikam nepřesouvá (Tvrdík tomu říká //vnitřní komunikace//).
-**1. krok:**
-Při e-cube směrování je v prvním kroku použita jen 0-tá dimenze. Kolize může nastat mezi dvěma sousedními uzly v této dimenzi, z nichž jeden by přeskočil k druhému a druhý zůstal. Sousední pár má v 0-tém bitu vždy jeden 0 a jeden 1.
-Mohou nastat dvě hlavní možnosti: Packety jsou součástí stejné zhušťující permutace, nebo jsou packety součástí každý jiné.
-V prvním případě, protože zhušťovací permutace je monotónní a packety tedy na druhém konci budou opět těsně za sebou, mohou nastat dvě podmožnosti:
----------------------
-aaaa0 -> bbbb0
-aaaa1 -> bbbb1 - 0-tý bit se neinvertuje, žádný přenos se nekoná, žádná kolize
----------------------
-aaaa0 -> bbbb1
-aaaa1 -> bbbb0 - 0-tý bit se invertuje u obou, packety se vymění, žádná kolize
----------------------
-V druhém případě, když jsou packety každý součástí jiné zhušť. permutace, vždy vede první ze dvou uzlů do úplně posledního ze všech, který jistě končí 1, a druhý do úplně prvního ze všech, který jistě končí 0. To znamená, že situace bude vždy tato:
-aaaa0 -> bbbb1
-aaaa1 -> bbbb0 - 0-tý bit se invertuje u obou, packety se vymění, žádná kolize
-:!: Pozor: zde je drobná chyba v tom, že takto to bude vždy jen tehdy, pokud má slovo, o které posouváme, lichou paritu. Pokud má sudou paritu, nastane ještě situace:
-aaaa1 -> bbbb1
-aaaa0 -> bbbb0
-Nicméně ani toto není kolizní, protože v tomto případě nedochází ke komunikaci a pakety zůstávají ve svých uzlech.
-Žádná z těchto tří možností není kolizní, 1. krok je tedy bezkolizní.
-**Indukční krok:**
-Po předchozím kroku se packety nacházejí na dvou disjunktních podkrychlích (<math>Q_{n-1}</math>) aaaa*. Odřízneme-li z adresy neutrální symbol, situace je úplně stejná jako v prvním kroku a tedy opět bezkolizní.
-JDU: ad bezkoliznost sousedů z různých zhuštění: Tento případ nastává při posunu o liché číslo. V případě, že posouváme o sudé, třeba 4, nenastane také varianta, že aaaa1 -> bbbb1, aaaa0 -> bbbb0 ???? Např u Q3 (011>111, 100>000)
-Edit by vd to JDU: Máš pravdu, tohle může nastat. Nicméně pokud toto nastane, v hyperkrychli to znamená, že nedochází k žádné komunikaci (výměně) a tudíž kolize stejně nemůže nastat.
-===== Offline algoritmus pro permutaci na SF 2D mřížce =====
-Popište a vysvětlete offline algoritmus pro bezkolizní realizaci libovolné zadané permutace π na SF plně duplexní **M(z<sub>1</sub>, z<sub>2</sub>)** (čili algoritmus permutace je-li pro danou permutaci povolen předvýpočet bezkolizního řešení). Odvoďte počet komunikačních kroků algoritmu. Popište algoritmus a důkaz jeho bezkoliznosti proveďte nejprve obecně, a pak demonstrujte na permutaci π na **M(5,4)** dle obrázku, kde každý paket je znázorněn čtvercem s číslem cílového řádku a sloupce.
-|   ^ 1   ^ 2   ^ 3   ^ 4   ^ 5   ^
-^ a | b,3 | c,3 | a,5 | d,3 | d,1 |
-^ b | d,5 | b,4 | c,4 | c,1 | d,2 |
-^ c | b,5 | a,3 | a,4 | b,2 | d,4 |
-^ d | c,2 | c,5 | a,2 | a,1 | b,1 |
-★ //Bylo ve zkoušce: [[par_zkouska_2011-06-30|2011-06-30]] a [[par_zkouska_2012-01-24|2012-01-24]]  4b, [[par_zkouska_2012-06-26|2012-06-26]] , [[par_zkouska_2014-02-04|2014-02-04]] //
-==== Řešení ====
-:!://Viz skripta CZ [2006] str. 154//
-**Pro naučení doporučuji záznam z 9. přednášky 2014/2015 cca od 40:00 do 58:00, je to tam skvěle vysvětlené.** Stačí si pamatovat ty 4 fáze a umět vysvětlit první, tj. párování v bipartitním grafu, které se snadno pamatuje i bez vzorců.
-Off-line algoritmus, který pro libovolnou permutaci <math>\pi</math> na <math>M(n,n)</math> předpočítá směrování o nejvýše <math>3n - 3</math> krocích bez pomocné paměti. Tento příklad je teda pro mřížku m x n.
-Algoritmus má 4 fáze:
-<code>
-Fáze 1: Ve ∀ sloupcích, předpočítej permutace takové, aby v každém řádku M (n, n)
-∃ nejvýše 1 paket určený pro daný sloupec.  O(m * n^2), kde m je počet barvení
-Fáze 2: Realizuj tyto permutace ve všech sloupcích paralelně. (∗ n − 1 kroků ∗)
-Fáze 3: Paralelně ve ∀ řádkách, zpermutuj pakety do správných sloupců. (∗ n − 1 kroků ∗)
-Fáze 4: Paralelně ve ∀ sloupcích, zpermutuj pakety do správných řádků. (∗ n − 1 kroků ∗)
-</code>
-{{:škola:předměty:mi-par:offline_mesh.png?600|}}
-Obrázek: Směrovací graf a párování pro SF mřížku. Postup: počáteční konfigurace je zadání, v jednotlivých uzlech jsou pakety a adresy, kam chtějí jít. Sestavím směrovací graf – v jeho levém sloupci jsou <math>s_{X}</math> a v pravém <math>d_{X}</math>, <math>s</math> značí //source//, <math>d</math> značí //destination// a <math>X</math> číslo sloupce. Poté provedeme hranové barvení – v případě mřížky <math>4\times4</math> jsou výsledkem čtyři čtveřice (každá čtveřice pak obsahuje čtyři disjunktní dvojice <math>s--d</math>, protože paket, který je v nějakém sloupci, je reprezentován právě jednou hranou v grafu), které kdybychom přes sebe překryli, získáme opět směrovací graf. Poslední krok je provedení permutace sloupců (zde je jedno, kterou ze čtveřic namapujeme na který řádek, všechny varianty jsou správné). Příklad pro první zelený řádek: podívám se na zelený graf na první uzel. V buňce mřížky <math>\mathtt{a1}</math> má být paket z prvního sloupce, který chce jít do 3. sloupce. Podívám se na druhý uzel grafu. V buňce mřížky <math>\mathtt{a2}</math> má být paket z druhého sloupce, který chce jít do 1. sloupce. Atd.
-Je důležité popsat, jak vlastně tu první fázi uděláte. Na to se používá Hallova věta o párování, známá též jako metoda //tanečního mistra// nebo //maďarská metoda//. Trik je v tom, že celý problém hledání sloupcové permutace **převedeme na problém párování na bipartitním grafu**.
-**Věta 5, Hallova věta o párování**
-Libovolný <math>m</math>-regulární graf s 2n uzly může být rozložen do <math>m</math> dokonalých párování čili má <math>m</math>-barvení hran v čase <math>\mathcal{O}\left(m*n^{2}\right)</math>. [Zdroj: přednáška 9 (2015/16), slide 20]
-(Konkrétně Hallova věta je dobře vysvětlena na záznamu 10. přednáška roku 2008, viz [[https://www.youtube.com/watch?v=mQDdvpG0Bps|]])
-{{https://i.imgur.com/66SeXQx.png?600|}}
-Obrázek: Příklad bipartitního párování aka //taneční//. Na obrázku existují již tři páry holka--kluk (my jsme ten prostřední). Nyní ale přijde svalovec (kroužek v kroužku) a chce naší dívku, my mu ji přenecháme a jdeme sebrat dívku někomu jinému, takhle se vše může nejhůř rozpojit až na začátek, ale nakonec je algoritmem garantováno, že vše dobře dopadne. Z toho ale plyne i složitost: Vyrobit 1 párování o velikosti <math>n</math> uzlů trvá nejhůře <math>n^2</math>. Opakujeme tolikrát, kolik je stupeň grafu, a tedy pokud je stupeň grafu <math>n</math>, složitost je <math>\mathcal{O}\left(n^{3}\right)</math>.
-==== Řešení konkrétního příkladu ze zadání ====
-{{:škola:předměty:mi-par:smerovani.png?200|}}
-Směrovací graf
-{{:škola:předměty:mi-par:parovani.png?500|}}
-Vytvořená úplná párování
-{{:škola:předměty:mi-par:faze.png?600|}}
-Postup algoritmu po fázích (1. je po provedení permutací ve sloupcích)
-**Hint (by zatretom):**
-Na termínu 9. 2. 2015 jsme měli provést permutaci podle konkrétního zadání - co si pamatuju, tak v zadání nebylo úplně napsaný, že chce popsat tu konstrukci permutace, co se dělá offline (spíš jsem to pochopil jako popsání, co mají splňovat ty tři permutace a proč to bude fungovat). Ano, pochopil jsem to špatně, chtěl tam tu konstrukci mít (bez ní dával 4/8 nebo i 0/8). Krokovat procházku je IMHO zdlouhavý, zkuste to takhle:
-Na směrovací graf se hodí pravítko, čar je tam hodně nevyznáte se v tom (nebo to musíte nakreslit hrozně velký) - jako náhrada pravítka dobře poslouží ISIC. Procházku jenom popiště, ale krokovat ji je hrozně zdlouhavý. Spíš si vezměte i tužku a gumu, nakreslete si mřížku a zkuste tu první fázi tipnout tužkou okometricky (metodou kouknu a vidím, dá se to do dvou minut). Ten rozpad na úplná párování můžete zpětně dokreslit podle toho, co jste vyšpekulovali.
-===== Operace přeložení na indBFn, odvodit zakladní síťové zpoždení =====
-indBF4 - operace prelozeni n=2k, odvodit zakladni sitove spozdeni
-★ //Bylo ve zkoušce: [[par_zkouska_2012-01-17|2012-01-17]] ??//
-==== Řešení ====
-operace přeložení je na indBFn bezkolizní, # kroků by měl být n. Výše zmiňovaný počet kolizí by byl např. v případě operací prohození nebo otočení
-Edit by plech.d: Přeložení je definováno jako xor n-bitovým řetězcem w. Operace je na motýlkovi bezkolizní, protože v každém kroku i dle i-tého bitu w buď bity všech adres invertuje nebo všechny nechává. Z toho plyne, že všech k přepínačů v jedné úrovni je buď křížem nebo rovně – vstupní dva packety posílají do různých kanálů – cesty jsou hranově disjunktní.
-Cesty se tedy sestaví automatickým směrováním od začátku do konce bez překážky a jsou dlouhé n+1 kroků.
-Pro SF tedy platí:
-<math>t_{SF} = t_s + (n+1)\mu t_m</math>
-Pro WH:
-<math>t_{WH} = t_s + (n+1)t_d + \mu t_m</math>
-:?: t_d? to je asi chyba, predpokladam, ze to ma byt t_m. A nevim, proc se opomijeji t_w a t_r, ale mozna to bylo v zadani.
-Poznámka: Předpokládám, že je omyl v zadání, kde je řečeno, že chceme základní síťové zpoždění. To by totiž znamenalo, že máme vypustit t<sub>s</sub>, což je docela neobvyklé. Pravděpodobně je míněno základní komunikační zpoždění, které t<sub>s</sub> zahrnuje.
-Poznámka 2: Pořád si nejsem jist, zda je hran n+1 nebo n. Zda se počítá hrana před 0-tým stupněm motýlka. Ale nevidím důvod, proč by se nepočítala, proto píšu n+1. Doporučuju, pokud si tím taky nejste jisti, toto do písemky zmínit a ukázat na obrázku, aby nedošlo k nedorozumění.
-====== Kolektivní komunikační algoritmy (10. + 11. přednáška)======
 ===== Multicast na 2D mřížce ve WH síti =====
@@ Line 1010: / Line 195: @@
 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.
-===== Binární výměna pro AAS v mřížce=====
-Popište algoritmus binární výměny pro All to All Scatter (AAS) v
-<math>M(\sqrt{p},\sqrt{p})</math>, 1-port, Full-duplex, WH, kombinující, každý procesor má připraven pro všechny ostatní paket velikosti <math>\mu</math>. Určete <math>t_{\rm AAS}</math> a <math>r_{\rm AAS}</math>.
-★ //Bylo ve zkoušce: [[.:par_zkouska_2015-01-28|2015-01-28]] za 10 b//
-==== Řešení ====
-//[přednáška 11, slide 24]//
-{{:škola:předměty:mi-par:binexch_aas_m_8_8.png|}}
-Algoritmus binární výměny je simulace AAS pro SF hyperkrychli. To dobře funguje, pokud délky stran jsou mocniny dvou. Do testu je třeba explicitně napsat, že se jedná o hyperkubický algoritmus.
-  - Mřížka se vždy rekurzivně půlí, např. střídavě ve směrech X a Y
-  - Celkový počet **fází, ale nikoliv kroků** je <math>k + l = \log{\sqrt{p}} + \log{\sqrt{p}} = \log{\sqrt{p} \sqrt{p}} = \log{p}</math>
-<math>r_{\tiny AAS} \ne \log{p}</math>, protože dochází ke kolizím při používání kanálů. Tj. jedna fáze nemůže proběhnout v jednom kroku! Tedy až na ty dvě, kdy si pakety prohazují sousední uzly.
-V každém kroku se mezi partnery vymění <math>\frac{p}{2}</math> paketů (uzel odešle <math>\frac{p}{2}</math>, zůstane mu tedy <math>\frac{p}{2}</math> a posílal by dál už jen <math>\frac{p}{4}</math>, ovšem od svého partnera obdrží taky <math>\frac{p}{2}</math> hodnot, takže na poslání bude mít opět <math>\frac{p}{2}</math> hodnot (paketů).
-  - fáze <math>t_1 = 2\left( t_s + \frac{ \sqrt{p} }{ 2 } \cdot t_d + t_m \cdot \mu \cdot \frac{p}{2} \right) \cdot \frac{ \sqrt{p} }{ 2 } = \sqrt p t_s+ \frac{p}{2}t_d+\sqrt p \frac{p}{2}\mu t_m</math>
-  - fáze <math>t_2 = 2\left( t_s + \frac{ \sqrt{p} }{ 4 } \cdot t_d + t_m \cdot \mu \cdot \frac{p}{2} \right) \cdot \frac{ \sqrt{p} }{ 4 } = \frac{\sqrt p}{2}t_s+ \frac{p}{8}t_d+\frac{\sqrt p}{2} \frac{p}{2}\mu t_m</math>
-poslední fáze: <math> t_k = 2\left( t_s + 1 \cdot t_d + t_m \cdot \mu \cdot \frac{p}{2} \right) \cdot 1 = 2t_s+ 2t_d+ p\mu t_m</math>
-vysvětlení vzorečku: 2 znamená dimenzi X a Y, v každé dimenzi proběhne <math>\frac{\sqrt{p}}{i} </math> výměn, i se iterativně zvyšuje. Každá výměna pak obsahuje startovní zpoždění, přenos hlavičky, za kterou hned následuje přenos zprávy, jejíž velikost je po celou dobu stejná.
-<math>t_{\rm AAS} = (\sqrt p+\frac{sqrt p}{2}+...+2)(t_s+\frac{p}{2}\mu t_m)+(\frac{p}{2}+\frac{p}{8}+...+2)t_d=2(\sqrt p - 1)(t_s+\frac{p}{2}\mu t_m)+2t_d\frac{p-1}{3} = 2\sqrt p t_s+p\sqrt p \mu t_m+ \frac{2}{3}pt_d</math>
-Počet kroků (tedy <math>r_{\rm AAS}</math>) udává, kolikrát se startuje komunikace. Je to tedy <math>2 (\sqrt{p} - 1)</math>.
-Pozn: zacatek vysvetlen dobre v 20080520_X36PAR_cviceni11.avi, od 05:00
 ===== AAB na 2D toroidu, SF, všeportový, nekombinující =====
@@ Line 1076: / Line 228: @@
 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ě.
-===== Multicast na Qn =====
-==== Řešení ====
-:!://Viz skripta CZ [2006] str. 178 nebo EN [2009] str. 157 a 155//
-=== Algoritmus ===
- Z cílové množinu uzlů <math>|M|</math> a zdrojového uzlu //s// (který neleží v <math>|M|</math>) vytvořím ADOC (lexikograficky vzestupně setříděný řetěz uzlů) a dostávám tak vlastně 1D mřížku. Rozesílat zprávu mohu z uzlu <math>0^n</math>, protože kostka je uzlově symetrická, takže přeložení není problém.
- - Použiji algoritmus RD (rekurzivní zdvojování)
-  - rozdělím pole na dvě poloviny. Pošlu ze zdroje zprávu nejbližšímu uzlu z druhé poloviny (přepokládám zdroj 0000)
-  - rekurzivně aplikuju to samé pořád dokola, dokud nejsou všichni informovaní - čili vzniklé dvě poloviny zase rozdělím na poloviny a posílám z informovaných uzlů do nových polovin zprávu
-Informovaných uzlů musí být <math>|M|</math>. V každém kroku se počet informovaných uzlů maximálně zdvojnásobí. Počet kroků je tedy <math>r_{\rm MC}=\left\lceil \log{|M| + 1}\right\rceil</math>.
-Pro směrování je použito e-cube směrování, porovnávájící dimenze zleva doprava (stejně jako ADOC; opačně než je obvyklé).
-Pozn: Jelikož ADOC není standardní pojem v grafech, je nutné jej vysvětlit a poté i dokázat bezkoliznost na řetězci u,v,w,z jako ve skriptech.
 ===== OAS na 2D toroidu  =====
@@ Line 1353: / Line 485: @@
 </math>
-====== Lineární algebra (12. přednáška)======
+====== Lineární algebra ======
 ===== Transpozice na 2D mřízce, SF =====
@@ Line 1437: / Line 569: @@
 {{tag>škola s_řešením zkoušky}}
+x