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: 2013-02-06, 2012-01-31 a 2011-01-10

Řešení je podrobně popsané i zde.

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 zde

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>

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: 2015-01-28, 2014-01-13,2013-01-16,2012-02-10 - všude za 10b bez psí_3

Viz FIT [2012] přednáška 8 slide 19, skripta CZ [2006] str. 121 nebo EN [2009] str. 117

1. Faze - Setrid vsechny xz-roviny v zx-poradi.
2. Faze - Setrid vsechny yz-roviny v zy-poradi.
3. Faze - Setrid vsechny xy-roviny v yx-poradi stridave ve smeru y.
4. Faze - Proved jednu licho-sudou a jednu sudo-lichou transpozici ve vsech sloupcich.
5. 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

1. Po fázi 1, v každé xz-rovině existuje nejvýše 1 nečistý řádek, a proto :
   1. jakékoliv 2 yz-roviny se mohou lišit v nejvýše n nulách
   2. všech n yz-rovin obsahuje ve svých nečistých řádcích souhrnně nejvýše <math>n^2</math> prvků
2. Tudíž po fázi 2 všechny nečisté řádky mohou překlenout nejvýše 2 xy-roviny.
3. Je-li nečistá xy-rovina pouze jedna, jdeme přímo na fázi 5 a jsme hotovi.
4. Existují-li 2 nečisté xy-roviny, fáze 3 a 4, vyčistí aspoň 1 z nich a fáze 5 dokončí řazení.

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

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

<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:
1) paralelně setřídí všechny řádky střídavým směrem
2) 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 = ¹⁾:
<math>\log_z (t_{s} + m t_m) + (z - 1) t_d </math>

<math>log sqrt p(t_{s}+\frac{sqrt N}{sqrt p}t_{m}) + (sqrt p -1)t_{d}</math>

• Krok 3) Lokální násobení submatic zabere (je přímo v zadání příkladu):

<math>\alpha (\frac{sqrt N}{sqrt p})^{2} = \alpha \frac{N}{p}</math>

• Lokální redukce na jedno číslo (každý řádek ze své submatice musí zredukovat na jedno číslo):

<math> \frac{sqrt N}{sqrt p} \frac{sqrt N}{sqrt p} = \frac{N}{p} </math>

• Krok 4) Paralelní redukce (každý procesor má už nyní pouze sloupcový subvektor):

<math>\frac{sqrt N}{sqrt p} \log {\sqrt p}</math>

Postup je skoro stejný jako v případě 1, asymptoticky by měl vyjít stejně.

Podle skript se v třetí fázi pouze sekvenčně udělá vše potřebné, takže tam další přepočty nedělám a také podle skript je fáze druhá a čtvrtá asymptoticky stejná, tak je tak i rovnou počítám.

Tedy

1. Krok 1: Poslat vektor části vektoru X na diagonálu
2. Krok 2: OAB ve sloupci
3. Krok 3: Lokální násobení submatic
4. Krok 4: Paralelní redukce (dle skript Krok 4 = O(Krok 2), tak ho tam prostě počítám dvakrát)

<math>T(n,p) = \underbrace{t_{s} + (\sqrt{p}-1)t_{d}+ \frac{\sqrt{N}}{\sqrt{p}}t_{m}}_{\text{Krok 1}} + \underbrace{2 \log \sqrt{p}(t_{s}+(\frac{\sqrt{N}}{\sqrt{p}})t_{m}) + 2(sqrt{p}-1)t_{d}}_{\text{Krok 2 + Krok 4}} + \underbrace{\alpha \frac{N}{p}}_{\text{Krok 3}}</math>

Jak je vidět, Krok 1 je asymptoticky menší než krok 2, takže ho k tomu asymptoticky přičtu :

<math>T(n,p) = 2 \log \sqrt{p}(t_{s}+(\frac{\sqrt{N}}{\sqrt{p}})t_{m}) + 3(sqrt{p}-1)t_{d} + \alpha \frac{N}{p}</math>
<math>T(n,p) = 2 \log \sqrt{p} t_{s} + 2 \log \sqrt{p} \frac{\sqrt{N}}{\sqrt{p}} t_{m} + 3 sqrt{p} t_{d} + \alpha \frac{N}{p}</math>

<math>C(n,p) = 2 p \log \sqrt{p} t_{s} + 2 \sqrt{p} \log \sqrt{p} \sqrt{N} t_{m} + 3 p sqrt{p} t_{d} + \alpha N</math>

Sekvenční algoritmus pracuje dle zadání : <math> \alpha \frac{N}{p}</math>, pro jeden procesor to tedy bude : <math> \alpha N</math>

<math>SU(n) = \alpha N </math>

<math>E(n,p) = \frac{SU(n)}{C(n,p)} = E_0</math>

<math>\frac{\alpha N}{2 p \log \sqrt{p} t_{s} + 2 \sqrt{p} \log \sqrt{p} \sqrt{N} t_{m} + 3 p sqrt{p} t_{d} + \alpha N} = E_0</math>

<math>\alpha N= 2 p \log \sqrt{p} t_{s} E_0 + 2 \sqrt{p} \log \sqrt{p} \sqrt{N} t_{m} E_0 + 3 p sqrt{p} t_{d} E_0 + \alpha N E_0 </math>

<math>2 p \log \sqrt{p} t_{s} E_0 = O(3 p sqrt{p} t_{d} E_0) </math>
levý zanedbáme a pravý je vždy větší

<math>\alpha N \dot= 2 \sqrt{p} \log \sqrt{p} \sqrt{N} t_{m} E_0 + 3 p sqrt{p} t_{d} E_0 + \alpha N E_0 </math>

<math>- 2 \sqrt{p} \log \sqrt{p} \sqrt{N} t_{m} E_0 = 3 p sqrt{p} t_{d} E_0 + \alpha N E_0 - \alpha N </math>

<math> 2 \sqrt{p} \log \sqrt{p} \sqrt{N} t_{m} E_0 = - 3 p sqrt{p} t_{d} E_0 - \alpha N E_0 + \alpha N </math>

<math> 2 t_{m} E_0 \sqrt{p} \log \sqrt{p} \sqrt{N} = - t_{d} E_0 3 p sqrt{p} + N (\alpha - \alpha E_0) </math>

<math> 2 t_{m} E_0 \sqrt{p} \log \sqrt{p} \sqrt{N} = N (\alpha - \alpha E_0) - t_{d} E_0 3 p sqrt{p} </math>

<math> \underbrace{2 t_{m} E_0}_{\beta} \sqrt{p} \log \sqrt{p} \sqrt{N} = N \underbrace{(\alpha - \alpha E_0)}_{\gamma} - \underbrace{3 t_{d} E_0}_{\delta} p sqrt{p} </math>

<math> \beta \sqrt{p} \log \sqrt{p} \sqrt{N} = \gamma N - \delta p sqrt{p} </math>

Nyní je potřeba udělat rovnici se zanedbáním jedné části, pak se zanedbáním druhé části a pak asymptoticky vybrat to asymptoticky menší/větší (podle toho, jestli si vyjádřím “p” nebo “N”)

Pokud se podívám, na původ těch výrazů, zjistím následující :

<math> \underbrace{\beta \sqrt{p} \log \sqrt{p} \sqrt{N}}_{\text{Posilani dat v kroku 2,4 }} = \underbrace{\gamma N}_{\text{ Sekvencni cast }} - \underbrace{\delta p sqrt{p}}_{\text{ Vytvareni cesty v kroku 2,4}} </math>

Sekvenční část musí zůstat vždy, ale můžu úlohu rozdělit na dvě části, tj. jednou počítat jenom s posíláním dat a jednou s vytvářením cesty.

Nechám v rovnici posílání dat :

<math> \beta \sqrt{p} \log \sqrt{p} \sqrt{N} = \gamma N </math>

<math> \beta \sqrt{p} \log \sqrt{p} = \gamma \sqrt{N} </math>

<math> \frac{\beta^2 p \log^2 \sqrt{p}}{\gamma^2} = N </math>

<math> N = \frac{\beta^2 p \log^2 \sqrt{p}}{\gamma^2} \dot = p \log^2 {p} = \psi_{1_a}(p) </math>

Nechám v rovnici druhou část pro vytváření cesty :

<math> 0 = \gamma N - \delta p sqrt{p} </math>

<math> \delta p sqrt{p} = \gamma N</math>

<math> \frac{\delta p sqrt{p}}{\gamma} = N</math>

<math> N = \frac{\delta p sqrt{p}}{\gamma} \dot= p sqrt{p} = \psi_{1_b}(p)</math>

Teď obě rovnice “zmerguju”. Vycházím z toho, že <math> \psi_1(p) </math> je asymptoticky MINIMÁLNÍ (viz definice v první přednášce). Zajímá nás tedy co nejmenší možné. Z toho, co jsme vypočítali víme že :

<math> N = \Omega(p sqrt{p}) </math>
<math> N = \Omega(p \log^2 {p}) </math>

Aby obě dvě rovnice platili zároveň, tak N musí být nejméně řádu <math> p sqrt{p} </math> a tedy :

<math> N = p sqrt{p} = \psi_1(p) </math>

A druhá část je hned :

<math> N = p sqrt{p} </math>

<math> N = p^{\frac{3}{2}} </math>

<math> N^{\frac{2}{3}} = p </math>

<math> N^{\frac{2}{3}} = \sqrt[3]{N^2} = p = \psi_2(N) </math>

Tak jsem volal s Tvrdíkem po skypu a toto řešení je SPRÁVNĚ. Ve skriptech má drobnou nepřesnost, pro 2D mřížku je opravdu takováto složitost. (On to má ve skriptech jako pro hyperkrychli a 2D mřížku, ale ve skutečnosti to platí pouze pro hyperkrychli, pro 2D mřížku platí to, co jsem tady napsal).

Tento postup je sice správný, ale prý zbytečně složitý a pro některé případy nepoužitelný (třeba pro větší odmocniny jak ze dvou).

Nyní vzhledem k dalším obtížným úpravám to zredukuji asymptoticky co nejvíce. Potřebuji se zbavit odmocniny z N, což mohu udělat tímto způsobem

Pro přehlednost jsem tento alternativní postup dal do zvláštní stránky, pro většinu případů se vám bude hodit spíše znalost postupu 2.2. Na alternativní řešení se můžete podívat zde

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