Odvoďte spodní meze <math>\normalsize \rho_{OAS}</math> na počet kroků,<math>\normalsize \gamma_{OAS}</math> na paralelní součet délek použitých cest a <math>\normalsize \tau_{OAS}</math> na komunikační časovou složitost operace rozesílání jeden-všem (OAS) v kombinujícím 2-portovém 2-D toroidu <math>\normalsize K(z_1,z_2)</math> s červím přepínáním (WH), jestliže zdrojový uzel <math>\normalsize s=[a_1,a_2]</math> má pro každý uzel připravený packet o velikosti m. Předpokládejte, že přenos packetu o velikosti <math>\normalsize \mu</math> na vzdálenost d trvá čas <math>\normalsize t(d,\mu)=t_s+dt_d+\mu t_m</math>. Popište co nejefektivnější OAS algoritmus za těchto podmínek. Odvoďte jeho počet kroků <math>\normalsize r_{OAS}</math>, paralelní součet délek použitých cest <math>\normalsize g_{OAS}</math> a komunikační zpoždění <math>\normalsize t_{OAS}</math> a porovnáním se spodními mezemi vyhodnoťte jeho optimalitu.

★ Bylo ve zkoušce: 2013-01-16 a NE2012-01-24 a 2011-01-17 a 2015-01-06 (ale všeportový)

mi-par2014-prednaska10-kko1.pdf slide 40

Spodní mez na počet kroků: V prvním kroku to vědí 3, v dalším 3×3=9 … Takže vzorec je <math>\rho=\lceil log_{d+1}(V(G))\rceil = \lceil log_{3}(z1.z2)\rceil</math> (d - počet portů)

Spodní mez na paralelní součet délek: diam(G) = exc(s, G), u 2-D toroidu <math>\lfloor \frac{z_1}{2} \rfloor + \lfloor \frac{z_2}{2} \rfloor</math>

Časová složitost: <math>\tau = \lceil log_{3}(z1 z2) \rceil ts + (\lfloor \frac{z_1}{2} \rfloor + \lfloor \frac{z_2}{2} \rfloor) td + \lceil \frac{z1 z2 - 1}{2} \rceil \mu tm</math>

Algoritmus: Ternární rozesílání - zdroj vezme jednu třetinu adresátů, tu si nechá, zbylé dvě třetiny rozešle doprava a doleva. V první fázi algoritmu rozesíláme data jen po kružnici 1D. Po té, co proběhne OAS na kružnici začnou uzly rozesílat data po svých jednotlivých kružnicích, takže musíme pouze vyřešit rozesílání po kružnici. V každém kroce se velikost paketu zetřetinuje a na třetinu klesne i vzdálenost. Celé je to geometrická řada.

Počet kroků tohoto algoritmu je <math>\rho=\lceil log_{3}(z1.z2)\rceil</math>, protože v každém kroku každý uzel posílá data.

JDU: doporučuju přejít na řešení 2. Dejte sem nějak vědět, který z těch řešení je tedy dobře, ať se to špatné smaže.
řešení1:
řešení2:+

Celková poslaná vzdálenost je z1.(z2-1)/2 , tento vzorec dostaneme sečtením řady <math>z1*(\frac{1}{3}*\frac{\frac{1}{z2}-1}{\frac{1}{3}-1})</math>

Další věc, kterou musíme spočítat pro dosazení je celková odeslaná velikost. To je opět geometrická řada a dostaneme <math>\frac{z1*z2-1}{2}</math>

Komunikační zpoždění je po dosazení: <math>T=log_{3}(z1*z2)*ts+z1*\frac{z2-1}{2}*td+log_{3}(z1*z1)*\frac{z1*z2-1}{2}*tm</math>

Srovnání optimality: Algoritmus je optimální.

Poznámky: Za bernou minci berte myšlenky, ač jsem si to nechal zkontrolovat od Tvrdíka, tak je možné, že tam nějaký chybky zbyly. Ptal jsem se ho ještě na to, jestli je lepší vybrat pro první broadcast delší rozměr, nebo kratší, ale to je už prý mimo předmět.

EDIT 1: : Kde sa v riešení vzala časť: <math>log_{3}(z1*z1)</math> ? Nemá byť riešením len: <math>T=log_{3}(z1*z2)*ts+\frac{z1*z2-1}{2}*td+\frac{z1*z2-1}{2}*tm</math> ? Obdobne ako je to v príklade pre 1-port OAS.

EDIT 2: Podle mě je to tam protože tolik se provede kroků. Jinak řečeno: Na začátku má zpráva velikost Z1*Z2, na konci 1. Průměrně v každém kroku tedy <math>(z1*z2-1)/2</math>. A celkem kroků je <math>log_{3}(z1*z2)</math>. Dohromady to dá tedy výsledek výše

Podle prosemináře 2013 bych řekl, že výsledek je:

První komunikuji v první dimenzi:

<math> t_{OAS}(K(z_{1})) =
t_{s} + \frac{z_{1}}{3}t_{d} + \frac{z_{1} * z_{2} - 1}{3}mt_{m} +
t_{s} + \frac{z_{1}}{9}t_{d} + \frac{z_{1} * z_{2} - 1}{9}mt_{m} +
… </math>

Součet:

<math> t_{OAS}(K(z_{1})) = log_{3}(z_{1})t_{s} + \frac{z_{1}-1}{3-1}t_{d} + … cekam\_na\_dokonceni\_rady …

t_{OAS}(K(…, z_{2})) = log_{3}(z_{2})t_{s} + \frac{z_{2}-1}{3-1}t_{d} + … dale …

t_{OAS}(K(z_{1}, z_{2})) = log_{3}(z_{1}z_{2})t_{s} + \frac{z_{1} + z_{2} - 2}{2}t_{d} + \frac{z_{1}z_{2} - 2}{2}mt_{m} </math>

Vysvětlení: ts + nechám si 1/3 a zbytek pošlu na obě strany + mám zprávu (z1*z2-1), kterou postupně dělím na 1/3.

JDU: Nemám náhodou v první dimenzi zprávu pouze (z1*z2-z2), kterou dělím na třetiny? (v první dimenzi se zprávy, které bude zdroj posílat do druhé dimenze, dělit nemusí).

Vysvětlete a popište Cannonův algoritmus paralelního násobení čtvercových <math>\sqrt{N}</math> x <math>\sqrt{N}</math> matic C=AB na všeportové hyperkrychli Q_{log p}, p<N. Odvoďte výraz pro paralelní čas T(N,p) jestliže:

1) směrovače provádí WH přepínání paketů, kde přenos paketu o velikosti µ mezi dvěma uzly ve vzdálenosti d trvá t(d,µ)=t_s+dt_d+µt_m.
2) prvky matic mají velikost m
3) sekvenční lokální násobení dvou matic o velikosti <math>r \times r</math> trvá čas <math>\alpha r^3</math>, kde <math> m </math> a <math>\alpha</math> jsou konstanty. Pro zadanou efektivnost <math>E_0</math> odvoďte izoefektivní funkce <math>\psi_1 (p)</math> a <math>\psi_2(N)</math>. Dále odvoďte spodní mez <math>\psi_3(N)</math> na počet procesorů pro dosažení asymptotické časové optimality.

Tohle jsem řešil půlku zkoušky a Tvrdik mi řekl, že jsem došel docela daleko, takže:

Cannon je vlastně:

1. cyklická rotace ve směru H
2. cyklická rotace ve směru V
3. vynásobení
4. <math>\sqrt{p}</math> * (rotace V + rotace H + násobení)

celkem tedy: <math> \sqrt p * ( T_{komunikace} + T_{nasobeni})</math>. Vzorce máte zadané, na konstanty moc nehleďte, jen aby tam byla všechna písmenka, co tam mají být. Jestli je tam někde plus mínus jedna je vcelku jedno.

<math>\Psi_1(p) = n^2</math>, <math>\Psi_2(n) \sqrt{p}</math> - inverzní k <math>\Psi_1</math>.

Problém nastává při počítání Tmin, kde vám vyjde docela hnusná derivace. Prý se tam dá jeden člen zanedbat, pokud uvažujute p v rozsahu 1 až n. Musíte si tedy tu rovnici rozdělit na několik součtů a místo A1 + A2 = A3, řešit asymptoticky A1 = A3 a A2 = A3. Viz jak to říkal na prosemináři.

Řešení ze semináře pro dálkaře
<math>T_{1} = T_{2} = ts + \sqrt{p} / 2 * n^2 / p * tm</math>
proč se zde nepočítá s klasickým vzorcem pro WH tedy <math> t_s + dt_d + mt_m</math> ? kde je parametr <math>t_d</math> ?
<math>T_{3} = \sqrt{p} * (Su (n/ \sqrt{p}) + 2ts + n^2 / p * tm)</math>
<math>Su(k) = dk^3 </math>

Možný důvod absence <math>t_d</math> :

Finální asymptotický čas (ten úplně dole - podle skript) už <math>t_d</math> neobsahuje, ale pravděpodobně došlo pouze k jeho zanedbání. Moje představa je taková, že při mapování virt. mřížky do hyperkrychle (BRGC), kdy se řádek <math>\sqrt{p}</math> dlouhý mapuje do podkrychle <math>Q_{log\sqrt{p}}</math>, dochází k tomu, že můžu v rámci té 1D mřížky dělat zkratky. Je celkem jasný, že průměr téhle podkrychle je <math>log\sqrt{p}</math>, což znamená, že nejvzdálenější uzly na mřížce už nebudou od sebe <math>\sqrt{p}</math>, ale právě ten log.

Pokud tam nakonec vyjde něco jako <math>O(t_d log\sqrt{p})</math>, přebije to <math>t_s sqrt{p}</math>

Teorie: Imho jde o algoritmus “Permutační směrování na hyperkrychli” (viz přednáška 9 (2014/2015), slide 38). Mělo by to fungovat, pokud je matice mapovaná šachovnicově do 2D mřížky vnořené do hyperkrychle pomocí BRGC. (Inception)

Pak se tedy cyklický posun realizuje pomocí nějakého xoru a e-cube směrování (nebudou kolize). Tohle vysvětluje, proč je daná permutace hotová vždy na jeden krok.

Proč se tu počítá s maticí <math>\normalsize n \times n</math>, když je zadaná <math>\normalsize \sqrt(N) \times \sqrt(N)</math>

<math>T(n^2,p) = 2(ts + \sqrt{p} / 2 * n^2 / p * tm) + \sqrt{p} * ( (n/ \sqrt{p})^3 + 2ts + n^2 / p * tm)</math>

: Toto je riešenie pre hyperkrychlu. Na seminári bol riešený Cannon pre toroid: Poznámky proseminář_09. Aj na skúške v 2010/2011 bol Cannon pre Toroid.

Podle anglických skript (str. 185) je celková složitost pro všeportovou WH hyperkrychli <math>Q_{\log {p}}</math> následující :

<math>T_{Cannon}(N, p) \dot= t_s sqrt{p} + \frac{N}{\sqrt{p}} t_m + O ( \frac{n^3}{p} )</math>

Popište a vysvětlete Cannonův algoritmus paralelního násobení čtvercových <math>\sqrt N \times \sqrt N</math> matic <math>C = AB</math> na 1-portovém 2-D toroidu <math>K (\sqrt p, \sqrt p)</math> procesorů, kde <math>p < N</math>. Odvoďte co nejpřesněji výraz pro paralelní čas <math>T (N,p)</math>, jestliže (1) směrovače provádějí červí (WH) přepínání paketů, kde přenos paketu o velikosti <math> \mu </math> mezi 2 uzly ve vzdálenosti d trvá <math>t(d, \mu) = t_s + dt_d + \mu t_m</math>, (2) prvky matic mají velikost <math> m </math> a (3) sekvenční lokální násobení dvou matic o velikosti <math>r \times r</math> trvá čas <math>\alpha r^3</math>, kde <math> m </math> a <math>\alpha</math> jsou konstanty. Pro zadanou efektivnost <math>E_0</math> odvoďte izoefektivní funkce <math>\psi_1 (p)</math> a <math>\psi_2(N)</math>. Dále odvoďte spodní mez <math>\psi_3(N)</math> na počet procesorů pro dosažení asymptotické časové optimality.

★ Bylo ve zkoušce: 2012-02-03

Viz skripta CZ [2006] str. 199, obdobná varianta příkladu (avšak SF, tudíž čísla nejsou stejná!) je též vysvětlena na videu z 13. prosemináře 2013.

Algoritmus má celkem tři fáze:

1. horizontální cyklická rotace řádku i v matici A o i-1 pozic doleva,
2. vertikální cyklická rotace sloupce k v matici B o k-1 pozic nahoru,
3. cyklus <math>\sqrt p</math>x;
   1. násobení submatic na procesorech,
   2. cyklická rotace v matici A o 1 pozici doleva,
   3. cyklická rotace v matici B o 1 pozici nahoru.

FAZE 1
for all i = 1,…,<math>sqrt p</math> doIP všechny submatice <math>A_i_,_*</math> v řádku i rotace o i-1 pozic doleva

FAZE 2
for all k = 1,…,<math>sqrt p</math> doIP všechny submatice <math>B_*_,_k</math> v sloupci k rotace o k-1 pozic nahoru

FAZE 3
repeat <math>sqrt p</math> times
{
for all i,k = 1,…<math>sqrt p</math> doIP <math>P_i_,_k</math> vynásobí momentální submatice A*B a přičte do <math>C_i_,_k</math>
for all i = 1,…,<math>sqrt p</math> doIP všechny submatice <math>A_i_,_*</math> v řádku i rotace o 1 pozici doleva
for all k = 1,…,<math>sqrt p</math> doIP všechny submatice <math>B_*_,_k</math> ve sloupci k rotace o 1 pozici nahoru
}

doIP = do_In_Parallel

[základ podle Poznámek z prosemináře 9 ZS 11/12 ]

<math>T(N,p) = T_1(N,p) + T_2(N,p) + T_3(N,p)</math>

První dvě fáze mají shodnou složitost, liší se pouze dimenzí, ve které se rotuje. Výpočet složitosti vychází ze zadaného vzorce pro komunikační zpoždění. Jedná se o rotaci na kružnici o 0 až <math>\normalsize \sqrt p</math> (délka jedné strany) pozic. Vybereme si vždy nejkratší směr, takže nejdelší vzdálenost bude rovna polovině, tedy <math>\normalsize d = \frac{\sqrt p}{2}</math>. Velikost paketu odpovídá velikosti submatice na jeden procesor, tedy <math>\normalsize \mu = \frac{N}{p}</math>.

Protoze mame WH smerovani, vime, ze WH blokuje cely kanal od uzlu U az do uzlu V ve vzdalenosti tech <math>\normalsize \frac{\sqrt p}{2}</math>. Namalujte si kruznici o 7dmi uzlech, kde kazdy posila zpravu protejsimu uzlu, vyznacte si cary te komunikace a vidite, ze se vam ty cary prekryvaji ⇒ v jednu chvili tak muzou komunikovat max jen 2 uzly (jedna komunikace jednou stranou kruznice, druha druhou). Ale tech uzlu co chteji komunikovat je <math>\normalsize \sqrt p</math>, takze se cela komunikace bude opakovat <math>\normalsize \frac{\sqrt p}{2}</math>krat. Kdybychom meli vseportovy model, budou se akorat soucasne provadet prvni 2 faze, stejne tak 2. a 3. cast 3. faze, protoze se jedna o ruzne matice, tak je muzem rotovat zaroven. Vse je vysvetleno na 13. proseminari viz /https://fit.avc-cvut.cz/

<math>T_1(N,p) = T_2(N,p) = \frac{\sqrt p}{2} \left(t_s + \frac{\sqrt p}{2} t_d + \frac{N}{p} t_m \right)</math>

Ve třetí fázi probíhá lokální sekvenční násobení submatic, která má dle zadání pro matice <math>\normalsize k \times k</math> složitost <math>\normalsize \alpha k^3</math>. Naše submatice mají velikost <math>\normalsize \frac{N}{p} = \frac{\sqrt N \cdot \sqrt N}{\sqrt p \cdot sqrt p}</math>, takže složitost <math>\normalsize \alpha \left( \frac{\sqrt N}{\sqrt p} \right)^3</math>. Poté se provede horizontální a vertikální cyklický posun o 1 pozici. A to celé se <math>\normalsize \sqrt p</math>krát opakuje.

<math>T_3(N,p) = \sqrt p \cdot \left[ \alpha \left( \frac{\sqrt N}{\sqrt p} \right)^3 + 2\left( t_s + 1\cdot t_d + \frac{N}{p} t_m \right) \right]</math>

Celkový čas je potom:

<math>T(N,p) = 2 \frac{\sqrt p}{2} \left(t_s + \frac{\sqrt p}{2} t_d + \frac{N}{p} t_m \right) + \sqrt p \cdot \left[ \alpha \left( \frac{\sqrt N}{\sqrt p} \right)^3 + 2\left( t_s + t_d + \frac{N}{p} t_m \right) \right] </math>

Vypustíme jednotkové konstanty <math>{t_s}, {t_d}</math> a po úpravách dostáváme:

<math>T(N,p) = \frac{1}{2} p \cdot t_d + \alpha \frac{ N\sqrt{N} }{ p } + 3 \frac{ N \sqrt{p} }{ p } t_m = \frac{1}{2} p \cdot t_d + \alpha \frac{ N\sqrt{N} }{ p } + 3 \frac{ N }{ \sqrt{p} } t_m</math>

Dle poznámek z 9. prosemináře se celý člen s <math>{t_m}</math> může vypustit. Člen <math>{t_m}</math> je asymptoticky menší než ostatní. Potom dostáváme:

<math>T(N,p) = O\left( p \cdot t_d + \alpha \frac{ N\sqrt{N} }{ p } \right)</math>

Vloženo by plech.d: (Pozn: Já používám všude místo samotného <math>t_m</math> součin <math>m t_m</math>. Vycházím ze zadání, kde je m definováno jako velikost jednoho prvku matice.)

Není možné jen tak zanedbat člen <math>3 \frac{ N }{ \sqrt{p} } m t_m</math>, protože pro malé p je tento člen naopak velký oproti <math>\frac{1}{2} p t_d</math>. Musíme nalézt hranici <math>p_0</math>, pro kterou jsou oba výrazy navzájem rovny. Pak budeme řešit problém zvlášť pro <math>p = o(p_0)</math> a pro <math>p = \Omega(p_0)</math>. Tento postup jsme si ukazovali na posledním prosemináři 2014.

Výpočet <math>p_0</math>:

<math>\frac{1}{2} p_0 t_d = 3 \frac{N}{sqrt{p_0}} m t_m</math>

<math>p_0^{\frac{3}{2}} = \frac{6 m t_m}{t_d} N</math>

<math>p_0 = \Theta(N^{\frac{2}{3}})</math>

První část řešení je pro <math>p = o(p_0) = o(N^{\frac{2}{3}})</math> a zanedbává člen <math>\frac{1}{2} p t_d</math>:

<math>T(N,p) = \alpha \frac{\sqrt{N}^3}{p} + 3 \frac{N}{\sqrt{p}} m t_m</math>

<math>C(N,p) = \alpha \sqrt{N}^3 + 3 \sqrt{p} N m t_m</math>

Nyní si ze vzorečku pro efektivnost vyjádříme p, abychom našli <math>\psi_2(N) = N</math>. To je ale ve sporu s předpokladem, že <math>p = o(N^{\frac{2}{3}})</math>. Tuto větev řešení můžeme zahodit.

Následuje řešení pro <math>p = \Omega(p_0) = \Omega(N^{\frac{2}{3}})</math>, které zanedbává člen <math>3 \frac{N}{sqrt{p}} m t_m</math>. Toto řešení pokračuje níže v sekci Škálovatelnost od původního autora.

<math>E(N,p) = \frac{ \alpha (\sqrt N)^3 }{ p \cdot \left( p \cdot t_d + \alpha \frac{ N\sqrt{N} }{ p } \right) } = \frac{ \alpha N\sqrt N }{ p^2 \cdot t_d + \alpha N\sqrt{N} }</math>

<math>E(N,p) = E_{\tiny O}</math>

<math>\alpha (1-E_{\tiny 0}) \cdot N\sqrt N = E_{\tiny 0} \cdot p^2 \cdot t_d</math>

<math>N^{\frac{3}{2}}= \frac{ E_0 \cdot p^2 \cdot t_d }{ \alpha (1-E_0) }</math>

<math>N =\left( \frac{E_0 \cdot t_d }{\alpha (1-E_0)}\right)^{\frac{2}{3}} \cdot p^{\frac{4}{3}} = O(p^{\frac{4}{3}}) = \psi_1</math>

<math>p = \sqrt{ \frac{ \alpha (1-E_0) \cdot N\sqrt N }{ E_0 \cdot t_d} } = O( N^{\frac{3}{4}}) = \psi_2</math>

Výpočet <math>\psi_3</math>:

<math>\frac{\partial T(N,p)}{\partial p}=\frac{\partial}{\partial p} \left( p \cdot t_d + \alpha \cdot \frac{N^{\frac{3}{2}}}{p} \right) = t_d - \alpha \cdot N^{\frac{3}{2}} \cdot p^{-2}</math>

<math>p_t = \sqrt{\frac{\alpha}{t_d}} \cdot N^{\frac{3}{4}}</math>

<math>T(N,p_t) = \sqrt{\alpha \cdot t_d} \cdot N^{\frac{3}{4}} + \sqrt{\alpha \cdot t_d} \cdot N^{\frac{3}{4}} = 2 \cdot \sqrt{\alpha \cdot t_d} \cdot N^{\frac{3}{4}} </math>

<math>\psi_3 = O(N^{\frac{3}{4}})</math>

Neni to tak, ze dosazenim p_t do puvodni rovnice pro cas teprve dostaneme Tmin a to pak musime polozit rovno za T(N,p), vyjadrit p a az to nam da Psi3 ?

EDIT: z prosemináře 2013/2014 při výpočtu psi_1 se dostaneme do tvaru <math>\psi_1 = (1-E0)\alpha N\sqrt{N} = 3E0N\sqrt{p} + 2E0p\sqrt{p}</math> Člen <math> 3E0N\sqrt{p} </math> se nedá rozdělit, proto si musíme uvědomit jak musí být N velký vůči p aby platila rovnost. Jediná možnost aby to platilo je, že <math>P=\theta(N)</math>. Důkaz je sporem. a je v tom duchu, že jestli platí p=O(N) tak musí platit i malý o(N), čili aby platilo p<n musím dosait <math>p=N/k</math> kde <math>k>=1</math> čili počítam <math> \psi_1(p) = \theta(N)</math> a <math>\psi_2(n) = \theta(p)</math>

susantom koment: Bacha, na tom prosemináři 2013 se to dělalo s SF, tady je WH, proto ta rovnice vypadá jinak. Takže ta tvoje logika je sice správná, ale zde nepoužitelná, protože pracuješ se špatnou rovnicí.

Popište a vysvětlete Cannonův algoritmus paralelního násobení čtvercových <math>\sqrt N \times \sqrt N</math> matic <math>C = AB</math> na 1-portové 2-D mřížce <math>M (\sqrt p, \sqrt p)</math> procesorů, kde <math>p < N</math>. Odvoďte co nejpřesněji výraz pro paralelní čas <math>T (N,p)</math>, jestliže (1) směrovače provádějí červí (WH) přepínání paketů, kde přenos paketu o velikosti <math> \mu </math> mezi 2 uzly ve vzdálenosti d trvá <math>t(d, \mu) = t_s + dt_d + \mu t_m</math>, (2) prvky matic mají velikost <math> m </math> a (3) sekvenční lokální násobení dvou matic o velikosti <math>r \times r</math> trvá čas <math>\alpha r^3</math>, kde <math> m </math> a <math>\alpha</math> jsou konstanty. Pro zadanou efektivnost <math>E_0</math> odvoďte izoefektivní funkce <math>\psi_1 (p)</math> a <math>\psi_2(N)</math>. Dále odvoďte spodní mez <math>\psi_3(N)</math> na počet procesorů pro dosažení asymptotické časové optimality.

★ Bylo ve zkoušce: 2013-01-02 a 2015-01-06

Algoritmus a škálovatelnost spočítáme stejně jako v případě výše. Škálovatelnost vyjde ve finále stejně.

Ověřeno p. Tvrdíkem.

<math>T_1(N,p) = T_2(N,p) = \frac{\sqrt{p}}{2} \left(t_s + \frac{\sqrt{p}}{2}t_d + \frac{N}{p} t_m \right)</math>

V prvních dvou fázích je nejhorší situace ve středním řádku, kde lze posílat z každé poloviny mřížky na druhou stranu pouze jeden paket, aby nedošlo ke kolizím. V této situaci posílám přesně na vzdálenost poloviny řádku (<math>\frac{\sqrt{p}}{2}</math>) a je nutné to zopakovat pro všechny dvojice, tedy <math>\frac{\sqrt{p}}{2}</math> krát.

<math>T_3(N,p) = \sqrt p \cdot \left[ \alpha \left( \frac{\sqrt N}{\sqrt p} \right)^3 + 2\left( t_s + \sqrt{p}t_d + \frac{N}{p} t_m \right) \right]</math>

Ve 3. fázi už pak posouvám všude stejně a nejhorší případ je přesunutí nejlevějš submatice na nejpravější procesor v řádku a to lze dělat zároveň během toho, co ostatní v řádku posouvají pouze sousedům o 1 doleva.

Pokud by se jednalo o SF:

<math>T_1(N,p) = T_2(N,p) = 2\left(t_s + \sqrt{p}\frac{N}{p} t_m \right)</math>

Pro SF je nejhorší případ přesunutí nejlevější submatice v řádku na nejpravějí procesor. V prostředním řádku oproti tomu všechny procesory posouvají submatice pouze o polovinu délku řádku.

<math>T_3(N,p) = \sqrt p \cdot \left[ \alpha \left( \frac{\sqrt N}{\sqrt p} \right)^3 + 2\left( t_s + \sqrt{p}\frac{N}{p} t_m \right) \right]</math>

EDIT: ten WH je dobře, ale T1 tady u SF se mi moc nezdá

EDIT2: Na 13. prosemináři 2013 Tvrdík vysvětluje ten T1 pro SF toroid (pak je triviální to převést na M ), je to takhle. správně.

Popište paralelní algoritmus pro LU dekompozici husté <math> \sqrt{N} \times \sqrt{N}</math> matice A mapované blokově šachovnicově na p-procesorovou 2-D mřížku <math> M( \sqrt{p} , \sqrt{p} ) </math> s červím přepínáním (WH), kde přenos r prvků matice na vzdálenost d trvá čas <math> t(d,r) = t_s + d t_d + r t_m </math>. Odvoďte výraz pro paralelní čas T(N,p) a izoefektivní funkce <math> \Psi_1 (p) </math> a <math> \Psi_2 (N) </math>. Předpokládejte, že lokální aritmetické/logické/paměťové operace procesoru mají jednotkovou složitost. Dále předpokládejte, že složitost sekvenční LU dekompozice <math> k \times k </math> matice je <math> \alpha k^3 </math>, sekvenční inverze <math> k \times k </math> matice je <math> \beta k^3 </math> a sekvenčního násobení 2 <math> k \times k </math> matice je <math> \gamma k^3 </math>, kde <math> \alpha, \beta, \gamma </math> jsou konstanty.

(při nejmenším pro mřížku)

Viz skripta EN [2010] str. 190, varianta příkladu (liší se v portech) je též vysvětlen na videu z 13. prosemináře 2013 od 45:40.

Algoritmus : Na jednom procesoru by mělo být <math>\frac{N}{p}</math> čísel

• První fáze

Jeden procesor musí spočítat inverzi
<math>T_1 = \beta \left(\frac{\sqrt{N}}{\sqrt{p}}\right)^3 </math>

• Druhá fáze

OAB na sloupci

<math> T_2 = \log ({\sqrt{p} - i + 1}) (t_s + \frac{N}{p} t_m) + (\sqrt{p} - i) t_d </math>

• Třetí fáze

násobení + OAB na řádku

<math> T_3 = \gamma \left(\frac{\sqrt{N}}{\sqrt{p}}\right)^3 + T_2</math>

• Čtvrtá fáze

Každý procesor opět násobí.

<math> T_4 = \gamma \left(\frac{\sqrt{N}}{\sqrt{p}}\right)^3 </math>

• Celkem

No a jedeme po diagonále, která je dlouhá <math>\sqrt{p}</math>

<math> T = \sum_{i=1}^{\sqrt{p}} (T_1 + T_2 + T_3 + T_4) </math>

U T_2 se nám to jediné mění v závislosti na parametru “i”. A to následovně :

<math> T_{2_1} = \log ({\sqrt{p}}) (t_s + \frac{N}{p} t_m) + (\sqrt{p} - 1) t_d </math>
<math> T_{2_2} = \log ({\sqrt{p} - 1}) (t_s + \frac{N}{p} t_m) + (\sqrt{p} - 2) t_d </math>
<math> T_{2_3} = \log ({\sqrt{p} - 2}) (t_s + \frac{N}{p} t_m) + (\sqrt{p} - 3) t_d </math>
<math> T_{2_4} = \log ({\sqrt{p} - 3}) (t_s + \frac{N}{p} t_m) + (\sqrt{p} - 4) t_d </math>
<math> T_{2_{\sqrt{p}}} = \log ({2}) (t_s + \frac{N}{p} t_m) + (1) t_d </math>

První část

<math>\log 2 + \log 3 + \cdot \cdot \cdot + \log {\sqrt{p}} = \log (2 . 3 . 4 . . . \sqrt{p}) = \log (\sqrt{p} !) \dot= \log ({\sqrt{p}}^{\sqrt{p}}) = \sqrt{p} \log {\sqrt{p}} = \frac {1}{2} \sqrt{p} \log {p} </math>

Druhá část

<math>1 + 2 + 3 + \cdot \cdot \cdot + \sqrt{p} - 1 = \frac{n (a_1 + a_n)}{2} = \frac{(\sqrt{p} - 1) (1 + (\sqrt{p} - 1)} {2} \dot= \frac{\sqrt{p} \sqrt{p}}{2} = \frac{p}{2}</math>

<math> T(N,p) = \underbrace{ \sqrt{p} \beta \left(\frac{\sqrt{N}}{\sqrt{p}}\right)^3}_{ \text{T_1 = Inverze}} + \underbrace{ \frac {1}{2} \sqrt{p} \log {p} (t_s + \frac{N}{p} t_m) + \frac{p}{2} t_d}_{ \text{T_2 = OAB na sloupci}} + \underbrace{ \underbrace{ \sqrt{p} \gamma \left(\frac{\sqrt{N}}{\sqrt{p}}\right)^3}_{ \text{Nasobeni matic}} + \underbrace{ \left(\frac {1}{2} \sqrt{p} \log {p} (t_s + \frac{N}{p} t_m) + \frac{p}{2} t_d \right)}_{ \text{OAB na radku}}}_{\text{T_3}} + \underbrace{ \sqrt{p} \gamma \left(\frac{\sqrt{N}}{\sqrt{p}}\right)^3}_{ \text{T_4 = Nasobeni matic}} </math>

<math> SU = \alpha (\sqrt{N})^3 </math>

A jde se upravovat :

<math> T = \sqrt{p} \beta \left(\frac{\sqrt{N}}{\sqrt{p}}\right)^3 + \frac {1}{2} \sqrt{p} \log {p} (t_s + \frac{N}{p} t_m) + \frac{p}{2} t_d + \sqrt{p} \gamma \left(\frac{\sqrt{N}}{\sqrt{p}}\right)^3 + \left(\frac {1}{2} \sqrt{p} \log {p} (t_s + \frac{N}{p} t_m) + \frac{p}{2} t_d \right) + \sqrt{p} \gamma \left(\frac{\sqrt{N}}{\sqrt{p}}\right)^3 =\\=

\beta \frac{N \sqrt{N}}{p} + 2 \left(\frac {1}{2} \sqrt{p} \log {p} (t_s + \frac{N}{p} t_m) + \frac{p}{2} t_d \right) + 2 \gamma \frac{N \sqrt{N}}{p} =\\=

\beta \frac{N \sqrt{N}}{p} + \sqrt{p} \log {p} (t_s + \frac{N}{p} t_m) + p t_d + 2 \gamma \frac{N \sqrt{N}}{p} =\\=

\beta \frac{N \sqrt{N}}{p} + \underbrace{ \sqrt{p} \log {p} t_s}_{ \sqrt{p} \log {p} = O(p)} + \sqrt{p} \log {p} \frac{N}{p} t_m + p t_d + 2 \gamma \frac{N \sqrt{N}}{p} \dot=
\dot=

\beta \frac{N \sqrt{N}}{p} + \log {p} \frac{N}{\sqrt{p}} t_m + p t_d + 2 \gamma \frac{N \sqrt{N}}{p} </math>

<math> C(N,p) = \beta N \sqrt{N} + \log {p} \sqrt{p} N t_m + p^2 t_d + 2 \gamma N \sqrt{N} </math>

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

\frac{\alpha N \sqrt{N}}{\beta N \sqrt{N} + \log {p} \sqrt{p} N t_m + p^2 t_d + 2 \gamma N \sqrt{N}}= E_0

\alpha N \sqrt{N} = E_0 \beta N \sqrt{N} + E_0 \log {p} \sqrt{p} N t_m + E_0 p^2 t_d + 2 E_0 \gamma N \sqrt{N}

\alpha N \sqrt{N} - E_0 \beta N \sqrt{N} - 2 E_0 \gamma N \sqrt{N} = E_0 \log {p} \sqrt{p} N t_m + E_0 p^2 t_d

N \sqrt{N}(\alpha - E_0 \beta - 2 E_0 \gamma) = E_0 \log {p} \sqrt{p} N t_m + E_0 p^2 t_d

</math>

Rozdělíme na dva podúkoly a zmergujeme :

a)

<math> N \sqrt{N}(\alpha - E_0 \beta - 2 E_0 \gamma) = E_0 \log {p} \sqrt{p} N t_m

N \sqrt{N} = \frac{E_0 t_m}{\alpha - E_0 \beta - 2 E_0 \gamma} \log {p} \sqrt{p} N

\sqrt{N} = \frac{E_0 t_m}{\alpha - E_0 \beta - 2 E_0 \gamma} \log {p} \sqrt{p}

N = \left(\frac{E_0 t_m}{\alpha - E_0 \beta - 2 E_0 \gamma}\right)^2 p \log^2 {p} \dot= p \log^2{p} = \psi_{1_a}(p)

</math>

b)

<math> N \sqrt{N}(\alpha - E_0 \beta - 2 E_0 \gamma) = E_0 p^2 t_d

N \sqrt{N} = \frac{E_0 t_d}{\alpha - E_0 \beta - 2 E_0 \gamma} p^2

N^{\frac{3}{2}} = \frac{E_0 t_d}{\alpha - E_0 \beta - 2 E_0 \gamma} p^2

N^ = \left(\frac{E_0 t_d}{\alpha - E_0 \beta - 2 E_0 \gamma}\right)^{\frac{2}{3}} p^{\frac{4}{3}} \dot = p \sqrt[3] {p} = \psi_{1_b}(p)

</math>

No a teď to dáme dohromady :

<math>

N = \Omega(\psi_{1_a}(p)) = \Omega(p \log^2{p})
N = \Omega(\psi_{1_b}(p)) = \Omega(p \sqrt[3] {p}) </math>

No a z toho plyne že :

<math>

N = p \sqrt[3] {p} = \psi_1(p)
N = p^{\frac{4}{3}}
p = N^{\frac{3}{4}} = \psi_2(N)

</math>

Popište algoritmus sudoliché redukce pro řešení tridiagonální soustavy n lineárních rovnic mapovaných blokově na p-procesorovou hyperkrychli, <math>p<n</math>, SF, přenos paketu o velikosti <math> u </math> na vzdálenost <math> d </math> trvá <math>t(d,u)= t_s + d \cdot u \cdot t_m</math>. Odvoďte asymptoticky hodnotu <math>T(n,p)</math>. Aritmetické, logické, paměťové operace mají konstantní složitost.

★ Bylo ve zkoušce: NE2012-01-24 (místo Q_n na 1D mřížce a WH) a 2013-01-23, 2015-01-28 8b

Viz skripta CZ [2006] str. 201

Soustava má podobu:

<math> \begin{array}{lcr} (f_1 x_0 +) g_1 x_1 + h_1 x_2 & = & b_1
f_2 x_1 + g_2 x_2 + h_2 x_3 & = & b_2
&\cdots &
f_i x_{i-1} + g_i x_i + h_i x_{i+1} & = & b_i
&\cdots &
\end{array} </math>

Pokud jsou všechny koeficienty <math>\normalsize g_i</math> nenulové, pak lze všechny sudé řádky vyjádřit jako sousední liché <math>x_{i-1}</math> a <math>x_{i+1}</math> a dosadit do rovnice pro <math>x_i</math>. Tím nám vznikne rovnice obsahující <math>x_i</math>, <math>x_{i-2}</math> a <math>x_{i+2}</math>, tedy opět sudé <math>x_i</math>. Každou sudo-lichou redukcí se počet rovnic sníží na polovinu. Sekvenční čas pro řešení soustavy <math>n</math> rovnic se skládá z postupné eliminace rovnic; <math>O(n) = SU(n)</math>

Komunikační závislosti při paralelním algoritmu jsou naznačeny na obrázku:

Při <math>n>p</math> připadá na 1 procesor <math>n\over p</math> řádků. V každém kroku počet rovnic obsluhovaných procesorem klesá na polovinu.

V 1. kroku komunikují uzly ve vzdálenosti 1.

V 2. kroku uzly ve vzdálenosti 2, ve třetím ve vzdálenosti <math>2^2</math>, … , v n-tém <math>2^{k-1}</math>. Pokud je <math>p<n</math>, pak prvních <math>\log {n \over p}</math> kroků se rovnice zpracovávají lokálně, poté zůstane 1 rovnice na procesor a poté následuje běžná komunikace ⇒ její složitost závisí na vhodném mapování. Očíslujeme-li si procesory čísly 1,2, … , p, namapujeme je v hyperkrychli na uzly ohodnocené binárně pomocí Grayova kódu BRGC ⇒ ten má dobrou vlastnost, že 2 čísla <math>G(j \cdot 2^k)</math> a <math>G¹⁾ </math>

<math> O (\frac{n}{p} + \frac {n}{p} log p tm + \(sqrt p - 1)td) + O( \sqrt p td + \frac{n}{p} tm + 2\frac{n}{p} ) + O ( \sqrt p td + 2\frac {n}{p} log p tm + (\frac {n^2}{p})) =

O ( 3\frac {n}{p} log p tm + (3\sqrt p - 1) td + (\frac {n^2}{p})) = </math>

<math> O ( \frac {n}{p} log p tm + \sqrt p td + (\frac {n^2}{p})) </math>

Zatím se jedná jen o hrubý nástřel. Určitě tam budou chyby. Prosím o kontrolu a pripadne upravy

Je ve výpočtu zahrnuto to, že je matice namapována blokově šachovnicově - tedy, že jeden procesoru může držet více matic ?

podle mě řešení výše neni úplně správně, ale aby případný čtenář mohl porovnat obě řešení, vytvořím tento fork.

Pár věcí na úvod:

Jelikož matice je o rozměrech <math>\sqrt N * \sqrt N</math> a procesorů je <math>\sqrt p * \sqrt p</math>, tak každý procesor drží submatice o rozměrech <math>\frac{\sqrt N}{\sqrt p} * \frac{\sqrt N}{\sqrt p}</math> a první sloupec procesorů navíc drží <math>3 * \frac{\sqrt N}{\sqrt p}</math> (r, b a x - to vychází ze zadání).

Pseudokód:

vector x(t) = initial_value;
vector r(t) = vector b - matice A * vector x(t)
while (||vector r|| > epsilon) do_sequently {
   t := t + 1;
   ∀ i:= 0 .. n - 1 do parallel
      xi = ri(t-1)/ai,i + xi(t-1);
   vector r(t) = vector b - matice A * vector x(t)
}

Jak vidíte, kód je stejný - až na inicializaci.

V prvním kroce je tedy potřeba přesunout všechny tyto vektory na diagonálu. Nejdál to bude samozřejmě na vzdálenost <math>{\sqrt p} - 1</math>, čiže

<math> O ( ts + 3*\frac {\sqrt n}{\sqrt p}*tm + ({\sqrt p} - 1) * td) </math>

V dalším kroce se násobí matice vektorem - viz vektor krát matice (bez přesunutí vektoru x na diagonálu, my už ji tam máme! A NAVÍC se výsledek (vector r(t)) neposílá na první sloupec, ale na diagonálu).

Další řádek je while cyklus, vyhodnocuje se ||vector r||. To je obyčejný skalární součin, který trvá <math>O(1)</math> když p = n (každý procesor pouze jeho část umocní), když p < n, tak to trvá <math>\frac{\sqrt n}{\sqrt p}</math>. Teď má tedy každý procesor na diagonále svůj kousek velikosti ||r||, je tedy potřeba vše sečíst a OAB všem. To už neni úplně jednoduchý:

1) Všechno sečíst na diagonále by měl být běžný postup, akorát vzdálenosti budou dvojnásobné, ale jinak by to neměl být problém. Čiže <math> O (\frac{\sqrt n}{\sqrt p} + log \sqrt p * (ts + \frac {\sqrt n}{\sqrt p}*tm) + 2*({\sqrt p} - 1) * td)</math> (lokální + paralelní redukce)

2) OAB na mřížce - musí se poslat všem procesorům, aby všichni věděli, jestli mají skončit

A teď si všimněte, že uvnitř for cyklu se pouze dělí / sčítají prvky, které jsou všechny na diagonále! Takže <math>O(1)</math>

Poslední řádek ve while cyklu je stejný jako při inicializaci. Nakonec je potřeba všechny části vectoru x přesunout z diagonály na první procesor - musí být namapovány stejně jako při začátku algoritmu

Dotaz: Zadání vyžaduje popis a čas jedné iterace algoritmu. Je tedy opravdu třeba počítat podmíku pokračování další iterace, nebo dokonce inicializaci celého algoritmu? Nestačí počítat vnitřek toho while cyklu (jednu iteraci) tj. lokální operaci + MVM? Jenže to bychom pak museli dělat uvnitř této smyčky přesun vektoru na diagonálu a zpět a to by nebylo efektivní. Dle zadání máme počítat s tím, že vektory jsou mapovány na pravý sloupec procesorů – na začátku iterace? Na začátku algoritmu? Zdá se mi, že to zadání není dostatečně přesně formulováno. Co myslíte?

Nebo je myšleno od začátku algoritmu do konce první iterace, jako je to tady popsáno?

Foxův algoritmus pro násobení matic <math>\sqrt N * \sqrt N</math> na všeportovém toroidu <math>K(\sqrt p, \sqrt p)</math>, který používá SF přepínání. Byla zadána složitost lokálního násobení a kolik trvá přenos zprávy na délku d (klasický vzoreček pro SF).

★ Bylo ve zkoušce:2012-01-03 a 2012-01-17 a 2013-01-30, 2013-12-20, 2014-01-13 - s WH přepínáním

Viz skripta CZ [2006] str. 200, EN [2009], pg. 185

<math>\forall j=1, … , \sqrt p</math> do_sequentially {

<math>\forall i=1,…, \sqrt p</math> do_in_parallel

P_{i,(i+j) mod sqrt p} rezešle matici A_{i,(i+j) mod sqrt p} v rámci řádku <math>i</math> (OAB);

<math>\forall i, k=1, …, \sqrt p</math> do_in_parallel

P_i,k přičte C_i,k součin přijatých matic A_i,k a B_i,k

<math>\forall k = 1, …, \sqrt p</math> do_in_parallel

Všechny submatice B_*,k v sloupci orotují o <math>1</math> pozic nahoru

}

Jestli čtu skripta správně, Foxův algoritmus předpokládá mapování blokově šachovnicově.

Složitost rozesílání OAB na všeportovém 1-D SF Toroidu <math>(t_s +\frac {N}{p}t_m)\frac{sqrt p }{2} </math>

Strana submatice která má <math>\frac{N}{p}</math> prvků bude <math>\frac{sqrt N}{sqrt p}</math> a lokální násobení by mělo být tudíž <math>(\frac{sqrt N}{sqrt p})^3 </math>

Složitost rotování matic o jednu pozici nahoru <math>t_s +\frac {N}{p}t_m </math>

Celková složitost je:

<math>O(\sqrt p(\frac{sqrt p }{2} t_s +\frac {\sqrt p}{2}\frac {N}{p} t_m + (\frac{sqrt N}{sqrt p})^3 + t_s +\frac {N}{p}t_m) )=</math>

<math>O(\frac {p}{2}t_s +\frac {N}{\sqrt p}(\frac {\sqrt p}{2} + 1 )t_m + \frac{(sqrt N)^3}{p})</math>

<math>O(\frac {p}{2}t_s +\frac {N}{2}t_m + \frac{(sqrt N)^3}{p})</math>

VasekJ: imho by za <math>t_m</math> mělo následovat i ve SF i ve WH <math>t_m * m</math> (velikost jednoho prvku matice má velikost m)

<math>T(N, p) = p + N + \frac{(sqrt N)^3}{p}</math>

<math>C(N, p) = p^2 + Np + (sqrt N)^3</math>

<math>E(N, p) = \frac{(sqrt N)^3}{p^2 + Np + (sqrt N)^3}</math>

V tomto kroku můžete zanedbat <math>p^2</math> protože v nejhorším případě bude mít stejnou složitost jako Np. No a pak dál už je to snadný, psí1 a psí2. (dnes uznáno u zkoušky)

tedy psí_1(p)= p^2, psí_2(N)= sqrt(N)

★ Bylo ve zkoušce: 2016-01-15, 2015-01-13, 2012-01-10

Popsat alg. násobení matice A(√N,√N) mapované blokově po řádcích vektorem x(√N,1) mapovaným blokově na mřížku M(p), 1⇐p⇐√N. Výsledný vektor y = Ax má být po skončení výpočtu mapován také blokově. Předpokládejte, že M(p) je všeportová s přepínáním ulož-pošli-dál (SF), kde přenos <math> \mu </math> čísel mezi procesory ve vzdálenosti <math> \delta </math> trvá čas t(<math> \delta </math>,<math> \mu </math>) = <math> t_s </math> + <math> \delta \mu </math> <math> t_m </math>. Dále předpokládejte, že skalární součin dvou vektorů o rozměru (k x 1) sekvenčně na 1 procesoru trvá čas <math> \beta </math>k, kde <math> \beta </math> je konstanta. Odvoďte co nejpřesněji jeho paralelní čas T(n,p) a izoefektivní funkce ψ1(p), ψ2(N).

Každý cpu má <math>\frac{\sqrt N}{p} </math> řádků.

algoritmus má 2 části

• A - rozeslat svou část vektoru x všem ostatním procesorům,
• B - lokálně vynásobit a sečíst části.

<math>T_{A}</math>:

AAB na 1D všeportové mřížce. Všechny uzly pošlou svá data všem ostatním a nějaká dostanou. Ty si uloží a pošlou dál. Důležité je to, že si data uloží. Čili v dalším kroku zase nabíhá <math>t_{s}</math>. Počet těchto kroků se zjistí průměrem sítě - (p-1). Což je asymptoticky stejně jako p (to mi v písemce uznal). Každý krok se posílá na vzdálenost 1. Množství dat, které posíláme je <math>\frac{\sqrt N}{p} </math>. Kdyby byl 1-portová, tak v každém kroku odesíláme <math>O(\frac{\sqrt N}{p} )</math> dat a můžeme to počítat úplně stejně.

<math>T_{A} = (t_{s} + 1\frac{\sqrt N}{p}t_{m})p = p t_{s}+\sqrt N t_{m}</math>

<math>T_{B}</math>:

Nyní má kadý CPU komplet vektor x. Tímto vektorem musí vynásobit svých <math>\frac{\sqrt N}{p} </math> řádků. Takže násobíme <math>\frac{\sqrt N}{p} </math> krát dva vektory velikosti <math>\sqrt N </math> x 1. Jedna tato operace trvá <math>\beta \sqrt N </math>

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

celkově:

<math>T= T_{A}+T_{B}=pt_{s}+\sqrt N t_{m} + \beta \frac{ N}{p}</math>

<math>C(N,p)= p^2 t_{s}+\sqrt N p t_{m} + \beta N</math>

<math>E(N,p)= \frac{ SU(N)}{C(N,p)} =\frac{ \beta N}{p^2 t_{s}+\sqrt N p t_{m} + \beta N }</math>

U opravy mi bylo řečeno, že první sčítanec jmenovatele se dá zanedbat vůči druhému (p bude maximálně <math>\sqrt N</math> čili to bude maximálně rovno). Proč se stejnou logikou nemůžu zanedbat druhý sčítanec vůči třetímu už nevim.

Edit: Protože tam musíš nechat aspoň jeden člen vyjadřující komunikační část a jeden pro lokální část. Zanedbání provádíš jen mezi více komunikačními členy. IMHO.

Edit: IMHO muzes zanedbat prvni scitanec, protoze se da vyjadrit jako multiplikativni konstanta u toho druheho.

Edit: podle mě to jde (pokud zanedbám první sčítanec)

<math> \beta N = E_{0}(p \sqrt{N}t_{m} + \beta N)
\gamma N = p \sqrt{N}
\gamma \frac{N}{\sqrt{N}}*\frac{\sqrt{N}}{\sqrt{N}} = p
\gamma \sqrt{N} = p
N = (\frac{p}{\gamma})^{2} </math>

Vyloženě nic zanedbávat se nemusí, klasicky se to rozdělí na podúlohy a pak zase spojí

<math>E(N,p)= \frac{ SU(N)}{C(N,p)} =\frac{ \beta . N}{p^2 .t_{s}+\sqrt N . p. t_{m} + \beta . N } = E_0 </math>

<math>\frac{ \beta . N}{p^2 .t_{s}+\sqrt N . p. t_{m} + \beta . N } = E_0 </math>

<math>\beta . N = E_0 \left(p^2 .t_{s}+\sqrt N . p. t_{m} + \beta . N\right) </math>

<math>\beta . N = E_0 . p^2 .t_{s} + E_0 . \sqrt N . p. t_{m} + E_0 . \beta . N </math>

<math>\beta . N - E_0 . \beta . N = E_0 . p^2 .t_{s} + E_0 . \sqrt N . p. t_{m} </math>

<math>\beta . N(1 - E_0) = E_0 . p^2 .t_{s} + E_0 . \sqrt N . p. t_{m}</math>

No a teď víme, že součet pravé strany se musí asymptoticky rovnat levé straně. Zajímá nás především asymptotické řešení, proto můžeme úlohu rozdělit na dvě části, kdy prvně budeme počítat pouze s jedním členem onoho součtu, pak s druhým členem, a pak to asymptoticky spojíme.

<math>\beta . N(1 - E_0) = E_0 . p^2 .t_{s} </math>

<math>N = \frac{E_0 . p^2 .t_{s}}{\beta . (1 - E_0)} = \frac{E_0 .t_{s}}{\beta . (1 - E_0)} . p^2 \dot= p^2 = \psi_{1_a}(p)</math>

A teď druhou část :

<math>\beta . N(1 - E_0) = E_0 . \sqrt N . p. t_{m}</math>

<math>N = \frac{E_0 . \sqrt N . p. t_{m}}{\beta . (1 - E_0)} = \frac{E_0. t_{m}}{\beta . (1 - E_0)} \sqrt N . p </math>

<math>\sqrt{N}= \frac{E_0. t_{m}}{\beta . (1 - E_0)} p </math>

<math>N= {\left(\frac{E_0. t_{m}}{\beta . (1 - E_0)}\right)}^2 p^2 \dot= p^2 = \psi_{1_b}(p) </math>

Tady to vyšlo obojí stejně, takže není moc co řešit, ale obecně to řešíme tak, že <math>\psi_1(p)</math> je asymptoticky minimální funkce a proto řešíme asymptoticky soustavu dvou rovnic kde :

<math>\psi{1_a} = N = \Omega(p^2)</math>
<math>\psi{1_b} = N = \Omega(p^2)</math>

Což zde je triviální a tedy <math> N = p^2 = \psi_1(p) </math>

No a <math> \psi_2(n) </math> je inverzní, čili :

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

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