====== PDP - Vyřešené zkouškové příklady za 12 bodů ======
===== Násobení matice vektorem, mapování matice blokově šachovnicově ===== 
Násobení matice vektorem, mapování matice <math>A(sqrt{N}, sqrt{N} )</math> BLOKOVĚ šachovnicově na 2D mřížku <math>M(sqrt{p}, sqrt{p} )</math>, vektor <math>X(sqrt{N})</math> na první sloupec procesorů mapovaných šachovitě, WH. Popsat algoritmus, co nejpřesněji T(N, p), spočítat Ψ1(p), Ψ2(N). Sekvenční násobení matice <math>r</math>x<math>r</math> vektorem <math>r</math> trvá čas <math>\alpha r^{2}</math>.

★ //Bylo ve zkoušce: [[par_zkouska_2012-05-18|2012-05-18]], [[škola:předměty:mi-par:par_zkouska_2014-01-06|2014-01-06]], [[par_zkouska_2013-01-09|2013-01-09]] //
==== Řešení ===

:!://Viz skripta CZ [2006] str. 196-197 nebo EN [2009] str. 181, přednáška FIT [12/2012] slajd 15-16//

==Algoritmus==
  - Krok 1: Poslat části vektoru X na diagonálu
  - Krok 2: OAB ve sloupci
  - Krok 3: Lokální násobení submatic
  - Krok 4: V řádcích se provedou nejdřív lokální redukce na jednotlivých procesorech a následně i paralelní redukce s výsledkem v prvním sloupci.

  * Každý procesor si drží svou submatici velikosti <math>\frac{\sqrt N}{\sqrt p}</math> x <math>\frac{\sqrt N}{\sqrt p}</math> a procesory v prvním sloupci mřížky mají každý <math>\frac{\sqrt N}{\sqrt p}</math> vektoru X.

== Postup 1 ==
  * **Krok 1)** Posílání vektoru X na diagonálu procesorů. Musí se počkat na toho nejpomalejšího - toho který posílá na nejdelší vzdálenost :

Vychází ze vzorečku: \\
<math>t_{s} + \underbrace{d}_{\text{ Vzdalenost }} t_{d} + \underbrace{\mu}_{\text{ Velikost dat}} t_{m}</math>\\

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

  * **Krok 2)** OAB paralelně ve sloupcích zabere na WH:
Vychází ze vzorečku (počítáme s nejhorším případem, tj. o levý horní nebo pravý spodní procesor v dané mřížce, asymptoticky ale mají tak jako tak všechny procesory stejnou složitost, nejlepší to mají ty procesory uprostřed, kteří to zvládnou "jenom" 2x rychleji (může to posílat na obě strany)): \\
<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 2 ==
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 

  - Krok 1: Poslat vektor části vektoru X na diagonálu
  - Krok 2: OAB ve sloupci
  - Krok 3: Lokální násobení submatic
  - 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>\\


== Postup 2.2 ==

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



== 2.2.1. Posílání dat ==
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>\\

== 2.2.2. Vytváření cesty ==
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>\\

== 2.2.merge ==
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).**


== postup 2.1 ==
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 [[https://www.fit-wiki.cz/%C5%A1kola/p%C5%99edm%C4%9Bty/mi-par/principy_%C5%99e%C5%A1en%C3%AD_%C3%BAloh#odmocnina_navíc|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 [[par_sachovnice_druhe_reseni|zde]]

{{tag>zkoušky s_řešením škola}}