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

(jestli je to full duplex nebo ne bývá v zadání. tohle je full duplex. )

Viz přednáška 11 FIT slajd 10

Algoritmus pro AAB na k-rozměrné 1-portové mřížce s kombinováním paketů je založen na AAB na 1 rozměrné 1-portové mřížce. Provádí se technikou sudo-lichých výměn.

• V lichém kroku si každý lichý a následující sudý vymění zprávy. Posílají pouze nové zprávy, to jest ty, které se dozvěděly v předchozím kroku (neplatí pro první dva kroky, viz dále).
• V sudém kroku udělá to samé každý sudý a následující lichý.
• Na M(z) je počet kroků k = z, pokud je z liché, k = z-1 v opačném případě.

Na začátku má každý uzel svou jednu zprávu, kterou chce poslat všem ostatním. V prvním kroku si tedy každá licho-sudá dvojice uzlů vymění vzájemně jednu zprávu, čímž už bude mít každý zprávy dvě (kromě posledního v případě lichého počtu uzlů). Ve druhém kroku si každá sudo-lichá dvojice vymění vše co mají, což jest dvě zprávy. V každém dalším kroku už se vyměňují pouze ty zprávy, které uzel nově obdržel v předchozím kroku, což jsou pokaždé právě dvě zprávy. Velikost zprávy je tedy v podstatě konstantní a délka trasy je vždy 1.

Obrázek za tisíc slov:

Je-li z liché: <math>r_{\tiny AAB} = z,\: t_{\tiny AAB} = z t_s + (2z-2) \mu t_m</math>,

jinak: <math>r_{\tiny AAB} = z-1,\: t_{\tiny AAB} = (z-1) t_s + (2z-3) \mu t_m</math>.

To (2z - 2) vykoukám z obrázku. V prvním kroku pošle jednička jeden paket velikosti <math>\mu</math> dvojce a dvojka jeden paket velikosti <math>\mu</math> jedničce. Protože to ty procesory provádějí paralelně, tak je zpoždění v prvním kroku <math>\mu t_m</math>. V druhém kroku jeden procesor posílá najednou dva pakety, proto <math>2 \mu t_m</math>. Ve třetím kroku <math>\mu t_m</math>. Dohromady tedy <math>4 \mu t_m</math>. Když to zobecním, tak (2z - 2).

Na více rozměrné mřížce se postupuje po dimenzích. Například ve 2D mřížce se nejprve provede AAB ve všech řádcích (tj. dimenze z₁), poté ve všech sloupcích (tj. dimenze z₂).

<math>r_{\tiny AAB} = \sum_{i=1}^k r_{\tiny AAB}(M(z_i)) = \sum_{i=1}^k z_i - (z_i-1 \normalsize\text{ mod2})</math>

Na začátku bude každý uzel začínat s jednou zprávou. Po dokončení AAB v první dimenzi už bude mít každý uzel tolik zpráv, kolik je velikost této dimenze. V dalším AAB ve druhé dimenzi už tedy budou uzly začínat se <math>\normalsize z_1</math> a končit se <math>\normalsize z_1 \cdot z_2</math> zprávami. A tak dále.

<math>t_{\tiny AAB}(M(z_1,….,z_n),\mu) = \sum_{i=1}^k t_{\tiny AAB}(M(z_i),(\prod_{j=1}^{i-1} z_j) \cdot \mu))</math>

v tom vzorečku chybí ta zpoždění Ts a Tm. Těch Ts bude asi stejně jako r(AAB), ta Tm je třeba ověřit, já jsem do toho vzorečku ještě nepronikl…

Řekl bych, že:

<math>t_{\tiny AAB}(M(z_1,….,z_n),\mu) = \sum_{i=1}^n t_{\tiny AAB}(M(z_i),(\prod_{j=1}^{i-1} z_j) \cdot \mu) = \sum_{i=1}^n ( (z_i - 1 + (z_i mod 2) ) t_s + (2 z_i - 3 + (z_i mod 2) ) t_m \mu \prod_{j=1}^{i-1} z_j )</math>

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

Popsat směrování na 1D toroidu odolné proti deadlocku + jaké řešení + důkaz.

Popis je jasný, prostě člověk musí umět teorii

Viz skripta CZ [2006] str. 146, skripta EN [2009] str. 90, prednaska 6, strana 38.

Důkaz se udělá tak, že se nakreslí graf kanál. závislostí a ukáže se, že neobsahuje cykly.

Dodatek by voho (nejsem si ale jistý): Dělá se to přes virtuální kanály. V toroidu o dimenzi N má každý uzel 2N sousedů (portů). Každý port může být plně duplexní. Kdybychom byli v mřížce, tak uděláme dimenzionálně uspořádané směrování, ale to v toroidu nejde (viz tornádo, cyklický posun). Když chceme zamezit deadlocku, rozdělíme fyzické kanály logicky na dva poloduplexní virtuální kanály (VK). Změní se směrovací funkce, která podle nějaké hlavičky v paketu pozná, ve kterém VK se paket pohybuje. Mějme VK incr a decr. VK incr se využívá pouze pro posílání paketů v striktně rostoucím pořadí, VK decr pro posílání paketů v pořadí striktně klesajícím.

Pro 1D toroid K(z) a směrování mezi uzly u, v

Jestliže <math>u < v</math>, posílají se pakety v kanálu <math>c_{1u} \ldots c_{10}</math> a pak <math>c_{0(z-1)} \ldots c_{0(v+1)}</math>. Jestliže <math>u > v</math>, posílají se pakety v kanálu <math>c_{0u} \ldots c_{0(v+1)}</math>.

edit Radek: nejlépe je to vidět na obrázku ze skript, pokud je uzel tedy uzel <math>u < v</math>, pak se jde horní cestou přes <math>c_{1u} \ldots c_{10}</math> a pak se pokračuje spodní cestou <math>c_{0(z-1)} \ldots c_{0(v+1)}</math>. Tím dojde ke zrušení cyklu a nemožnosti vzniknutí zablokování.

pozn.: každý fyzický kanál lze rozdělit na <math>k >= 2</math> virtuálních kanálů

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.

★ Bylo ve zkoušce: 2012-05-18

Popište EREW PRAM algoritmus pro výpočet pořadí uzlů při průchodu inorder (levý podstrom, kořen, pravý podstrom) všech n uzlů Eulerova binárního stromu S. Výsledkem bude pole IN[1..n]. Eulerův strom S má m = 2n-2 hran a je reprezentován polem uzlů, které mají odkazy na cyklický seznam svých hran. Předpokládejte, že je již zkonstruovaná Eulerova cesta vzniklá při průchodu S do hloubky a je uložená v poli EA[1..m], kde EA[i] je i-tá hrana této cesty. Odvoďte paralelní čas T(m,p) pro 1 ≤ p ≤ m tohoto algoritmu. Předpokládejte, že lokální operace trvají jednotkový čas a operace R/W mají čas d > 1.

Podobná myšlenka jako PreOrder Přednáška 7 slide 42

alg. EREW_PRAM_InOrder(In:EA[1..m]; Out: inOrder[1..n])
  for xy in EA do parallel:
    if xy.direction <> xy.next.direction      // ak má moje next hrana jinou orientaci než já
      weight[xy.next] = 1
    else 
      weight[xy.next] = 0
  
  call pps on EA
  
  for xy in EA list do parallel:
    if xy.direction <> xy.next.direction then
      inOrder[y] = weight[xy]

malo by to fungovat pre binarne stromy, v tejto podobe to cisluje od '1'
este by sa tam asi malo doplnit, ze pre koren plati: root = pocet uzlov

Pozn. Pozor, není myšlena next hrana dle definice reprezentace grafu pro Eulerovské stromy jako je tomu v přednášce 7/34, ale je tím myšlena následující hrana v eulerovské cestě.

Časová složitost tohoto algoritmu je velice podobná jako paralelní sčítačka. Jen koeficient u m/p bude o pár jednotek vyšší.

Pokud algoritmus správně chápu, tak není korektní, protože přestane fungovat ve chvíli, kdy nějaký uzel nemá levý podstrom (extrémní případ by byl třeba spojový seznam).

EA je eulerovský strom, podívej se na přednášku 7 slide 41, tam je krásně nakreslený jak vypadá. Tvoří eulerovskou kružnici, takže tam vždycky bude next.

EDIT: Trošku problém může být, že neznáme next. V EA máme uloženou jen hranu a její směr (Down, Up).

JDU: Domnívám se, že ten pseudokód nefunguje. Už když ten strom bude vypadat jako nudle doleva a na konci třešeň tak to nečísluje dobře (ty uzly v té nudli to kvůli tomu IF ani nijak neočísluje, protože jejich NEXT nemá jiný směr).

EDIT: Předpokládam, že ten algoritmus je zamýšlen pro plné bin. stromy - každý vnitřní uzel ma pravý i levý podstrom. Ostatně u neplných stromů jako ten, který navrhuje JDU nedává in-order číslování smysl

Pero: Myšlenka algoritmu mi připadá správná, ale nefungovala by, pokud by poslední patro binárního stromu nebylo plné. Ale snad to jen někdo tady zapomněl dopsat do zadání, že je úplný.
Jen ten algoritmus není dotažený do konce, má někdo nápad, jak nakonec získám to pole IN?

Edit VD: Myslím, že algoritmus funguje správně, ale tedy jen na binární stromy. Jak je uvedeno výše, že ještě potřebujeme root = pocet uzlov, tak to podle mě není pravda (alespoň pokud si alg. odkrokujete na binárním stromu, kořen dostane správné číslo).

def EREW_PRAM_InOrder([] EA) {

  for edge in EA do_in_parallel {
		# Tato hrana má jinou orientaci než další hrana
		# v eulerovské cestě
		if edge.Direction != edge.Next.Direction:
			# Pozor: ne této hraně ale další
			EA[indexOf(edget.Next)].Weight = 1
		else:
			EA[indexOf(edget.Next)].Weight = 0	
	}	

	pps(EA, on_attribute=Weight)
	InOrder = array(EA.Length)

  for edge in EA do_in_parallel {
		# Tato hrana má jinou orientaci než další hrana
		# v eulerovské cestě
		if edge.Direction != edge.Next.Direction:
			# edge = x -> y (hrana vede z vrcholu x do y)
			InOrder[edge.Y] = EA[indexOf(edge)].Weight
	}
	
	return InOrder; 
}

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

Slajd 7/34 FEL

Analogicky jako EREW PRAM (třeba číslování preorder), jen hrany dolů ohodnotím 1 a hrany nahoru -1. Důležité je podle mě taky to, jaký byl vstup. Tím byl graf, každý uzel znal odkazy do pole na své hrany, hrany znaly odkazy na své protějšky a byla zkonstruována eulerovská kružnice, která byla k dispozici ve formě pole jako zobrazení pořadí hrany v kružnici → idetifikátor hrany.

Zde stejný algoritmus jen to trochu připomíná kód:

def EREW_PRAM_AllLevels(EA):
    for edge in EA do_in_parallel:
        if edge.Direction == DOWN:
            ea.Weight = 1
        else:
            ea.Weight = -1
 
    pps(EA, on_attribute=Weight)
    Level = array(EA.Length)
 
    for edge in EA do_in_parallel:
        if edge.Direction == DOWN:
            # edge = x -> y
            Level[edge.Y] = EA[indexOf(edge)].Weight
 
    Level[indexOf(ROOT)] = 0
 
    return Level

★ Bylo ve zkoušce: 2013-01-09

viz skripta x36par-skriptacz2.pdf strana 161 nebo přednáška 9 slide 30 (2013/2014)

Důkaz je induktivní, v prvním kroku může dojít ke kolizi při směrování podle nejnižšího bitu. Je zřejmé, že ke kolizi může dojít pouze pro dvojici sousedů spojených hranou v nejnižší dimenzi (tj. máme uzly bbb0 a bbb1).
Jelikož je to sousední dvojice, tak i ve výsledku budou sousední v tomto pořadí (z definice zhuštění).

Tedy mohou nastat dva případy :

1. “bbb0→ccc0, bbb1→ccc1”: výsledné permutované dva uzly mají stejný nejnižší bit ⇒ v e-cube směrování k pohybu nedochází ⇒ kolize nenastane
2. “bbb0→ccc1, bbb1→ddd0”: výsledné permutované dva uzly mají rozdílný nejnižší bit ⇒ e-cube směrování generuje pohyb v nejnižší dimenzi ⇒ oba se pohnou a vymění si pozice ⇒ opět bezkolizní ⇒ tímto krokem se každý z obou uzlů vnoří do jiné podkrychle Qn-1. Pro ni dokážeme bezkoliznost stejným způsobem.

Jak se může v druhém bodu vnořit do jiné podkrychle, když permutoval na nejnižším bitu (a ne na nejvyšším)?

Pozn: Neni tady nahodou ta druha cast spatne? Ja bych rekl, ze ten nejnizsi bit je ten nejvic v pravo.

Pozn: Zhusteni zachovava poradi, takze kdyz jeden paket zacina na uzlu s poslednim bitem = 0 a druhy vedle nej, tedy s poslednim bitem = 1, budou i ve vysledku muset mit v cili posledni bit roven: jeden 0 a druhy 1 nebo opacne) Proto mame 2 moznosti viz vyse.

Zaroven se tu pouziva e-cube smerovani, ktere postupne porovnava bity zdrojoveho a ciloveho uzlu - pokud se nelisi (prvni pripad, protoze posledni bit v cili ccc0 a zdroji bbb0 je stejny), posle ty 2 pakety pod sebou rovne ⇒ nedojde ke kolizi. V druhem pripade se zdrojovy a cilovy uzel lisi v poslednim bite ⇒ bude se lisit i u zdroje a cile toho druheho paketu. Opet e-cube porovna i-ty bit zdroje a cile a pokud se lisi, posle pakety krizem ⇒ opet nebude kolize - nenabouraji do sebe

Ještě přidám moji verzi (bliznjan): V i-tém kroku (kroky i bity indexuji od nuly, bity indexuji zprava od nejnižšího) řeším vzájemně pouze ty dvojice paketů, jejichž souřadnice se liší právě v i-tém bitu zprava (jinak by v Qn nebyly v sousedních uzlech). Kolize by mohla nastat, kdybych takovouto dvojici paketů chtěl přesunout do stejného uzlu, tedy na stejné souřadnice. Vzhledem k e-cube směrování už mám bity vpravo (nižší) vyřešené a mohou se v následujících krocích měnit už jen vyšší bity, ale ty se naopak zatím neměnily. U dvou paketů, co zrovna řeším, tudíž platí, že jejich vyšší bity byly od začátku rovny, takže na začátku (i teď) byly od sebe vzdálené o méně než <math>2^{i+1}</math> pozic (vzdáleností nemyslím Hammingovu vzdálenost, ale to celkové pořadí, o které ve zhuštění jde). Po celkovém zhuštění nesmí dva pakety skončit na stejné pozici, a proto kdybych teď, v i-tém kroku, oběma nastavil i-tý bit na stejnou hodnotu, tak bych potom v dalších krocích musel nastavit alespoň jeden jejich bit ve vyšších pozicích na různé hodnoty. Kdybych nějaký vyšší bit změnil, tak by pak ale ve výsledku byla vzdálenost (opět nemyslím Hammingovu) alespoň <math>2^{i+1}</math>, takže by byla vzdálenost vyšší než před zhuštěním, jenže zhuštění nikdy vzdálenost zvýšit nesmí, takže by to byl spor s tím, že se jedná o zhuštění.

Popište, jak si procesory na zadané indBFn zjistí pořadí, když lokálně mají jen flag 0/1 (zda patří do množiny) a následně proveďte neúplnou online permutaci zhuštění procesorů s flagem 1. Dokažte, že online směrování na indBF je pro ni bezkolizní

★ Bylo ve zkoušce: 2016-01-15

zjištění cílového umístění, když teď zná jen ten flag 0/1 - provede se prefixový součet, viz obrázek, předpokladem je třeba, že přepínače po cestě umí sčítat, naprosto v pohodě mi zde uznal, že se udělá PPS, napsat co je PPS (1-2 věty) a obrázek

V podstatě stejné jako přechdchozí příklad (s e-cube směrováním).

Důkaz je ve slidech, slide 31 přednáška 9 (pro oBFn, ale to je v skoro to samé).

Minimální směrování v indBFn funguje tak, že se porovnají adresy cíle a zdroje (postupně od LSB k MSB, v každé úrovni jeden). Když se bit adresy zdroje a cíle liší, tak se jde směrovačem křížem, když se neliší, tak se jde rovně.

Kolize může nastat v 1. úrovni motýlka pouze pro sousední uzly (tedy např. zdrojové uzly bbbb0 a bbbb1). Ty se permutují buď na uzly se stejnou paritou (xxxx0 a xxxx1) nebo s opačnou paritou (xxxx1 a xxxy0). Žádný jiný případ nemůže nastat. Když je parita stejná, tak oba uzly chtějí v cestě pokračovat rovně - není kolize a když je různá, tak chtějí oba pokračovat křížem - není kolize.

Po prvním stupni indBFn budou pakety směrovány do disjunktních podmotýlků indBFn-1 a důkaz tam induktivně probíhá stejně.

Dokažte, že v Qn je operace přeložení i→i xor w je při směrování e-cube bezkolizní (w je n-bitová posloupnost)

E-cube směrování se řídí bity řetězce w (protože <math>i \; \oplus_2 \; (i \; \oplus_2 \; w) = w</math>). w je v podstatě maska - tam, kde má w 1, tam se invertuje bit i. Jinak řečeno, po hranách se bude přecházet v těch dimenzích, kde má w bit nastavený na 1. Např. pro <math>Q_3</math> a <math>w = 001</math> se bude přecházet po hraně v první dimenzi, pro <math>w = 110</math> v druhé a třetí.

Ke kolizi může nastat v libovolném kroku k mezi uzly spojenými hranou dimenze k.

Existují 2 možnosti:

• a) k-tý bit řetězce w je 0 ⇒ k pohybu v k-té dimenzi nedojde ⇒ kolize nenastává
• b) k-tý bit řetězce w je 1 ⇒ u obou uzlů dojde k pohybu v dimenzi k ⇒ vymění se pozice ⇒ kolize nenastává

Pozn. by Klaara (ad pochybnosti o XORech): Řešení je OK. Jde o to si jakoby “vyjádřit” w. A že w = i XOR (i XOR w), to prostě platí :), zkuste si to na příkladu. Taky si to můžete představit tak, že vám někdo zadá jen i → j, tj. adresy zdroje a cíle. A vy z toho potřebujete vytáhnout ty rozdílné bity, což zjistíte tak, že uděláte i XOR j. Když za j dosadíte (i XOR w), vyjde zas to samé. - no a čo? Úloha znie dokáž bezkolíznosť a nie nájdi w, ktoré je zadané. Celý pokec o dvoch XORoch je tu podľa mňa zbytočný a zavádza.

—

Edit: dovysvětlení by Rulfik
jelikož permutace na <math>Q_n</math> je definována následujícím předpisem <math>\pi_{u \mapsto v}(x)= x\oplus (u \oplus v)</math>, kde <math> \oplus </math> je bitová nonekvivalence (XOR). A v zadání je přeložení <math>{u \mapsto v}</math> zadáno pro <math>u = i</math> a <math>v = i \oplus w</math>

Potom cílová adresa permutovaného paketu vyslaného z uzlu <math>x</math> v <math>Q_n</math> po přeložení je dána následujícím vzorcem <math>i \oplus i \oplus w \oplus x = w \oplus x</math>

Edit: aby to bylo jasné, jak jsme se dostali k tomuto vzorci: <math>\overbrace{i}^{u}\mapsto\overbrace{i\,\mathtt{XOR}\,w}^{v}\text{.}</math>

xor je definován následovně

Je nutné si uvědomit, že se směruje e-cube (tedy po jednotlivých dimenzích od LSB k MSB) tedy celkem v n krocích. Pro každý k-tý krok mohou nastat následující 2 případy:

Je li w=0, pak k-tý bit adresy paketu zůstává nezměněn, ke směrování nedochází = žádná kolize

Je-li w=1, pak k-tý bit se zneguje = čili u dvou sousedních uzlů dojde ke křížové výměně paketů = žádná kolize.

Čili je pravda, že směrování se řídí bity řetězce k jak již bylo uvedeno.

Dokažte, že minimální směřování pro nepřímý oBF_n je vždy uzlově disjuktní pro permutaci cyklicky posun <math>\pi^{\delta}_{s} : (0, i) \mapsto (n, i \oplus_{2^n} \delta), i \in = \{1, .., 2^n\}</math> (posouváme o <math>\delta</math>), kde <math>\delta</math> je konstanta.

★ Bylo ve zkoušce: 2011-05-19

mi-par2015-prednaska9-permutations.pdf slide 34

Cyklický posun jsou 2 operace zhuštění na stejné síti. Důkaz je tedy skoro stejný jako u důkazu že zhuštění je bezkonfliktní:

1. záleží na paritě slova o které se posouváme. Pokud je parita lichá, v prvním sloupci se vždy nastaví přepínače křížem = není kolize. Pokud je parita sudá, nejnižší bit se vůbec nemění a čili se nastaví přepínače rovně = není kolize
2. jelikož výstupy ze stupně 0 jdou na vstupy disjunktních podmotýlků, dá se 1) aplikovat znovu.

(a) Cyklický posun o <math>\delta=5</math> na <math>indBF_{4}</math>, (b) Cyklický posun o <math>\delta=10</math> na <math>indBF_{4}</math>.

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)

Řešení obdobného příkladu: PAR - Vyřešené zkouškové příklady za 8 bodů

Dokázat, že každou monotónní permutaci lze na SF oBFn realizovat bezkolizně, tj. v O(n) krocích, odhadnout skrytou konstantu

Viz skripta [2006] str. 161-162 && [2015] 9. přednáška / slide 33

Monotónní permutace se skládá ze zhušťovací, roztažné a identity. Identita je triviálně bezkolizní, to vyplývá přímo z její definice. Roztažná je jen zrcadlová ke zhušťovací. Musíme tedy dokázat, že zhuštění je bezkolizní.

Důkaz je induktivní. Uvažujme, že žádné dva pakety se nemohou srazit na stejném uzlu v 1. úrovni (číslujeme od nuly). Ke kolizi by mohlo dojít jen mezi pakety, které by tvořily sudo–lichou dvojici po sobě jdoucích paketů. Tyto pakety by ovšem po zhuštění skončily také na dvou po sobě jdoucích výstupech. Mohou nastat dvě situace:

1. Výstupní uzly budou sudo–lichá dvojice (nejnižší bit se neliší). → Pakety šly v 1. úrovni rovně (dle pravidel min. směrování). → Nemohlo dojít ke kolizi.
2. Výstupní uzly budou licho–sudá dvojice (nejnižší bit se liší). → Pakety šly v 1. úrovni křížem. → Nemohlo dojít ke kolizi.

Po tomto kroku se pakety dostanou na vstupy dvou navzájem disjunktních podmotýlků oBF_n-1 (sudý a lichý), jejich cesty se tedy rozchází. Jelikož obyčejný motýlek je rekurzivní, tak lze na oba podmotýlky induktivně aplikovat stejný postup. Tím je zřejmé, že všechny tři permutace jsou bezkolizní.

Každá z permutací má složitost O(n). PPS má složitost O(2n) (FIXED). Celkem tedy O(5n), skrytá konstanta je 5. PPS n vstupních hodnot lze řešit na libovolné n-uzlové síti v čase T = O(diam(G)) viz Prednaska 7, slide 11. diam(oBFn) = 2n viz Prednaska 4, slide 37.

DOTAZ : v tom zminenem tvrzeni se preci pise, ze to PPS lze resit v O(log n), kde n je pocet vstupnich hodnot, u nas tedy v O(log 2^n) = n. Podminku toho, ze tvrzeni to plati mame splnenou (diam(G) = 2*n = O(log2^n) = O(n). Budu rad za objasneni, diky. (navic tam se navic predpoklada, ze pocet uzlu je stejne jako pocet hodnot)

• Monotónní permutace je jakákoli neúplná permutace, která nemění pořadí paketů. Jinak řečeno, jedná se o směrování z libovolné podmnožiny vstupů do stejně velké podmnožiny výstupů, které mohou být různě posunuté, ale musí zachovávat stejné pořadí paketů. Každou monotónní permutaci lze vytvořit složením z permutace zhušťovací a roztažné.
• Zhušťovací permutace je směrování paketů z libovolné podmnožiny x vstupů do prvních, nebo posledních x výstupů (tj. odshora, nebo odspoda), přičemž se opět zachovává relativní pořadí paketů.
• Roztažná permutace (též zředění) je zrcadlovým otočením zhušťovací permutace. Je pro ni nutné zrcadlově otočit i celého motýlka, tj. posílat pakety zprava doleva.
• Identita je směrování paketů z libovolné podmnožiny (nebo všech) vstupů do protějších výstupů. Jednoduše řečeno, pouze přenese pakety z jedné strany na druhou ve stejné řádce.

Realizace monotónní permutace na obyčejném motýlkovi má celkem čtyři fáze. Nejprve musíme spočítat relativní pořadí paketů (tj. aktivních vstupů) pomocí paralelního prefixového součtu (PPS). To je potřeba k výpočtu výstupních adres pro druhou fázi, zhušťovací permutaci. Ve třetí fázi provedeme roztažnou permutaci. Nejprve jsme pakety poslali zleva doprava, poté zpátky doleva, takže nakonec musíme provést identitu, poslat je na protější výstupu doprava.

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