Differences

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

--- users:martin.kocicka:pdp:12b [2017/06/09 07:02] – vytvořeno martin.kocicka
+++ users:martin.kocicka:pdp:12b [2017/06/09 07:05] (current) – martin.kocicka
@@ Line 1: / Line 1: @@
-====== PAR - Vyřešené zkouškové příklady za 12 bodů ======
+====== PDP - Vyřešené zkouškové příklady za 12 bodů ======
-===== Cenově optimální APRAM algoritmus pro paralelní redukci =====
-//Pozn. v některých zadáních je tento příklad za 5 bodů.//
-Uvažujte standardní **APRAM** model počítače(lokální operace trvají 1, posloupnost <math>k\ge 1</math> globálních R/W za sebou trvá čas <math>k+d-1</math> a bariérová synchronizace //p// procesů trvá <math>B(p)=\alpha d\log p</math>, kde <math>\alpha</math> a <math>d > 1</math> jsou dané konstanty). Dále předpokládejte, že procesory mají **nezávislou** paměťovou a aritmetickou jednotku. Popište co nejrychlejší APRAM algoritmus pro **paralelní redukci** //n// čísel pomocí **binární** asociativní operace <math>\bullet</math>. Odvoďte paralelní **čas** <math>T(n,p)</math>, **izoefektivní** funkce <math>\psi _1(p)</math> a <math>\psi _2(n)</math> a asymptotickou spodní mez <math>\psi _3(n)</math> na počet procesorů pro dosažení časové optimality.
-Analýzu časové složitosti proveďte pro model s **dynamickou** bariérovou synchronizací.
-★ //Bylo ve zkoušce:  [[par_zkouska_2013-02-06|2013-02-06]], [[par_zkouska_2012-01-31|2012-01-31]] a [[par_zkouska_2011-01-10|2011-01-10]] //
-==== Řešení ====
-Řešení je podrobně popsané i {{:škola:předměty:mi-par:apram.pdf|zde}}.
-=== Postup z 4. prosemináře 2013 ===
-Sekvence APRAM redukce n čísel na <math>p_a</math> procesorech je\\
-<math>
-\left \langle
-RR
-\left \langle \frac{R}{L} \right \rangle ^{\frac{n}{p_a} - 2}
-L W B
-\left \langle R L W B \right \rangle ^{\log{p_a}}
- \right \rangle
-</math>
-Máme nezávislé jednotky pro práci s pamětí a aritmetiku => v sekvenční části můžeme načítat nová čísla v každém novém cyklu a v dalším je sčítat\\ (v čase t přijde první číslo, v čase t+1 další v čase t+2 je sečtu a zároveň načtu další)
-<math>T_a(n,p_a) = d + \left ( \frac{n}{p_a} - 1 \right ) + 1 + d + B(p_a)
-+ \log{p_a}(d + 1 + d + B(p_a)) </math>
-Jedničky mohu opomenout, <math>d</math> také, protože je asymptoticky menší oproti <math>B({p_a}) = d\log{p_a}</math>\\
-<math>T_a(n,p_a) = \frac{n}{p_a} + \alpha d \log^2{p_a}</math>\\
-<math>C_a(n,p_a) = n + \alpha p_a d \log^2{p_a}</math>\\
-Protože <math>SU(n) \dot= n</math> má rovnice\\ <math>E(n,p_a) = \frac{n}{n + \alpha d p_a \log^2{p_a}} = E_0</math> řešení:\\
-<math>n = \frac{E_0 \alpha d}{1 - E_0} p_a \log^2{p_a}</math> a
-<math>p_a \dot= \frac{\gamma n}{\log^2{\gamma n}}</math>, kde <math>\gamma =  \frac{1 - E_0}{E_0 \alpha d}</math>
-<hidden onHidden="**[+] Alternativní postup**" onVisible="**[-] Alternativní postup**" initialState="hidden">
-Pro efektivní simulaci PRAM algoritmu s <math>p_p</math> procesory na APRAM počítači je potřeba řádově snížit počet procesorů z <math>p_a</math> na <math>p'_a = \frac{p_p}{B(p_p)}</math>. Víme, že p-procesorový PRAM algoritmus pro paralelní redukci nad polem ''n'' hodnotje časově i cenově optimální, pokud <math>p = \Theta (\frac{n}{\log{n}})</math>. Položme pro jednoduchost <math>p_p = \frac{n}{\log{n}}</math>.
-Pro optimální počet procesorů <math>p'_a</math> pro APRAM redukci platí:\\
-;#;<math>p'_a = \frac{p_p}{B(p_p)}
-= \frac{\frac{n}{\log{n}}}{\alpha d \log{(\frac{n}{\log{n}})}}
-= \frac{n}{\alpha d \log{n} (\log{n} - \log{\log{n}})}
-\dot= \frac{n}{\alpha d \log^2{n}}</math>;#;
-V první fázi výpočtu každý APRAM procesor zredkuje sekvence <math>n/p'_a = \alpha d \log^2{n} = \beta</math> čísel. Z předpokladu pro nezávislou pamětovou a aritmetickou jednotku plyne, že zatímco se z paměti pomocí R načítají hodnoty, aritmetická jednotka je okamžitě redukuje na mezivýsledky. Pak je složitost první fáze rovna
-;#;<math>T_a^I(n,p'_a ) = d+ \beta - 1 + 1 \dot= \beta</math>.;#;
-Druhá fáze začíná bariérou, pak se zapíšou lokální výsledky první fáze, znovu bariéra a pak se provede APRAM redukce <math>p'_a</math> čísel na <math>p'_a</math> procesorech:\\
-;#;<math>T_a^{II}(n,p'_a )
-\dot= B(p'_a) + d + B(p'_a) + 2B(p'_a)\log{p'_a}
-\dot= 2B(p'_a)\log{p'_a} \le 2 \beta</math>;#;\\
-''pozn. - podle mého by tam mělo ještě někde být d...''
-Výraz <math>2B(p'_a)\log{p'_a}</math> předpokládá, že se v každém kroku účastní všech <math>p'_a</math> procesorů. Při dynamické bariérové synchronizaci ale počet procesorů exponenciálně klesá, takže čas spotřebovaný na dynamickou bariérovou synchronizaci je\\
-;#;<math>
- t_{BS} = 2( B(p'_a) + B(\frac{p'_a}{2}) + B(\frac{p'_a}{2^2}) + \cdots + B(2))
-</math>;#;\\
-;#;<math>
- t_{BS} = \alpha d \log{p'_a}(log{p'_a}+1) \dot= \alpha d \log^2{p'_a} \le \beta
-</math>;#;
-Celkový čas je <math>T_a(n, p'_a) = T_a^{I}(n,p'_a ) + T_a^{II}(n,p'_a ) \le 2 \beta</math>.
-Celková cena je <math> C_a(n, p'_a) = p'_a T_a(n, p'_a) = \frac{n}{\beta} \times 2\beta = 2n</math>
-</hidden>
-Spočítaný postup krok za krokem i s komentáři a včetně psi3
-[[https://www.fit-wiki.cz/%C5%A1kola/p%C5%99edm%C4%9Bty/mi-par/principy_%C5%99e%C5%A1en%C3%AD_%C3%BAloh?&#konkrétní_ukázka_řešení|zde]]
-== Dynamická bariéra ==
-Pro dynamickou bariéru je první část výpočtu stejná (každý procesor musí vyřešit svůj díl čísel), ale když pak začnou komunikovat mezi sebou, tak to není <math> {<RLWB(p)>}^{\log p} </math> jako u statické, protože v každém kroku se vám polovina procesorů uvolní (již nemusí nic dělat) a tak děláte bariéru pro menší počet procesorů. Po prvním sečtení stačí udělat bariéru už pouze pro polovinu procesorů až zbyde jenom jeden, tedy krok po kroku to vypadá jako : <math> RLWB(\frac{p}{2}) + RLWB(\frac{p}{4}) + RLWB(\frac{p}{8}) </math> ... <math> + RLWB(2) </math>
-Pokud se na to podíváte jako že logaritmus dělení je rozdíl logaritmu, tak je to vlastně posloupnost <math>1 + 2 + 3 + </math> ... <math> + \log p - 1</math>. To je klasický součet řady, jehož vzoreček je : <math>\frac{n (n-1)}{2}</math> a tedy <math>\frac {d \log^2 p}{2}</math>
-(je to tedy 2 rychlejší, asymptoticky to ale vyjde stejně jako se statickou)
-Pozn. součet aritmetické řady je <math>\frac{n (a1 + an)}{2}</math> tedy <math>\frac{(log (p)) (1 + log (p) - 1))}{2}</math>
-založeno na <math>log(a/b) = log a - log b</math> v tomto případě řady  <math> RLWB(\frac{p}{2}) + RLWB(\frac{p}{4}) + RLWB(\frac{p}{8}) </math> ... <math> + RLWB(2) = log p * (RLW) + (B(p/2) + B(p/4) + ... + B(2)) </math>
-===== Třídění ve 3D mřížce =====
-Popište algoritmus pro **třídění** //N// celých čísel na p-procesorové **3-D mřížce** <math>M(\sqrt[3] p,\sqrt[3] p,\sqrt[3] p), p \le N</math>. **Odvoďte** co nejpřesněji jeho paralelní čas <math>T(N,p)</math>, **izoefektivní** funkce <math>\psi_1(p)</math> a <math>\psi_2(N)</math>, a asymptotickou spodní mez <math>\psi_3(N)</math> na počet procesorů pro dosažení časové optimality, jestliže (1) sekvenční **setřídění** //k// čísel na 1 procesoru trvá čas <math>\alpha k \log k</math>, (2) operace **Merge-and-Split** 2 setříděných posloupností //k// čísel provedená 2 sousedními procesory trvá čas <math>\beta k</math> a (3) lexikografické setřídění v 2-D mřížce <math>M(\sqrt N,\sqrt N)</math> trvá čas <math>\gamma \sqrt N</math>, kde <math>\alpha ,\beta ,\gamma</math> jsou konstanty.
-★ //Bylo ve zkoušce: [[par_zkouska_2015-01-28|2015-01-28]], [[par_zkouska_2014-01-13|2014-01-13]],[[par_zkouska_2013-01-16|2013-01-16]],[[par_zkouska_2012-02-10|2012-02-10]] - všude za 10b bez psí_3//
-==== Řešení ====
-:!://Viz FIT [2012] přednáška 8 slide 19, skripta CZ [2006] str. 121 nebo EN [2009] str. 117//
-{{:škola:předměty:mi-par:3dsort.jpg|}}
-  - Faze - Setrid vsechny xz-roviny v zx-poradi.
-  - Faze - Setrid vsechny yz-roviny v zy-poradi.
-  - Faze - Setrid vsechny xy-roviny v yx-poradi stridave ve smeru y.
-  - Faze - Proved jednu licho-sudou a jednu sudo-lichou transpozici ve vsech sloupcich.
-  - Faze - Setrid vsechny xy-roviny v yx-poradi.
-**Důkaz pomoci 01-třídící lemma** (pro stranu mřížky rovnou n)
-viz. přednáška 8, slide 19
-   - Po fázi 1, v každé xz-rovině existuje nejvýše 1 nečistý řádek, a proto :
-     - jakékoliv 2 yz-roviny se mohou lišit v **nejvýše n** nulách
-     - všech n yz-rovin obsahuje ve svých nečistých řádcích souhrnně **nejvýše** <math>n^2</math> prvků
-   - Tudíž po fázi 2 všechny nečisté řádky mohou překlenout **nejvýše** 2 xy-roviny.
-   - Je-li nečistá xy-rovina pouze jedna, jdeme přímo na fázi 5 a jsme hotovi.
-   - Existují-li 2 nečisté xy-roviny, fáze 3 a 4, vyčistí aspoň 1 z nich a fáze 5 dokončí řazení.
-=== Odvození ===
-   * V 5 fázích se 4x provede lexikografické třídění na 2D mřížce (rovině) - zx, zy, 2*yx. Jeden takový 2D lexikograficiký sort trvá podle zadání <math>O(\gamma \sqrt N)</math>.
-   * Ve 4. kroku se na všech sloupcích, 1D mřížkách <math>M(\sqrt[3] p)</math>, provede právě jedna sudo lichá a jedna licho sudá transpozice(tedy prohození sousedních čísel) se složitostí <math>2*O(1) => O(1)</math>.
-   * Pokud <math>p \leq N</math> pak třeba pamatovat, že se obecně neprovádí výměna čísel (CE) v čase O(1) ale tzv. Merge&Split (MS) v čase <math>O( \beta \frac N p)</math>, dle zadání. MS je vzájemná výměna s následným sloučením 2 seřazených posloupností(velikosti N/p) mezi 2 procesory. Výsledkem sloučení je vytvoření dvou nových posloupností velikosti N/p tak, že první procesor si nechá N/p menších čísel (souhrnně z obou posloupností) a druhý procesor si nechá všech N/p větších čísel.
-   * Pokud <math>p \leq N</math> pak na jeden procesor připadá více než jedno číslo a je nutno tyto čísla nejprve seřadit v čase <math>\alpha k \log k</math>.
-Paralelní čas se skládá ze součtu těchto částí, tedy
-<math>T(N,p) =sekv.serazeni \frac N p cisel + 4 \cdot T_{2DSort} \cdot Merge'N'Split+ 2\cdot Transpozice</math>
-<math> T(N,p) = \alpha \frac N p log \frac N p + 4 \beta \frac N p \gamma \sqrt[3]p + 2 \beta \frac N p = \alpha \frac N p log \frac N p + (2 \beta \frac N p ) \cdot ( 2 \gamma \sqrt[3] p + 1)</math>
-jedničku zanedbám
-<math> T (N,p) = \alpha \frac N p log \frac N p + 4 \beta \gamma \frac N {\sqrt[3]p^2}</math>
-<math>C(N,p) = p \cdot T(N,p) = \alpha N log \frac N p + 4 \beta \gamma \sqrt[3] p N</math>
-<math>E(N,p) = \frac {SU(n)} {C(N,p)} = \frac {N log N} {\alpha N log \frac N p + 4  \beta \gamma \sqrt[3] p N} = \frac {log N} {\alpha log \frac N p + 4 \beta \gamma \sqrt[3] p}</math>
-:?: Ten vzoreček na čas podle skript a přednášky není dobře. Chybí tam <math>log(p)</math>, správně by to mělo být <math> T (N,p) = O(\frac N p log (\frac N p)) + O(\frac N {\sqrt[3]p^2} log(p)) </math>. Výpočty, pak logicky nevycházejí tak, jak mají... Můj výpočet <math>\psi_1(p)</math> a <math>\psi_2(N)</math>. (maurever)
-:!: Nicméně ve skriptech i přednášce je v rovinách použit Shearsort, tenhle výpočet je korektní vzhledem k zadání, s tím log(p) je výpočet níže na této stránce.
-{{:škola:předměty:mi-par:par_3dsort.jpg?200|}}
-=== Škálovatelnost ===
-<math>E(N,p) = E_0 => log N = E_0 \alpha log \frac N p + 4  E_0 \beta \gamma \sqrt[3] p</math>
-<math>(1-E_0 \alpha) log N = - E_0 \alpha log p + 4 E_0 \beta \gamma \sqrt[3] p</math>
-<math>\underbrace {(\frac {- E_0 \alpha} {1 - E_0 \alpha})}_{\delta}  logp + \underbrace{(\frac {4  E_0 \beta \gamma} {1 - E_0 \alpha})}_{\xi} \sqrt[3] p = log N</math>, log p muzeme vuci <math>\sqrt[3] p</math> asymptoticky zanedbat, s tím, že předpokládáme <math>p \gg \xi \text{ and } p \gg \delta</math> (Tady by bylo vhodné zmínit, že např. pro <math>p = 1000</math> vychází <math>\sqrt[3] p \approx logp </math>. log roste rychleji, ale je to něco jiného než zanedbání loglog)
-<math>N \approx 2^{\xi \sqrt[3] p} = \psi_1 (p) </math>
-<math> \xi \sqrt[3] p = log N => p = \frac {log^3 N} {\xi^3} = \psi_2 (n) </math>
-Hledáme psi3, což je čas při optimálním # procesorů <math>p_{opt}</math>, který je asymptoticky roven spodní mezi <math>T_{min}</math>. Spodní mez nastane evidentně pro p=N.
-<math>T(N,N) = \alpha \frac{N}{N} log \frac{N}{N} + 4 \beta \gamma N N^{-\frac{2}{3}} = \alpha 0 + 4 \beta \gamma N^{\frac{1}{3}}</math>
-<math>T_{min} = O(N^{\frac{1}{3}}) = O(\sqrt[3]{N})</math>
-Teď potřebujeme najít takové p, pro které bude platit
-<math>T(N,p) = O(T_{min})</math>
-<math>\alpha \frac{N}{p} log \frac{N}{p} + 4 \beta \gamma N p^{-\frac{2}{3}} = O(\sqrt[3]{N})</math>
-Je to součet 2 funkcí, obě jsou klesající. Musí platit, že
-<math>\alpha \frac{N}{p} log \frac{N}{p} = O(\sqrt[3]{N}) \text{  and  } (4 \beta \gamma N p^{-\frac{2}{3}} = O(\sqrt[3]{N})</math>
-Vyřeším 2.část obdobně jako u ShearSortu
-<math>(4  \beta \gamma \frac N {\sqrt[3] p^2} = O( 4 \beta \gamma \sqrt[3] N) => \frac N {\sqrt[3] p^2} = O( \sqrt[3] N) => \sqrt[3] p^2 = \Omega (\sqrt[3] N^2)</math>
-<math>p = \Omega (N)</math>, jelikož je <math>1 \leq p \leq N</math>, pak <math>p = N</math>
-Pokud dosadíme výraz <math>p = \Omega (N) = \Theta (N)</math> do 1.části, zjistíme, že <math>\alpha \frac{N}{\Theta(N)} log \frac{N}{\Theta(N)} = \alpha const * log const</math> což evidentně platí (je menší než 3.odmocnina z N)
-<math>\psi_3 (n) = N</math>
-=== Modifikace pro Shear Sort ===
-<hidden onHidden="**[+] 3D sort z 8 bodových příkladů řešený Shear Sortem**" onVisible="**[-] 3D sort z 8 bodových příkladů řešený Shear Sortem**">
-**Časová složitost**
-<math>T_{1} = T_{2} = T_{3} = T_{5} = T_{2Dsort}, T_{4} = 2 = O(1)</math>\\
-Při použití p < N procesorů je časová složitost:\\
-<math>T(N,p) = 4 . T_{2D}(\sqrt[3]{N^2}, \sqrt[3]{p^2} )</math>\\
-\\
-Pro náš případ zvolíme pro 2D třídení algoritmus ShearSort.\\
-Ten funguje tak, že:\\
-) paralelně setřídí všechny řádky střídavým směrem\\
-) paralelně setřídí všechny sloupce\\
-\\
-Provedením 1 řádkové fáze a 1 sloupcové fáze se počet nečistých řádku sníži na polovinu => po log n fázích na M(n,n) se <math>n^2</math> procesory zůstane max. 1 nečistý řádek \\
-=> celkem potřebuji <math>(2log n + 1)</math> kroků. \\
-\\
-Každý z nich má složitost O(n) = třídení v lineární mřížce\\
- => složitost ShearSortu je: <math>T(n,n) = O ( n . log n^2 ) = O( \sqrt{N} .log{N} )</math>, kde N je počet uzlů.\\
-\\
-Každé volání ShearSortu je následováno otočením každého druhého řádku ( ShearSort setřizuji hadovitě ).\\
-\\
-Složitost této operace je <math>O(\sqrt{N}) </math> => <math>T_{3D}(N,N) = O (4.(\sqrt[3]{N} . log \sqrt[3]{N^2} + \sqrt[3]{N})) = O(\sqrt[3]{N} . log{N})</math>\\
-\\
-Pro p < N je třeba provést lokální setřídení => <math>\frac{N}{p}log\frac{N}{p}</math> a místo operace CE provést MS ( merge - split ) jejíž velikost není O(1) ale\\
-<math>O(\frac{N}{p})</math> => <math>T_{3D}(N,p) = O (\frac{N}{p}.log\frac{N}{p} + \frac{N}{p}.\sqrt[3]{p}.log p) = O(\frac{N}{p}.log\frac{N}{p} + \frac{N}{\sqrt[3]{p^2}}.log p)</math>\\
-\\
-<math>C(N,p) = O(N.log\frac{N}{p} + N.\sqrt[3]{p}.log p) => E(N,p) = \frac{SU(N)}{C(N,p)} = \frac{log N}{log\frac{N}{p}+\sqrt[3]{p}.log p}</math>\\
-**Škálovatelnost**
-:!://Viz skripta CZ [2006] str. 12//
-<math>\psi_{1}: \forall N_{p} = \Omega(\psi_{1}(p)): E(N_{p},p) \geq{E_{0}}</math>\\
-<math>\frac{logN}{logN - logp + \sqrt[3]{p}.logp} = E_{0} </math>\\
-=><math> logN = E_{0}.logN + E_{0}.logp.(\sqrt[3]{p} - 1)</math>\\
-<math>logN(1-E_{0}) = E_{0}.logp.(\sqrt[3]{p} - 1)</math>\\
-<math>logN = \frac{E_{0}}{1-E_{0}}.logp.(\sqrt[3]{p} - 1)</math>
-\\
-=> subst.: <math>k = (\frac{E_{0}}{1-E_{0}} ) </math>\\
-=> <math>N = ((2^{logp})^{\sqrt[3]{p} - 1})^k = p^{k.\sqrt[3]{p}}</math>
-\\
-\\
-<math>\underline{\underline{\psi_{1}(p) = p^{k.\sqrt[3]{p}}}}</math>\\
-\\
-\\
-<math>\psi_{2}: \forall p_{N} = O ( \psi_{2}(N) ): E ( N, p_{N} ) \geq{E_{0}}</math>\\
-\\
-<math>logN = K. logp.\sqrt[3]{p} </math>=> zajímá mě asymptoticky\\
-\\
-a) nahradím <math>logp</math> pomocí <math>\sqrt[3]{p} > logp </math>=><math> logN < K.p</math>\\
-\\
-b) nahradím <math>logp</math> pomocí <math>1 => 1 < logp => log N > \sqrt[3]{p} => log^{3}N > p</math>\\
-\\
-z a) a b) => <math>logN \leq{p} \leq{log^{3}N} </math>=><math> loglogN \leq{logp} \leq{loglog^{3}N} = 3loglogN </math>=><math> logp = loglogN </math>=>\\
-=> <math>logN = K loglogN.\sqrt[3]{p} </math>=><math> \sqrt[3]{p} = \frac{logN}{loglogN} </math>=><math> p = (\frac{logN}{loglogN})^{3} </math>=>\\
-\\
-=> <math>\underline{\underline{\psi_2(N) = (\frac{logN}{loglogN})^{3}}}</math>
-**PSI_2 malinko přehledněji:**
-<math>n = p^{K\cdot\sqrt[3]{p}}</math> -> <math>logn = K\cdot\sqrt[3]{p}\cdot log p</math>, to zlogaritmuju na <math>loglogn = logK + \frac{1}{3}logp + loglogp</math>
-Muzu zanedbat <math>logK</math> a vuci <math>logp</math> i <math>loglogp</math>. Takze mam <math>loglogn = \frac{1}{3}logp</math> a tedy <math>3 loglogn = logp</math>. Trojku nesmim zanedbat.
-A ted uz jen dosadim do puvodni rovnice, tj. <math>logn = K\cdot\sqrt[3]{p}\cdot 3loglogn</math> a vydelenim dostanu, ze <math>\frac{logn}{3Kloglogn} = \sqrt[3]{p}</math>, z cehoz je <math>p = (\frac{logn}{3Kloglogn})^3</math> a <math>\psi_2(n) = (\frac{logn}{loglogn})^{3}</math>
-</hidden>
-Víme, že složitost Shear Sortu je
-<math>T_{shear}(N,p)=
-\underbrace{\lceil(2\log{\sqrt{p}+1})\rceil}_{\text{pocet fazi}}\cdot EOTSort \cdot M\&S</math>
-EDIT: zdá se mi, že tu chybí vynásobení nějakou transformací. Shearsort řadí hadovitě a my to potřebujeme mít klasicky, takže musíme přehodit každý druhý řadek. (viz přednáška 8, 2014, 01h:01m)
-:?: Na zkoušce 5.2.2016 mi řekl, že správně má být u logaritmu +2 a ne +1 právě kvůli nějaké transformaci. Netuším přesně proč.
-<math>T_{3Dshear}(N,p)=
-\lceil(2\log{\sqrt[3] p+1})\rceil\cdot
-\sqrt[3]{p}\cdot
-\beta\frac{N}{p}</math>
-Celkový čas 3D sortu potom vypadá takto:
-<math> T(N,p) = \alpha \frac N p log \frac N p + \frac{8}{3}\beta \frac {N}{\sqrt[3] p^2} \log p + 2 \beta \frac N p </math>
-<math> C(N,p) = \alpha N log \frac N p + \frac{8}{3}\beta N \sqrt[3] p \log p + 2 \beta N</math>
-<math> E(N,p) = \frac {N log N} {\alpha N log \frac N p + \frac{8}{3}\beta N \sqrt[3] p \log p + 2 \beta N} = \frac {log N} {\alpha log \frac N p + \frac{8}{3}\beta \sqrt[3] p \log p + 2 \beta} = E_0</math>
-== Škálovatelnost ==
-<math>log N = E_0 \alpha log \frac{N}{p} + 2 E_0 \beta + \frac{8}{3} E_0 \beta \sqrt[3] p log p</math>
-<math>log N = E_0 \alpha log N - E_0 \alpha log p + 2 E_0 \beta + \frac{8}{3} E_0 \beta \sqrt[3] p \cdot log p</math>
-<math>log N =
-\underbrace{ \frac{- E_0 \alpha}{1-\alpha E_0}}_{\text A} log p +
-\underbrace{ \frac{2 E_0 \beta}{1-\alpha E_0}}_{\text B} +
-\underbrace{ \frac{8 E_0 \beta}{3 (1- \alpha E_0)}}_{\text C} \sqrt[3] p \cdot log p
-</math>
-<math>
-N = O( 2 ^{log p \cdot C \cdot \sqrt[3] p}) = O( p ^{C \sqrt[3] p}) = \psi_1 (p)
-</math>
-<math>
--B + log N = -A log p + C \sqrt[3] p \cdot log p
-</math>
-<math>A log p </math> můžeme asymptoticky zanedbat. Po zlogaritmování potom dostaneme:
-<math>
-log p = \frac{1}{3C} log log N
-</math>
-Zpětným dosazením dostáváme:
-<math>
-C \sqrt[3] p = \frac{3C log N}{log log N} \rightarrow p= O(( \frac{log N}{log log N})^3) = \psi_2 (N)
-</math>
 ===== Násobení matice vektorem, mapování matice blokově šachovnicově =====
 Násobení matice vektorem, mapování matice <math>A(sqrt{N}, sqrt{N} )</math> BLOKOVĚ šachovnicově na 2D mřížku <math>M(sqrt{p}, sqrt{p} )</math>, vektor <math>X(sqrt{N})</math> na první sloupec procesorů mapovaných šachovitě, WH. Popsat algoritmus, co nejpřesněji T(N, p), spočítat Ψ1(p), Ψ2(N). Sekvenční násobení matice <math>r</math>x<math>r</math> vektorem <math>r</math> trvá čas <math>\alpha r^{2}</math>.