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: 2012-01-10

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:

1. 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>.
2. 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> ).
3. 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>.
4. Další kroky se liší pro READ a WRITE:
   • WRITE:
     1. procesor <math>p_{i}'</math> zapíše obsah <math>A[i] = (j,k,s)</math> do <math>A[k]</math>
     2. 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:
     1. <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>.
     2. 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>.
     3. provede se permutace <math>A[i] = (j,k,v_{j})</math> do <math>A[k]</math>
     4. 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>.

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: 2013-01-23

Viz skripta CZ [2006] str. 45, věta 3.11; EN [2010] str. 27, theorem 2.16

mi-par2014-prednaska2-pararch.pdf slide 26

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: 2014-02-12

mi-par2014-prednaska2-pararch.pdf slide 24

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).

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: 2015-01-13, 2013-05-21, 2012-05-18, 2011-05-19

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…

10: očísluj uzly v grafu
20: vytvoř kostru grafu G průchodem do šířky od nějakého uzlu r
30: 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

A ještě pár obrázků:

1) 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

Hrany v kostře se orientují od potomků k předkovi.

Ostatní hrany se orientují od vyššího ID k nižšímu.

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:

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.

Uvažujme počet hran stromu m = 2n-2 a počet procesorů p = m.

Část A:

  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
    }
  }

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:

  for i in 0..m-1 do_in_parallel {
    if (maList[i] = 1) {
      List[ X[i] -1 ] = EA[i].endNode
  }

Stejný kód zapsaný v alternativní syntaxi:

# 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;
}

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).

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>

(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;
}

Eulerův strom a jeho reprezentaci polem, mám hotovou Eulerovu cestu.

★ Bylo ve zkoušce: 2012-06-26, 2014-02-04

  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 */

Stejný kód v alternativní syntaxi:

# 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;
}

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ě.

2014 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.

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.

Algoritmus pro p = n má následující podobu:

  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;

Stejný kód zapsaný v alternativní syntaxi:

# 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;
}

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.

<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:

1. procesor P₁ 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>
2. provede se PPS na p číslech (každý procesor má svůj lokální PS) <math>\rightarrow O \left ( log p \right )</math>
3. 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>

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.

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: 2013-01-16 a 2012-02-03

Přednáška 7, slide 32 [2015/16] | EN skripta, strana 104 (6.6.3)

Časově optimální algoritmus je popsaný v příkladu 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>

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ů.

1. 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>
2. 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>
3. 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 <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í.

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: 2012-01-03 a 2012-06-26 a 2013-01-02 a 2016-01-15 (za 10 bodů) a 2016-01-28 (za 10 bodů)

mi-par2014-prednaska8-sorting.pdf slide 31

Viz skripta CZ [2006] str. 127

Algoritmus pro p = N

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))
         }

Tento algoritmus odpovídá následujícímu schématu

Č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.

pro n = 16 schématicky:

⇒ <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:
0
0 1
0 1 2
…
0 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.

★ Bylo ve zkoušce: 2012-01-10, 2013-01-30, 2013-12-20, 2014-01-06 a 2015-01-06

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:

Důkaz. (Indukcí přes hloubku sítě.)

1. 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>)
2. 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.

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:
    1. Vodič je datově necitlivý k <math>f</math> - triviální, hodnota se přenáší.
    2. 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.

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í obdobného příkladu: 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ů ( SF,oBFn monotonni permutace).

Proč je permutace prohození na motýlku kolizní?

Viz skripta CZ [2006] str. 157, 158

Prohození je definováno jako:

1. <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>
2. <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í

1. Setřídit pakety na vstupech motýlku podle cílové adresy permutace
2. Je-li to úplná permutace, provedeme identitu
3. 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:

Tedy oba uzly chtějí routovat v nultém kroku na nulu, což znamená, že chtějí použít stejnou hranu.

★ Bylo ve zkoušce: 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.

Jedná se o varianci na stejné téma, které je vyřešené v tomto příkladu.

Nejdřív znázorníme, jak vlastně permutace bude vypadat.

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 * ¹⁾</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ě.

Viz skripta CZ [2006] str. 178 nebo EN [2009] str. 157 a 155

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í)

1. 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)
2. 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 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