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

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>