Differences

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

--- users:martin.kocicka:pdp:10b [2017/06/09 19:34] – martin.kocicka
+++ users:martin.kocicka:pdp:10b [2017/06/13 11:18] (current) – martin.kocicka
@@ Line 1: / Line 1: @@
 ====== PDP - Vyřešené zkouškové příklady za 10 bodů ======
-====== Kolektivní komunikační algoritmy (10. + 11. přednáška)======
+====== Kolektivní komunikační algoritmy ======
 ===== OAS 2-D toroid, WH, kombinující =====
@@ Line 79: / Line 79: @@
 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í).
-====== Lineární algebra (12. přednáška)======
+====== Lineární algebra ======
 ===== Cannonův algoritmus na všeportové hyperkrychli =====
@@ Line 268: / Line 267: @@
 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í.
 ===== Cannonův algoritmus na 1-portové mřížce =====
@@ Line 304: / Line 301: @@
 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 :-D), je to takhle. správně.
-===== LU Dekompozice =====
-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.
-==== Řešení ====
-(při nejmenším pro mřížku)
-:!://Viz skripta EN [2010] str. 190, varianta příkladu (liší se v portech) je též vysvětlen [[https://www.youtube.com/watch?v=RObDQ3Zn_bA|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>
-=== Výpočet ===
-<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} +
-\left(\frac {1}{2} \sqrt{p} \log {p} (t_s + \frac{N}{p} t_m) + \frac{p}{2} t_d \right)  +
-\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 +
-\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 +
-\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 +
-\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 +
-\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 +
-\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 +
-E_0 \gamma N \sqrt{N} \\
-\alpha N \sqrt{N} -
-E_0 \beta N \sqrt{N} -
-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>
-===== Řešení tridiagonální soustavy lineárních rovnic =====
-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: NE[[par_zkouska_2012-01-24|2012-01-24]] (místo Q<sub>n</sub> na 1D mřížce a WH) a [[par_zkouska_2013-01-23|2013-01-23]], [[par_zkouska_2015-01-28|2015-01-28]] 8b//
-==== Řešení ====
-:!://Viz skripta CZ [2006] str. 201//
-=== Algoritmus ===
-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:
-{{:škola:předměty:mi-par:vyřešené_příklady:slr_m1d.png?600|}}
-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((j+1) \cdot 2^k )</math> se liší maximálně ve 2 bitech => jakákoli komunikace potřebná v algoritmu probíhá **maximálně po 2 hranách**.
-=== Složitost ===
-Složitost se skládá z lokálního (sekvenčního) výpočtu <math>\frac{n}{p}</math> rovnic v <math>log(\frac{n}{p})</math> krocích a paralelní části.
-<math>T(n,p) = T_1(n,p) + T_2(n,p)</math>
-== Sekvenční část ==
-<math>
-T_1(n,p)
-= \left( {n \over p} \cdot {1 \over 2^0} + {n \over p} \cdot {1 \over 2^1} + ... + {n \over p} \cdot {1 \over { 2^{k-1} } } \right)
-= \frac{n}{p} \cdot \sum_{\small n=0}^{\small k-1} \frac{1}{2^n}
-</math>
-Jak je vidno, jedná se o součet geometrické posloupnosti. Součet prvních //n// členů posloupnosti se vypočítá jako <math>s_n = a_{\tiny 1} \frac{ 1-q^n }{1-q}</math>. V našem případě je <math>a_{\tiny 1} = \frac{n}{p},\: q = \frac{1}{2},\: n = k</math>. :!: Pozor nekdo to tu opravil na <math> n = k-1 </math> coz ale neni pravda protoze cela suma jede od 0 a ne od 1!
-Po dosazení do vzorce dostáváme:
-<math>T_1(n,p)
-= \frac{n}{p} \cdot \frac{ 1-\frac{1}{2^k} }{ 1-\frac{1}{2} }
-= \frac{n}{p} \cdot \frac{ \frac{2^k-1}{2^k} }{ \frac{1}{2} }
-= 2\frac{n}{p} \cdot \frac{ 2^k-1 }{ 2^k }
-</math>
-Nyní si musíme uvědomit, co tu představuje koeficient **//k//**. Jedná se o počet kroků, který bude pro každý procesor proveden sekvenčně, což je <math>k = log\frac{n}{p}</math>. Po dosazení:
-<math>T_1(n,p)
-= 2\frac{n}{p} \cdot \frac{ 2^{log\frac{n}{p}} -1 }{ 2^{log\frac{n}{p}} }
-= 2\frac{n}{p} \cdot \frac{ \frac{n}{p} -1 }{ \frac{n}{p} }
-= 2(\frac{n}{p} - 1)
-</math>
-Pozn.: Pro logaritmus platí <math>\normalsize y = log_2(x),\; x = 2^y</math>, z čehož vyplývá <math>\normalsize 2^{log_2(x)} = x</math>.
-== Paralelní část ==
-V paralelní části bude provedeno <math>\normalsize \log p</math> redukčních kroků. Díky zmíněné speciální vlastnosti Grayova kódu bude komunikace probíhat maximálně po dvou hranách. Ze zadání pak vyplývá horní mez komunikačního zpoždění <math>\normalsize t_s + 2 t_m \cdot \mu</math>.
-<math>T_2(n,p) \le \log p \cdot (t_s + 2 t_m \cdot \mu)</math>
-EDIT: **pro WH na mřížce by to mohlo být**:
-logp kroků, tzn. <math>logp \cdot t_s + (1+2+4+...) \cdot t_d + (\frac{n}{2p} + \frac{n}{4p} + ...) \mu \cdot t_m</math>
-tzn. nejdřív komunikují procesory vzdálenosti 1, poté vzd. 2 atd. To proběhne logp krát Viz obrázek. Množství dat, které si posílají je nejdřív polovina rovnic, poté polovina poloviny, atd. To proběhne log(n/p) krát = dokud nemám jen jednu rovnici.
-to jsou všechno geometrické řady, takže po úpravách dostaneme:
-<math>T_2(n,p) = logp \cdot t_s + (p-1) \cdot t_d +  (\frac{n}{p}-1)  \cdot \mu \cdot t_m </math>
-FIXME
-Edit By Rulfik: Dle mě to není pro ten případ s 1D WH Mřížkou uplně dobře, jelikož po sekvenční části se zredukuje počet rovnic na 1! Tudíž je velikost dat pro výměnu v každém paralelním kroku konstantní, mění se pouze vzdálenost, ta je dobře. Mělo by to tedy být: <math>logp \cdot t_s + (1+2+4+...) \cdot t_d + \mu \cdot t_m</math> a ve výsledku tedy <math>T_2(n,p) = logp \cdot t_s + (p-1) \cdot t_d +  logp \cdot \mu \cdot t_m </math>
-EDIT: Aha, tak jsem to špatně pochopila. Je to tedy tak, že nejdřív to procesory zredukují lokálně na 1 rovnici (já myslela, že jen na půlku), posílají jen jednu rovnici. Takže procesory na druhé úrovni mají každý tři rovnice, vyřeší a pošlou zase jednu? A toto řešení 3 rovnic se už zanedbává?
-Response: Lokálně na jednu rovnici ano (viz anglická scripta str 188). Mělo by to být tak jak říkáš, i ve skriptech píše, že komunikační zátěž je značná a ten výpočet vlastně konstantní.
-== Celková složitost ==
-<math>T(n,p) \leq 2(\frac{n}{p} - 1) + \log p \cdot (t_s + 2 t_m \cdot \mu ) = O \left ({n\over p} + \log p \right )</math>
-===== Jacobiho algoritmus =====
-Popište pseudokódem jednu iteraci Jakobiho algoritmu pro paralelní iterativní řešení soustavy n lineárních rovnic o n neznámých <math>A \vec{x} = \vec{b}</math> na p-procesorové 2-D mřížce <math>M(\sqrt{p},\sqrt{p})</math> na níž je matice <math>A</math> mapována blokově šachovnicově a všechny vektory blokově na poslední sloupec této 2-D mřížky. Identifikujte v tomto algoritmu základní výpočetní a komunikační operace. Odvoďte co nejpřesnější výraz pro paralelní čas <math>T(n,p)</math> jedné této iterace, jestliže:
-  - mřížka je 1-portová s plně-duplexními linkami a s červím (WH) přepínáním paketů, kde přenos paketu o velikosti <math>\mu</math> mezi 2 uzly ve vzdálenosti <math>d</math> trvá <math>t(d, \mu) = t_s + d t_d + \mu t_m</math>,
-  - jedna aritmetická/paměťová operace procesoru trvá jednotkový čas,
-  - sekvenční násobení matice <math>r \times r</math> vektorem <math>r \times 1</math> trvá čas <math>\alpha r^2</math>.
-★ //Bylo ve zkoušce: [[par_zkouska_2012-01-24|2012-01-24]] a [[par_zkouska_2012-01-31|2012-01-31]] a [[par_zkouska_2012-12-18|2012-12-18]]//
-==== Řešení ====
-:!://Viz skripta CZ [2006] str. 205-206 nebo EN [2009] str. 191//
-Jedna iterace jacobiho algoritmu:
-<code>
-while (||vector r|| > epsilon) do_sequentially {
-   t := t + 1;
-   ∀ i:= 0 .. n - 1 do parallel
-      xi(t) = ri(t-1)/ai,i + xi(t-1);
-   vector r(t) = vector b - matice A * vector x(t)
-}
-</code>
-Na 1. řádku se vyhodnocuje kriterium konvergence - paralelní výpočet skalárního součinu vektorů to je paralelní redukce
-a OAB výsledku tohoto součinu.
-U paralelní fáze 3. a 4. řádku zaleží na namapování matice, zde se jedná o 2D mřížku stejně jako v CZ skriptech,
-ale vektory jsou namapovány místo na diagonálu na poslední sloupec blokově (podle mne se jedná o vektory - r,b,x),
-což díky WH směrování by se měl tento vektor v jednom kroku poslat na diagonalu. Poté provest výpočet.
-. řádek je násobení matice vektorem (následné odečtní dvou vektorů lze zanedbat)
-=== 1. řádek má složitost: ===
-Par. redukce
-<math>
-T(N,p)= O(\frac {N}{p} + log \sqrt p ) = O(\frac {N}{p} + log p )
-</math>
-+
-EDIT: FIXME Po fázi redukce drží tento výsledek jeden z procesorů nemělo by se tak v následující fázi jednat o OAB na 2D mřížce? Tak aby o výsledku skalárního součinu
-věděly všechny CPU's.
-OAB na 1-portové = Binární zdvojování (záleží, ale na pozici zdroje):
-počet opakování =
-<math>
- log \sqrt p = \frac{1}{2} log p
-</math>
-JDU: Proč ne <math>log p </math>??  <math>log \sqrt p </math> na jednom rozměru + <math>log \sqrt p </math> na druhém rozměru.
-<math>
-d*td = \(sqrt p - 1)td
-</math>
-FIXME Nemělo by pro td platit spíše exc(u)td nebo v tomto případě <math>\(sqrt p - 1)td</math> (broadcastuju z posledniho sloupce) dle P10S26. Délky cest přeci na n vůbec nezávisí. Pravda - opraveno
-<math>
-\mu tm = \frac{n}{p}log p tm
-</math>
-JDU: Proč posíláme data o velikosti n/p, když norma, která se OAB posílá je jedno číslo?
-Celková složitost je:
-<math>
-O (\frac{n}{p} + log p + \frac{1}{2}log p (ts + \frac {n}{p}tm) + \(sqrt p - 1) td) =
-O (\frac{n}{p} + \frac {n}{p} log p tm + \(sqrt p - 1)td)
-</math>
-=== 3. a 4. má složitost: ===
-Poslání vektoru r na diagonálu, kde jsou namapovány a<sub>i,i</sub> konstanty.
-<math>
-   O( ts + \sqrt p td + \frac{n}{p} tm )
-</math>
-//-> Proč je //<math>\frac{n}{p} tm</math>//? Přeci se posílá jenom r a to je //<math>\frac{\sqrt{N}}{\sqrt{p}}</math> //čísel ne? // \\
-JDU: Souhlasím s <math>\frac{n}{\sqrt{p}}</math>, kde n je strana matice dle zadání
-Vydělení a sečtení výsledných hodnot
-<math>
-   O( 2\frac{n}{p})
-</math>
-JDU: opět se domnívám, že se bude dělit vektor o výšce jen <math>\frac{n}{\sqrt{p}}</math>
-Celková složitost je:
-<math>
-O( ts + \sqrt p td + \frac{n}{p} tm + 2\frac{n}{p} ) =
-O( \sqrt p td + \frac{n}{p} tm + 2\frac{n}{p} )
-</math>
-=== 5. má složitost ===
-Ze stránky 197 CZ skript. Má násobení matice a vektoru 4 fáze.
-. Rozeslání vektoru na diagonálu - ta samá složitost jako 1. část na řádku 3 a 4 =
-<math>
-   O( ts + \sqrt p td + \frac{n}{p} tm )
-</math>
-JDU: Pokud zde chceme posílat vektor X z pravého sloupce na diagonálu, museli bychom ho tam v části, kde se řeší 3. a 4. řádek také poslat.\\
-Může ten vektor X zůstat na těch diagonálách po tom výpočtu, nebo ho opravdu musíme v tom kroku odeslat do pravého sloupce a v dalším kroku ho poslat zase zpět kvůli násobení?
-. rozeslání všech hodnot ve sloupečku, to by mělo mít stejnou složitost jako
-OAB z řádku 1.
-<math>
-O (\frac {n}{p} log p tm + \(sqrt p - 1)td)
-</math>
-. Každá procesor si vynásobí svojí matici vektorem
-<math>
-O ((\frac {n}{p})^2)
-</math>
-. Par. redukce na řádcích má stejnou složitost jako OAB, jedná se přesně o opačný proces
-+ sekvenční redukce jednotlivých vektorů
-paralelní komunikační část:
-<math>
-O (\frac {n}{p} log p tm + \(sqrt p - 1)td)
-</math>
-Každý procesor provede redukci na n/p číslech:
-<math>
-O (\frac {n}{p})
-</math>
-Složitost 4. fáze:
-<math>
-O (\frac {n}{p} log p tm +  \(sqrt p - 1)td + \frac {n}{p})
-</math>
-Celková složitost všech fází:
-<math>
-O ( ts + \sqrt p td + \frac{n}{p} tm + \frac {n}{p} log p tm +  \(sqrt p - 1)td + \frac {n}{p} log p tm +  \(sqrt p - 1)td +
-(\frac {n}{p})^2 + \frac {n}{p}) =
-O ( \sqrt p td + 2\frac {n}{p} log p tm + (\frac {n^2}{p}))
-</math>
-=== Celková složitost by měla být: ===
-<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
-FIXME
-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 ?
-FIXME
-==== Řešení 2 ====
-FIXME
-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:
-<code>
-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)
-}
-</code>
-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 [[par_řešené_příklady_12b#násobení_matice_vektorem_mapování_matice_blokově_šachovnicově|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ý:
-) 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)
-) 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 na SF 2D toroidu =====
@@ Line 915: / Line 364: @@
 tedy psí_1(p)= p^2, psí_2(N)= sqrt(N)
 ===== Alg. násobení matice A(√N,√N) mapované blokově po řádcích vektorem x(√N,1) mapovaným blokově na mřížku M(p) =====
@@ Line 1009: / Line 459: @@
 <math> p = \sqrt{N} = \psi_2(N) </math>\\
-{{tag>škola zkoušky s_řešením}}