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: 2012-05-18, 2014-01-06, 2013-01-09

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

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

• 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 je skoro stejný jako v případě 1, asymptoticky by měl vyjít stejně.

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

Tedy

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

A druhá část je hned :

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

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

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

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

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

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

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

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

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