Odvoďte maximální y takové, že mřížku <math>M(3,y)</math> vnoříme do mřížky <math>M(10,9)</math> s dil = 1 a load = 2. Příslušné vnoření popište algebraicky nebo schématickým obrázkem. Odvoďte hodnotu hranového zahlcení.

Mareen: Použitím harmoniky (viz příklady za 4b, PAR - Vyřešené zkouškové příklady za 4 body) v prostřední rovince se dosáhne y=48, ecng = 2:

Vnoření M(22,24) do M(x,5) s load=2 a min dil, určit ecng.

Viz skripta CZ [2006] str. 87 nebo EN [2009] str. 70

<math>\frac{22}{2}=11</math>
<math>11*5=55=x</math>
<math>ecng=6</math>

Edit1: Dobře se to počítá takto:

Na horní straně se střídá pět druhů hran. U každé z nich musíme ověřit ecng. Vezměme si jednu z nich. Podíváme se, jaký “vrchol hada” se nachází bezprostředně nalevo od ní. Najdeme první odpovídající “vrchol hada” napravo od ní. Pak snadno odpočítáme od toho pravého, vzdálenějšího, počet “vrcholů hada” cestou doleva směrem k naší hraně. Tyto všechny pravé “vrcholy hada”, včetně toho prvního, musí vést doleva přes naší hranu. A těch je pět pro každou z pěti druhů hran. K tomu ale nesmíme zapomenout u příslušných hran přičíst jednoduchou, “hadovou” hranu. To znamená, že ecng = 6.

Edit2: chvíli mi trvalo, než jsem prokouknul tuhle kupeckou matematiku, takže to radši rozepíšu: Celkem chceme namotat 22 hadů do cílové mřížky. Z obrázku vidíme, že 2 hadi zaberou 5 sloupců. Kolik sloupců zabere 22 hadů (hint: trojčlenka)? 22 hadů zabere 55 sloupců.

Edit3: Spočtení ecng a dil je jednoduché. Zde je obrázek k popisu v Edit1:

Klíčové je správně určit místo, kde budeme měřit - je jasné, že na kraji by nám to vyšlo jinak.

Vnoření M(13,13) do M(x,5) s load=2 a min dil, určit ecng.

Viz skripta CZ [2006] str. 87 nebo EN [2009] str. 70

<math>x = 20</math>
<math>ecng = 4</math>
<math>dil = 2</math>

To poslední mapování hrany, ten modrý oblouček co začíná nejvíc vpravo nepřechází přes tu hranu, kterou pozorujeme ( svislá růžová čára ), takže ta se do ecng nepočítá, ale tlusta cervena vodorovna hrana, ktera tu svislou caru krizuje ( spoj v rámci stejnýho sloupce ) už jo.

• ENG skripta str. 150 dole
• CZ skripta str. 173
• přednáška 10 / slide 16 (2015)

• na začátku zdroj rozešle paket všemi možnými směry
• pokud mi přišel paket z i-té dimenze, pošli ho dál v i-té dimenzi, pokud nejsem v i-té dimenzi poslední
• pošli paket v dimenzích (i+1)+, (i+1)-, …, (n-1)+, (n-1)-

<math>\rho = exc(M(…), s)</math> - nikdy nemůžu být rychlejší než vzdálenost nejvzdálenějšího uzlu od zdroje. Pozor spodní mez není poloměr mřížky, musíte tam napsat, že je to excentricita, jinak je to špatně.

<math>\tau = exc(M(…), s)(t_s + \mu t_d)</math> - délka jednoho kroku v SF mřížce je 1 a dělám <math>exc(G, s)</math> kroků, proto takový výraz

<math>r = diam(M(…)) = z_1 + … + z_n</math> - zdroj má nejhorší vzdálenost do nejvzdálenějšího uzlu právě průměr grafu

<math>t = diam(M(…))(t_s + \mu t_d) = (z_1 + … + z_n)(t_s + \mu t_d)</math>

Dotaz: Nesedí mi výše uvedený diam(M(…)). Ten se podle mě rovná: <math>\sum_{i=1}^{n}\left(z_{i}-1\right)</math>.

Máš pravdu, ale Tvrdík mi to uznal tak, jak to tu je. Možná chvilková slabost, říkal totiž, že tenhle příklad přede mnou ještě nikdo neudělal…

Dotaz II.: Můžete mi prosím vysvětlit, co ve výše uvedeném vzorečku znamená <math>t_s</math>? V přednáškách je u tohoto příkladu SF zpoždění zapsáno jako <math>t_s + t_d + \mu t_m</math>. Chápu, že je to asi nepodstatné, ale přijde mi, že je to pokaždé značené jinak.

Tento algoritmus je krokově i časově optimální.

hanouto: Přidal jsem navíc obrázek s nejhorším případem v 3D mřížce, k optimalitě jen napsal, že optimální je bez nějakého dalšího odůvodnění a plný počet bodů.

Přednáška 7/7 2014, skripta eng 96(dole + figure 6.8)

PPS EREW PRAM - základní optimální algoritmus

★ Bylo ve zkoušce: 2015-01-28 (samotný PPS EREW PRAM)

• SF mřížka neumožňuje lepší časové řešení než hloupé sekvenční řešení, protože posílání zpráv v SF je citlivé na vzdálenost.
• Na WH použijeme simulaci PPS na přímém stromu, který zploštíme do 1D lineárního pole.

Simulace na přímém stromu(Lemma 6.5):

Simulovat stromový PPS v <math>T = O (\log {n})</math> krocích

Pokud je p<n, pak <math>T(n,p) = O ( \frac{n}{p} + \log {p})</math>, součet má fáze:

1. Každý procesor provede součet nad svými čísly v <math>T_1 = O (\frac{n}{p})</math> krocích.
2. Provede se PPS nad p hodnotami. <math>T_2 = O (\log{p})</math>
3. <math>P_i</math> pošle svůj součet procesoru <math>P _i _+ _1</math>. <math>T_3 = O (1)</math> Edit: Tento krok platí pro PRAM, ale ne pro strom, kde není nutné nic posílat.
4. <math>P_i</math> přijme hodnotu a provede dopočet nad svými hodnotami. <math>T_4 = O (\frac{n}{p})</math>

<math>T(n,p) = O ( \frac{n}{p} + \log {p} + 1 + \frac{n}{p}) = O ( \frac{n}{p} + \log {p})</math>

PPS na stromě funguje takto:

1. Každý list pošle svému rodiči svoji hodnotu.
2. Rodič sečte hodnoty od svývh podstromů a pošle je svému rodiči. Hodnotu z levého podstromu pošle do pravého podstromu.
3. Co dostane od svého rodiče pošle svým potomkům

Na 2-portové mřížce se z hlediska maximálního počtu kroků nic nezlepší, pouze bude větší množství uzlů dříve informovaných.

“Důkaz správnosti”: 28.1.2015 - VasekJ: u PPS na PRAMu nemusíte ani psát psedoalgoritmus, stačí pouze popsat obrázek

Pero: Můžete mi prosím tohle někdo vysvětlit? Jednak nechápu, jak se třeba 3. krok může provést v jednom kroku na WH mřížce, vždyť se ty cesty kříží. A pak v tom vůbec nevidím simulaci PPS přímého stromu. Na stromu například v prvním kroku probíhá komunikace (při postfix značení) mezi uzly 1-3, 4-6, 8-10, 11-13.

Vysvětlení k simulaci na WH: Není to tam jednoduše vidět, ale je to tam :)

Vychází to z paralelní redukce na WH mřížce:

Nejlépe je to vysvětlené na videu ze 7. přednášky z roku 2004 (https://mipar.vjirovsky.cz/data.lecture/detail200407), ve skriptech ani na pozdějších přednáškách se o tom moc Tvrdík nezmiňuje. Jedná se o simulaci nepřímého úplného binárního stromu s 16 listy a tedy výškou 4. Z toho vyplývá i počet kroků, který je <math>2*T(h)=2*4=8</math>

Tady je stejný algoritmus jako na obrázku od Tvrdíka, jen odkrokovaný na nepřímém stromu. Stále platí pravidlo pošli data rodiči (modrá nahoru), rodič pošle hodnoty z levého podstromu do pravého podstromu (modrá dolů) a co dostane rodič od rodiče, pošle potomkům (červená).

Popište pseudokódem NC algoritmus pro paralelní sčítání 2 n-bitových čísel a dokažte jeho korektnost. Odvoďte jeho časovou složitost T(n,p), 1 ≤ p ≤ n, na EREW PRAM v jednotkovém modelu (čili všechny R,L,W operace trvají jednotkový čas).

★ Bylo ve zkoušce: 2012-01-31

Viz skripta CZ [2006] str. 101-102, skripta EN [2009] str. 98-99

Rychlé paralelní sčítačky 2 n-bitových čísel musí obsahovat obvod pro predikci přenosu, jinak by operace sčítání trvala čas O(n). Pro tyto účely se používá PPS. Uvažujme 2 n-bitová čísla X a Y, z kterých chceme vypočítat Z v O(log n) krocích. To provedeme předpočítáním pole přenosových bitů C = Cn , … , C1, C0, kde vždy C0 = 0. Pole C vypočteme prefixovým součtem s operací, která je dána následující tabulkou:

for i=0,...,n-1 do_in_parallel {
  if (x[i]==y[i]==1) b[i]=g // generace
  else if (x[i]==y[i]==0) b[i]=s  // stop
  else b[i]=p // propagate
}
aplikuj PPS s operací [kolečko] nad B[] a ulož výsledek do B’[]
for i=1,...,n do_in_parallel {
  if (b‘[i-1]==g) c[i]=1
  else c[i]=0
}

Takto je podle mě kompletní kód:

def ParBinAdder(X, Y) {

    B = array(n + 1)
    B' = array(n)

    # Naplní pole B
    for i=0 .. n - 1 do_in_parallel {
        if X[i] == Y[i] == 1:
            B[i] = GENERATE
        elif X[i] == Y[i] == 0:
            B[i] = STOP
        else:
            B[i] = PROPAGATE
    }

    B[n] = STOP
    
    # Odstraní PROPAGATE
    B' = PPS(data=[B[n], ..., B[0], s], operation=(*))
    C = array(n, fill_with=0)

    for i=1 .. n do_in_parallel {
        if B'[i-1] == GENERATE:
            C[i] = 1
    }

    for i=0 .. n-1 do_in_parallel {
        Z[i] = X[i] + Y[i] + C[i]
    }
}

Můžete tu prosím ještě někdo vysvětlit, jak funguje to vytváření B' za pomoci operace kolečko? Jak je definováno B'[i]?

• Odpoved: jsem presvedceny, ze je to takhle - scitacka ma prenosy zprava doleva, takze i tady bude ta operace aplikovana zprava doleva, a kod pro sekvencni reseni by vypadal nejspis: for i:=n,…,1 do { B[i] := B[i+1] O B[i] } a takhle upravene pole B se nazve B'. Akorat paralelne se to nedela znak po znaku, ale logaritmicky pomoci PPS, kde se misto operace +:RxR→R pouzije to kolecko O:{g,s,p}x{g,s,p}→{g,s,p} (bliznjan)

Toto je schéma, jak se dělá PPS nad B:

Popis (korektnost): Algoritmus v každém bitu zjistí, jak se bude chovat přenos, zda vznikne vždy, nebo jen pokud přišel z nižšího bitu, nebo zda bude spolknut. Následný PPS dá tyto chování do souvislosti tím, že projde pole z LSB do MSB a odstraní propagace. Tím již víme, v jakém bitu budeme a v jakém nebudeme přičítat k součtu původních bitů přenos.

V prvním cyklu může každý procesor vyřídit naráz poměrnou část n/p bitů. Pro každý bit provede dvě čtení (x_i a y_i) a jeden zápis (b_i), tj. tři operace.

<math>T_1(n,p) = 3\frac{n}{p}</math>

PPS přes n bitů pomocí p procesorů trvá:

<math>T_2(n,p) = \alpha\frac{n}{p} + \beta log p</math>

Poslední cyklus dělá jedno čtení a jeden zápis pro každý bit, který má procesor na starosti.

<math>T_3(n,p) = 2\frac{n}{p}</math>

<math>T(n,p) = T_1(n,p) + T_2(n,p) + T_3(n,p) = 3\frac{n}{p} + \alpha\frac{n}{p} + \beta log p + 2\frac{n}{p} = (\alpha + 5) \frac{n}{p} + \beta log p = O(\frac{n}{p} + log p)</math>

Edit: Nechyba tu nahodou este jeden krok, kedy sa finane vypocita ten sucet? Ten algoritmus vypocita len carry-on pre kazdy bit, ale este potrebujeme 2 operacie citania a 1 operaciu na zapis na kazdy bit, aby sme mali finalny vysledok, nie? - Chybí, ale algoritmus tak jak je definovaný v definici 9 přednáška 7 slide 20 má na výstupu jenom pole C.

Edit 2: Chybí a na straně 99 v ENG skriptech je v textu ten součet popsán. Přidal jsem výše pseudokód, který obsahuje i finální součet Z=X+Y+C.

Jsou dány uzly u=[12,4,8], v=[5,9,3] v 3D mřížce M(14,16,10). Souřadnice uzlu začínají v každé dimenzi od nuly. Zkonstruujte všechny uzlově disjunktní cesty mezi u a v, aby byly co nejkratší a určete jejich délky. Řešení vysvětlete a popište algebraicky, doplňte schm. obrázkem.

Obrázek je špatně, což je zřejmé z nedokreslené poslední cesty - ta by v tomto obrázku již nešla udělat s délkou nejkratší cesty + 4. Správný obrázek i s vysvětlením viz příklad níže.

Počet cest je roven dvojnásobku počtu dimenzí. Nejkratší cesty v 3D M získám pomocí dimenzionálního X-Y-Z směrování ? pohyb striktně nejdříve v dimenzi X, potom v dimenzi Y a pak v dimenzi Z. Rotací pořadí dimenzí, zkonstruuji další 2 cesty ?
3 cesty délky (12 - 5) + (9 - 4) + (8 - 3) = 17

1. <math>(12,4,8) \rightarrow{X} (5,4,8) \rightarrow{Y}(5,9,8) \rightarrow{Z} (5,9,3)</math>
2. <math>(12,4,8) \rightarrow{Y} (12,9,8) \rightarrow{Z}(12,9,3) \rightarrow{X} (5,9,3)</math>
3. <math>(12,4,8) \rightarrow{Z} (12,4,3) \rightarrow{X}(5,4,3) \rightarrow{Y} (5,9,3)</math>

<math> Z^{-} + X^{\Delta X}+ Y^{+} + Z^{+} + Z^{ \Delta Z} + Y^{-} </math>
<math>Y^{-} + Z^{\Delta Z} + X^{\Delta X} + X^{+}</math>

Zbývající 3 cesty jsou délky 17 + 4 = 21 (vždy v dvou dimenzích odskočíme tam a zpátky)
<math>A^-</math> … pohyb v ose A v opačném směru než je cíl
<math>\Delta A</math> … pohyb v ose A o rozdíl mezi počátkem a cílem směrem k cíli
jedna cesta je: <math>X^-, \Delta Z, Z^+, \Delta X, X^+, \Delta Y, Z^-</math>
zbývající vzniknou zase rotací dimenzí

Pozn. tady na to pozor! Trošku jinak by se to počítalo kdyby uzly měli nějakou dimenzi shodnou. Pak existuje pouze jedna minimální cesta. Nemůže se obecně říct “Pro jakékoliv dva uzly.” Dobré je si to aspoň trochu načrtnout!

Pozn2 (bangom). Stejne tak pokud bude nejaky uzel na konci mrizky, tak do nej nepujde udelat maximalni pocet cest (stupen uzlu?)… kreslete si to

Cvičení 6, 16:10 začína 2D, 28:40 začína 3D, 43:50 začína 4D

Dány vnitřní uzly u a v ve 4D mřížce, zkonstruujte všechny možné uzlově disjunktní cesty z u do v takové, aby jejich délky byly co nejmenší. Řešení popište algebraicky a doplňte schematickým náčrtkem. Udejte délky a počty cest pro obecný případ dvou uzlu v k-rozměrné mřížce.

• Disjunktní cesty jsou takové, které nemají žádný společný uzel (krome zdroje a cile), tj. uzly se musí lišit ve všech dimenzích. Takových cest existuje 2*k.
• Zkonstruujeme k cest délky <math>\sum_{i=1}^{k}{|u_i-v_i|}</math> pomocí minimálního dimenzionálního směrování (začátek v dimenzi 1 ≤ i ≤ k).
• Dalších k cest délky <math>4+\sum_{i=1}^{k}{|u_i-v_i|}</math> zkonstruujeme takto:
  1. Začneme v dimenzi 1 ≤ i ≤ k a uděláme jeden krok ve směru -(v_i - u_i) (tj. „špatným směrem“).
  2. Z tohoto uzlu postupujeme pomocí minimálního směrování začínajícího dimenzí (i + 1) mod_k. Toto směrování má k kroků. Pro dimenze (i - 1) mod_k a i udělám jeden krok navíc – posunu se o |u_i - v_i| +1 hran.
  3. Poslední krok udělám v dimenzi j = (i - 1) mod_k ve směru -(v_j - u_j), tj. posunu se o 1 hranu až do cíle.

Protože mi to nefungovalo při kreslení ve 3D, řekl bych, že ten krok 2 je špatně. Podle mě by tam mělo být, že jeden krok navíc provedeme v dimenzi (i + 1) mod_k a dále jedeme dle minimálního směrování. Viz obrázek.

• Jelikož jsme na začátku šli špatným směrem jeden krok, musíme se taky o jeden krok vrátit ⇒ + 2 kroky oproti nejkratší cestě.
• Jelikož jsme v dimenzi (i + 1) mod_k šli o krok dál, musíme se o tento krok také vrátit ⇒ + další 2 kroky oproti nejkratší cestě.
• Celkem je tedy délka trasy: nejkratší cesta + 4.

Pokud si nebude jisti představou, kudy vlastně cesta vede, podívejte se na barvu v překřížení. Funguje to jednoduše - vždy se jde v pořadí XYZ nebo ZXY nebo YZX (rotace dimenzí). Při konstrukci delších cest (šedé) vyjdu špatným směrem, v následující dimenzi jdu o krok dál, než bych šel při minimálním směrování, a poté už jdu čistě dle minimálního směrování.

Tohle platí pouze pro případ, kdy se počáteční a cílový uzel liší ve všech dimenzích a nejsou na okraji mřížky. Jinak je počet cest rovný nejnižšímu stupni z obou uzlů. V případě, že mají nějaké dimenze stejné, se více cest vede s odskokem. Až někdo bude mít náladu, vymyslete univerzální postup.

Neví někdo, jak na papír nakreslit cestu ve 4D mřížce, resp. hyperkrychli? Halucinogenní látky jsou přeci ve škole zakázané… (edit to uz sis spis neco vzal, ze to nedokazes, ne? :))

Cvičení 6, 16:10 začína 2D, 28:40 začína 3D, 43:50 začína 4D Kde tohle “cvičení” seženu? Doplnit odkaz prosím.

Mně to připadá nějaké složité. Nestačí tato jednoduchá úvaha? Nejkratší cesty získám minimiálním směrováním. V každém kroku se tedy musím přibližovat cíli. Z toho plyne, že v prvním kroku musím udělat posun v jakékoli dimenzi směrem k cíli, čili mám n možností, kam se vydat. (Kde n je počet dimenzí, ve kterých se uzly u a v liší.) Neplyne z toho rovnou, že cest je n? Jakákoli další by musela v prvním kroku jít přes jeden z n již použitých uzlů a nebyla by s předchozími uzlově disjuktní. Jedna taková triviální n-tice je postupný průchod dimenzemi, tak že začnu pokaždé jinou (ABCD, BACD, CABD, DABC). Není to vše, co je potřeba pro plný počet? Nebo je jasné, že jich je n, ale jde v úloze o to zkontruovat VŠECHNY takové n-tice uzlově disjunktních cest? (plech.d)

Nestačí. Nemáš najít pouze nejkratší cesty, ale všechny disjunktní cesty tak, aby byly co nejkratší. Disjunktních cest může být max 2*dimenze (to ti požere všechny sousední uzly k počátečnímu uzlu a žádné disjunktní cesty už neuděláš) a ty se je snažíš najít tak, aby byly co nejkratší → najdeš dimeze-krát úplně nejkratších pomocí přímýho směrování + ty úhybný. (hroncmir)