Differences

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

--- users:martin.kocicka:pdp:6b [2017/06/13 10:10] – martin.kocicka
+++ users:martin.kocicka:pdp:6b [2017/06/13 10:16] (current) – martin.kocicka
@@ Line 237: / Line 237: @@
 ====== Teorie a důkazy ======
-===== Dokažte, že e-cube směrování v Qn při zhuštění je bezkolizní =====
-★ //Bylo ve zkoušce: [[.:par_zkouska_2013-01-09|2013-01-09]]//
-==== Řešení ====
-//viz skripta {{:škola:předměty:x36par-skriptacz2.pdf|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 :
-  - "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
-  - "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í.
-===== Dokažte, že neúplná online permutace zhuštění na indBFn je bezkolizní =====
-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: [[.:par_zkouska_2016-01-15|2016-01-15]]//
-==== Řešení ====
-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
-{{ :škola:předměty:mi-par:výstřižek.png |}}
-V podstatě stejné jako [[škola:předměty:mi-par:par_řešené_příklady_4b#doka%C5%BEte_%C5%BEe_e-cube_sm%C4%9Brov%C3%A1n%C3%AD_v_qn_p%C5%99i_zhu%C5%A1t%C4%9Bn%C3%AD_je_bezkolizn%C3%AD|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ě.
-===== Důkaz bezkoliznosti operace přeložení na Qn při použití e-cube =====
-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šení ====
-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ě
-^ <math>x_k</math> ^ <math>w_k</math> ^ <math>x_k \oplus w_k</math> ^
-|0|0|0|
-|0|1|1|
-|1|0|1|
-|1|1|0|
-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:
-^ <math>x_k</math> ^ <math>w_k</math> ^ <math>x_k \oplus w_k</math> ^
-^0|**0**^0|
-^1|**0**^1|
-Je li w=0, pak k-tý bit adresy paketu zůstává nezměněn, ke směrování nedochází = žádná kolize
-^ <math>x_k</math> ^ <math>w_k</math> ^ <math>x_k \oplus w_k</math> ^
-^0|**1**^1|
-^1|**1**^0|
-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.
-===== Minimální směrování pro nepřímý oBFn =====
-Dokažte, že minimální směřování pro nepřímý oBF<sub>n</sub> 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: [[.:par_zkouska_2011-05-19|2011-05-19]]//
-==== Řešení ====
-[[https://edux.fit.cvut.cz/courses/MI-PAR.2/_media/lectures/mi-par2015-prednaska9-permutations.pdf|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í:
-  - 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
-  - jelikož výstupy ze stupně 0 jdou na vstupy disjunktních podmotýlků, dá se 1) aplikovat znovu.
-{{https://i.imgur.com/TP2Hz9D.png?850|}}
-(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>.
 ===== Konstrukce všech uzlově disjunktních cest v 3D mřížce s nejkratšími délkami =====
@@ Line 421: / Line 306: @@
 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)
-===== SF,oBFn monotonni permutace =====
-//Řešení obdobného příkladu: [[škola:předměty:mi-par:par_řešené_příklady_8b#důkaz_proveditelnosti_bezkolizní_monotonní_permutace_na_obf_algoritmus_složitost|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
-==== Řešení ====
-:!://Viz skripta [2006] str. 161-162// && [2015] 9. přednáška / slide 33
-=== Důkaz bezkoliznosti ===
-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:
-  - 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.
-  - 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<sub>n-1</sub> (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í.
-=== Časová složitost ===
-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)
-=== Trocha teorie ===
-  * 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.
-{{tag>škola zkoušky s_řešením}}