From 8d2a42401e1f2d65d659f649f4d84e0b6ff31703 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Fri, 18 Nov 2011 19:04:34 +0100 Subject: [PATCH] Oziveni hradlovych siti a bitonickeho trideni, zatim bez uprav --- .../1_9_deleni_bloku.eps | 0 .../5-addsort.tex => 5-hradla/5-hradla.tex | 270 +++++++++--------- {old/4-hradla => 5-hradla}/Makefile | 2 +- {old/5-addsort => 5-hradla}/blok_scitani.eps | 0 {old/5-addsort => 5-hradla}/blok_scitani.svg | 0 {old/5-addsort => 5-hradla}/bloky_1bit.eps | 0 {old/5-addsort => 5-hradla}/bloky_1bit.svg | 0 {old/4-hradla => 5-hradla}/chytry_or.eps | 0 {old/4-hradla => 5-hradla}/chytry_or.svg | 0 {old/5-addsort => 5-hradla}/deleni_bloku.eps | 0 .../5-addsort => 5-hradla}/hloupe_scitani.eps | 0 .../5-addsort => 5-hradla}/hloupe_scitani.svg | 0 {old/4-hradla => 5-hradla}/hloupy_or.eps | 0 {old/4-hradla => 5-hradla}/hloupy_or.svg | 0 {old/4-hradla => 5-hradla}/hradlo_and.eps | 0 {old/4-hradla => 5-hradla}/hradlo_and.svg | 0 .../4-hradla => 5-hradla}/hradlo_ternbior.eps | 0 .../4-hradla => 5-hradla}/hradlo_ternbior.svg | 0 {old/4-hradla => 5-hradla}/hradlo_ternor.eps | 0 {old/4-hradla => 5-hradla}/hradlo_ternor.svg | 0 {old/4-hradla => 5-hradla}/hradlova_sit.eps | 0 {old/4-hradla => 5-hradla}/hradlova_sit.svg | 0 {old/5-addsort => 5-hradla}/obvod.eps | 0 {old/5-addsort => 5-hradla}/obvod.svg | 0 {old/5-addsort => 5-hradla}/obvod_real.eps | 0 {old/5-addsort => 5-hradla}/obvod_real.svg | 0 .../5-addsort => 5-hradla}/skolni_scitani.eps | 0 .../5-addsort => 5-hradla}/skolni_scitani.svg | 0 {old/5-addsort => 5-hradla}/sl_stromecek.eps | 0 {old/5-addsort => 5-hradla}/sl_stromecek.svg | 0 {old/5-addsort => 5-hradla}/stromecek.eps | 0 {old/5-addsort => 5-hradla}/stromecek.svg | 0 .../tabulka_skladani_bloku.eps | 0 .../tabulka_skladani_bloku.svg | 0 {old/4-hradla => 5-hradla}/vypocet_site.eps | 0 {old/4-hradla => 5-hradla}/vypocet_site.svg | 0 6-bitonic/6-bitonic.tex | 130 +++++++++ {old/5-addsort => 6-bitonic}/Makefile | 2 +- {old/5-addsort => 6-bitonic}/sortnet.0 | 0 {old/5-addsort => 6-bitonic}/sortnet.1 | 0 {old/5-addsort => 6-bitonic}/sortnet.2 | 0 {old/5-addsort => 6-bitonic}/sortnet.3 | 0 {old/5-addsort => 6-bitonic}/sortnet.4 | 0 {old/5-addsort => 6-bitonic}/sortnet.5 | 0 {old/5-addsort => 6-bitonic}/sortnet.6 | 0 {old/5-addsort => 6-bitonic}/sortnet.7 | 0 {old/5-addsort => 6-bitonic}/sortnet.mp | 0 {old/5-addsort => 6-bitonic}/sortnet.mpx | 0 old/4-hradla/4-hradla.tex | 139 --------- 49 files changed, 270 insertions(+), 273 deletions(-) rename {old/5-addsort => 5-hradla}/1_9_deleni_bloku.eps (100%) rename old/5-addsort/5-addsort.tex => 5-hradla/5-hradla.tex (51%) rename {old/4-hradla => 5-hradla}/Makefile (66%) rename {old/5-addsort => 5-hradla}/blok_scitani.eps (100%) rename {old/5-addsort => 5-hradla}/blok_scitani.svg (100%) rename {old/5-addsort => 5-hradla}/bloky_1bit.eps (100%) rename {old/5-addsort => 5-hradla}/bloky_1bit.svg (100%) rename {old/4-hradla => 5-hradla}/chytry_or.eps (100%) rename {old/4-hradla => 5-hradla}/chytry_or.svg (100%) rename {old/5-addsort => 5-hradla}/deleni_bloku.eps (100%) rename {old/5-addsort => 5-hradla}/hloupe_scitani.eps (100%) rename {old/5-addsort => 5-hradla}/hloupe_scitani.svg (100%) rename {old/4-hradla => 5-hradla}/hloupy_or.eps (100%) rename {old/4-hradla => 5-hradla}/hloupy_or.svg (100%) rename {old/4-hradla => 5-hradla}/hradlo_and.eps (100%) rename {old/4-hradla => 5-hradla}/hradlo_and.svg (100%) rename {old/4-hradla => 5-hradla}/hradlo_ternbior.eps (100%) rename {old/4-hradla => 5-hradla}/hradlo_ternbior.svg (100%) rename {old/4-hradla => 5-hradla}/hradlo_ternor.eps (100%) rename {old/4-hradla => 5-hradla}/hradlo_ternor.svg (100%) rename {old/4-hradla => 5-hradla}/hradlova_sit.eps (100%) rename {old/4-hradla => 5-hradla}/hradlova_sit.svg (100%) rename {old/5-addsort => 5-hradla}/obvod.eps (100%) rename {old/5-addsort => 5-hradla}/obvod.svg (100%) rename {old/5-addsort => 5-hradla}/obvod_real.eps (100%) rename {old/5-addsort => 5-hradla}/obvod_real.svg (100%) rename {old/5-addsort => 5-hradla}/skolni_scitani.eps (100%) rename {old/5-addsort => 5-hradla}/skolni_scitani.svg (100%) rename {old/5-addsort => 5-hradla}/sl_stromecek.eps (100%) rename {old/5-addsort => 5-hradla}/sl_stromecek.svg (100%) rename {old/5-addsort => 5-hradla}/stromecek.eps (100%) rename {old/5-addsort => 5-hradla}/stromecek.svg (100%) rename {old/5-addsort => 5-hradla}/tabulka_skladani_bloku.eps (100%) rename {old/5-addsort => 5-hradla}/tabulka_skladani_bloku.svg (100%) rename {old/4-hradla => 5-hradla}/vypocet_site.eps (100%) rename {old/4-hradla => 5-hradla}/vypocet_site.svg (100%) create mode 100644 6-bitonic/6-bitonic.tex rename {old/5-addsort => 6-bitonic}/Makefile (64%) rename {old/5-addsort => 6-bitonic}/sortnet.0 (100%) rename {old/5-addsort => 6-bitonic}/sortnet.1 (100%) rename {old/5-addsort => 6-bitonic}/sortnet.2 (100%) rename {old/5-addsort => 6-bitonic}/sortnet.3 (100%) rename {old/5-addsort => 6-bitonic}/sortnet.4 (100%) rename {old/5-addsort => 6-bitonic}/sortnet.5 (100%) rename {old/5-addsort => 6-bitonic}/sortnet.6 (100%) rename {old/5-addsort => 6-bitonic}/sortnet.7 (100%) rename {old/5-addsort => 6-bitonic}/sortnet.mp (100%) rename {old/5-addsort => 6-bitonic}/sortnet.mpx (100%) delete mode 100644 old/4-hradla/4-hradla.tex diff --git a/old/5-addsort/1_9_deleni_bloku.eps b/5-hradla/1_9_deleni_bloku.eps similarity index 100% rename from old/5-addsort/1_9_deleni_bloku.eps rename to 5-hradla/1_9_deleni_bloku.eps diff --git a/old/5-addsort/5-addsort.tex b/5-hradla/5-hradla.tex similarity index 51% rename from old/5-addsort/5-addsort.tex rename to 5-hradla/5-hradla.tex index 36b35cc..f995d4f 100644 --- a/old/5-addsort/5-addsort.tex +++ b/5-hradla/5-hradla.tex @@ -1,6 +1,140 @@ \input ../lecnotes.tex -\prednaska{5}{Paralelní sèítání, bitonické tøídìní}{(zapsal: Petr Jankovský)} +\prednaska{5}{Hradlové sítì}{} + +\def\land{\mathbin{\&}} + +Výkon poèítaèù nelze zvy¹ovat donekoneèna a pøesto¾e ji¾ pìkných pár let platí, +¾e se jejich rychlost s~èasem exponenciálnì zvìt¹uje, jednou urèitì narazíme +pøinejmen¹ím na~fyzikální limity. + +Kdy¾ tedy nemù¾eme zvy¹ovat rychlost jednoho procesoru, jak poèítat rychleji? +Øe¹ením by mohlo být poøídit si procesorù víc. U¾~dnes na~bì¾ném PéCéèku máme +k~dispozici vícejádrové procesory, díky nim¾ mù¾eme vyu¾ít pararelní poèítání +a úlohu øe¹it tak, ¾e práci ¹ikovnì rozdìlíme mezi procesory (èi jádra) a +zamìstnáme je pøi~výpoètu v¹echny. + +My se podíváme na~abstraktní výpoèetní model, který je je¹tì paralelnìj¹í. +Techniky, které si uká¾eme na~tomto modelu, se v¹ak dají pøekvapivì vyu¾ít i~pøi~reálném +paralelizování na~nìkolika málo procesorech. Konec koncù i proto, ¾e vnitøní +architektura procesoru se na¹emu modelu velmi podobá. Budeme se zabývat +jednoduchým modelem paralelního poèítaèe, toti¾ hradlovou sítí. + +\h{Hradlové sítì} + +\s{Definice:} {\I Hradlo} je prvek, který umí vyhodnocovat nìjakou funkci +nad~koneènou abecedou $\Sigma$. + +Obecnì se na~hradlo díváme jako na~funkci $f: {\Sigma}^{k} \rightarrow \Sigma$, která dostane $k$ vstupù +a~vrátí jeden výstup, pøièem¾ hodnoty, nad~kterými pracuje, budou z~nìjaké koneèné +abecedy -- tedy z~nìjaké koneèné mno¾iny symbolù $\Sigma$. Písmenku $k$ zde øíkáme {\I arita +hradla}. + +\s{Pøíklad:} Èasto studujeme hradla booleovská (pracující nad abecedou $\{0,1\}$), která poèítají logické funkce. + +Z~nich nejèastìji potkáme: + +\itemize\ibull +\:nulární: to jsou konstanty (FALSE=0, TRUE=1), +\:unární: napø. negace (znaèíme~$\lnot$), +\:binární: logický souèin ({\csc and},~$\land$), souèet ({\csc or},~$\lor$), ... +\endlist + +\>Hradla kreslíme tøeba následovnì: + +\figure{hradlo_and.eps}{Binární hradlo provádící logickou operaci {\csc and}.}{1in} + +Jednotlivá hradla mù¾eme navzájem urèitým zpùsobem propojovat a vytváøet +z nich {\I hradlové sítì}. Pokud pou¾íváme pouze booleovská hradla, øíkáme takto vytvoøeným +sítím {\I booleovské obvody}. Pokud pracujeme s~operacemi nad nìjakou obecnìj¹í (ale koneènou) +mno¾inou symbolù (abecedou), nazývají se {\I kombinaèní obvody.} + +Ka¾dá hradlová sí» má nìjaké vstupy, nìjaké výstupy a uvnitø jsou propojovaná +hradla. Ka¾dý vstup hradla je pøipojen buïto na~nìkterý ze~vstupù sítì nebo +na~výstup jiného hradla. Výstupy hradel mohou být propojeny na~vstupy dal¹ích +hradel (mohou se vìtvit), nebo na výstupy sítì. Pøitom máme zakázáno vytváøet +cykly. + +Ne¾ si øekneme formální definici, podívejme se na obrázek. + +\figure{hradlova_sit.eps}{Hradlová sí» -- tøívstupová verze funkce {\I majorita}.}{3in} + +Obrazek znázoròuje hradlovou sí», která poèítá, zda je alespoò na~dvou ze~vstupù +jednièka. Pojïme si ale {\I hradlovou sí»} definovat formálnì. + +\s{Definice:} {\I Hradlová sí»} je urèena: +\itemize\ibull +\:{\I abecedou} $\Sigma$ (to je nìjaká koneèná mno¾ina symbolù, obvykle $\Sigma=\{0,1\}$); +\:po dvou disjunktními koneènými mno¾inami $I$~({\I vstupy}), $O$~({\I výstupy}) \hfil\break a~$H$~({\I hradla}); +\:acyklickým orientovaným multigrafem~$(V,E)$, kde~$V = I \cup O \cup H$; +\:zobrazením~$F$, které ka¾dému hradlu $h\in H$ pøiøadí nìjakou funkci~$F(h): + \Sigma^{a(h)} \rightarrow \Sigma$, co¾ je funkce, kterou toto hradlo vykonává. + Èíslu $a(h)$ øíkáme {\I arita} hradla~$h$; +\:zobrazením~$z: E \rightarrow {\bb N}$, které ka¾dé hranì vedoucí do~nìjakého + hradla pøiøazuje nìkterý ze vstupù tohoto hradla. +\endlist + +\>Pøitom jsou splnìny následující podmínky: + +\itemize\ibull +\:$\forall i \in I: \deg^{in}(i)=0$ (do~vstupù nic nevede); +\:$\forall o \in O: \deg^{in}(o)=1~\land~\deg^{out}(o)=0$ (z~výstupù nic nevede a do~ka¾dého vede právì jedna hrana); +\:$\forall h \in H: \deg^{in}(v)=a(v)$ (do~ka¾dého hradla vede tolik hran, kolik je jeho arita); +\:$\forall h \in H~\forall j: 1\le j\le a(h)$ existuje právì jedena hrana~$e$ taková, ¾e~$e$ konèí v~$h$ a~$z(e)=j$, + (v¹echny vstupy hradel jsou zapojeny). +\endlist + +\s{Pozorování:} Kdybychom pøipustili hradla s~libovolnì vysokým poètem vstupù, mohli +bychom libovolný problém se vstupem délky~$n$ vyøe¹it jedním hradlem o~$n$~vstupech, +kterému bychom pøiøadili funkci, která by na¹i úlohu rovnou vyøe¹ila. Tento model +v¹ak není ani realistický, ani pìkný. Proto pøijmìme omezení, ¾e~arity v¹ech hradel +budou omezeny nìjakou pevnou konstantou $k$ (uká¾e se, ¾e nám bude staèit dvojka +a~vystaèíme si tedy pouze s nulárními, unárními a binárními hradly). +Následující obrázky ukazují, jak hradla o~více vstupech nahradit dvouvstupovými: + +\twofigures{hradlo_ternor.eps}{Trojvstupové hradlo \csc or.}{0.5in}{hradlo_ternbior.eps}{Jeho nahrazení 2-vstupovými hradly.}{0.6in} + + +Nyní bychom je¹tì mìli definovat, co taková hradlová sí» vlastnì poèítá a~jak +její výpoèet probíhá. + +\s{Definice:} {\I Výpoèet sítì} probíhá po~{\I taktech.} V nultém taktu jsou definovány pouze +hodnoty na~vstupech sítì a na~výstupech hradel arity 0. Mù¾eme si to pøedstavit +tak, ¾e na~zaèátku nemá ¾ádné hradlo definovánu výstupní hodnotu (a¾ na ji¾ +zmínìná hradla nulární). V~ka¾dém dal¹ím taktu pak vydají výstup hradla, která +na~konci minulého taktu mìla definovány v¹echny hodnoty na vstupech. Jakmile +budou po~nìjakém koneèném poètu taktù definované i hodnoty v¹ech výstupù, sí» +se zastaví a~vydá výsledek. + +\s{Pozorování:} Proto¾e je sí» acyklická, je jasné, ¾e jakmile jednou nìjaké hradlo vydá +výstup, tak se tento výstup bìhem dal¹ího výpoètu sítì ji¾ nezmìní. + +\figure{vypocet_site.eps}{Výpoèet hradlové sítì.}{6cm} + +\>Podle toho, jak sí» poèítá, si ji mù¾eme rozdìlit na~vrstvy: + +\s{Definice:} {\I $i$-tá vrstva $S_i$} obsahuje právì takové vrcholy~$v$, pro~které nejdel¹í cesta ze~vstupù +sítì do $v$ má délku rovnou~$i$. + +\s{Pozorování:} V¹imnìme si, ¾e v $i$-tém taktu vydají hodnoty právì hradla z $S_i$. + +Dává tedy smysl prohlásit za~{\I èasovou slo¾itost} sítì poèet +jejích vrstev. Podobnì {\I prostorovou slo¾itost} definujeme jako poèet hradel v~síti. + +\s{Pøíklad:} Sestrojme sí», která zjistí, zda se mezi jejími~$n$ vstupy +vyskytuje alespoò jedna jednièka. + +\>{\I První øe¹ení:} zapojíme hradla za~sebe (sériovì). Èasová i prostorová +slo¾itost odpovídají~$\Theta(n)$. Zde ov¹em vùbec nevyu¾íváme toho, ¾e by mohlo poèítat více +hradel souèasnì. + +\figure{hloupy_or.eps}{Hradlová sí», která zjistí, zdali je na vstupu alespoò jedna jednièka.}{0.7in} + +\>{\I Druhé øe¹ení:} Hradla budeme spojovat do~dvojic, pak výsledky z~tìchto dvojic opìt +do~dvojic a tak dále. Díky paralelnímu zapojení dosáhneme èasové slo¾itosti $\Theta(\log n)$, +prostorová slo¾itost zùstane lineární. + +\figure{chytry_or.eps}{Chytøej¹í øe¹ení stejného problému pro vstup velikosti 16.}{3in} Minule jsme si zavedli paralelní výpoèetní model, ve kterém si nyní nìco naprogramujeme \dots @@ -18,7 +152,7 @@ bychom to mohli zapsat t $$ z_i=x_i \oplus y_i \oplus c_i, $$ -kde $z_i$ je $i$-tá èíslice souètu, $\oplus$ znaèí operaci {\sc xor} (souèet modulo~2) a~$c_i$ je {\I pøenos} +kde $z_i$ je $i$-tá èíslice souètu, $\oplus$ znaèí operaci {\csc xor} (souèet modulo~2) a~$c_i$ je {\I pøenos} z~$(i-1)$-ního øádu do~$i$-tého. Pøenos pøitom nastane tehdy, pokud se~nám potkají dvì jednièky pod~sebou, nebo kdy¾ se~vyskytne alespoò jedna jednièka a~k~tomu pøenos z~ni¾¹ího øádu. Jinými slovy tehdy, kdy¾ ze~tøí xorovaných èíslic jsou alespoò @@ -147,139 +281,11 @@ Algoritmus pracuje v~ hladinách kroku~2 poèet hradel exponenciálnì klesá od~$n$ k~1, na~hladinách kroku~5 exponenciálnì stoupá od~1 k~$n$, tak¾e dohromady se seète na~$\Theta(n)$. -\h{Tøídìní} - -Nyní se podíváme na~druhý problém, a~to na~problém tøídìní. Ji¾ známe pomìrnì efektivní sekvenèní algoritmy, které dovedou tøídit v~èase $\O(n\log n)$. Byli bychom jistì rádi, kdybychom to zvládli je¹tì rychleji. Pojïme se podívat, zda by nám v tom nepomohlo problém paralelizovat. - -Budeme pøi tom pracovat ve~výpoèetním modelu, kterému se øíká komparátorová sí». Ta je postavená z~hradel, kterým se øíká komparátory. - -\s{Definice:} {\I Komparátorová sí»} je kombinaèní obvod, jeho¾ hradla jsou -komparátory. - -\figure{sortnet.0}{Komparátor}{0.7in} - -Komparátor umí porovnat dvì hodnoty a~rozhodnout, která z~nich je vìt¹í -a~která men¹í. Nevrací v¹ak booleovský výsledek jako bì¾né hradlo, ale má dva -výstupy, pøièem¾ na~jednom vrátí men¹í ze~vstupních hodnot a~na~druhém vìt¹í. - -Výstupy komparátorù se nevìtví. Nemù¾eme tedy jeden výstup \uv{rozdvojit} a~pøipojit ho na~dva vstupy. (Vìtvení by dokonce ani nemìlo smysl, proto¾e zatímco rozdvojit bychom mohli, slouèit u¾~ne. Pokud tedy chceme, aby sí» mìla $n$~vstupù i~$n$~výstupù, rozdvojení stejnì nesmíme provést, i kdybychom jej mìli povolené.) - -\s{Pøíklad:} {\sl Bubble sort} - -Obrázek Bubble 1 ilustruje pou¾ití komparátorù pro tøídìní Bubble sortem. -©ipky pøedstavují jednotlivé komparátory. Výpoèet v¹ak je¹tì mù¾eme vylep¹it. - -\twofigures{sortnet.1}{Bubble 1}{143pt}{sortnet.2}{Bubble 2}{143pt} - -Sna¾íme se výpoèet co nejvíce paralelizovat (viz obrázek Bubble 2). -Jak je vidìt, komparátory na sebe nemusejí èekat. Tím mù¾eme výpoèet urychlit a místo èasu $\Theta{(n^2)}$ docílit èasové slo¾itosti $\Theta{(n)}$. V obou pøípadech je zachován kvadratický prostor. - -Nyní si uká¾eme je¹tì rychlej¹í tøídící algoritmus. Pùjdeme na nìj v¹ak trochu \uv{od lesa}. Nejdøíve vymyslíme sí», která bude umìt tøídit jenom nìco -- toti¾ bitonické posloupnosti. Bez újmy na obecnosti budeme pøedpokládat, ¾e ka¾dé dva prvky na vstupu jsou navzájem rùzné. - -\medskip -\s{Definice:} Øekneme, ¾e posloupnost $x_0,\dots,x_{n-1} $ je {\I èistì bitonická} právì tehdy, kdy¾ -pro nìjaké $x_k, k\in\{0, \dots, n-1\} $ platí, ¾e~v¹echny prvky pøed ním (vèetnì jeho samotného) -tvoøí rostoucí poslopnost, kde¾to prvky stojící za~ním tvoøí poslopnost klesající. -Formálnì zapsáno musí platit, ¾e: -$$x_0\leq x_1\leq \dots \leq x_k \geq x_{k+1}\geq\dots \geq x_{n-1}.$$ - -\s{Definice:} Posloupnost $x_0 \dots x_{n-1}$ je {\I bitonická}, právì kdy¾ $\exists~j\in \{0,\dots ,n-1\}$, pro -které je rotace pùvodní posloupnosti o $j$ prvkù, tedy posloupnost -$$x_j,x_{(j+1) \bmod n},\dots, x_{(j+n-1) \bmod n},$$ èistì bitonická. - -\s{Definice:} {\I Separátor $S_n$} je sí», ve které jsou v¾dy~$i$-tý a~$(i+{n/2})$-tý prvek vstupu -(pro $i=0,\dots, {n/2}-1$) propojeny komparátorem. Minimum se pak stane~$i$-tým, -maximum $(i+{n/2})$-tým prvkem výstupu. -\figure{sortnet.3}{$(y_i, y_{i+{n/2}}) = \(x_i, x_{i+{n/2}})$} {300pt} - -\s{Lemma:} Pokud separátor dostane na~vstupu bitonickou posloupnost, pak jeho výstup $y_0, \dots, y_{n-1}$ -splòuje: - -(i) $y_0,\dots, y_{n/2 -1}$ a~$y_{n/2},\dots, y_{n-1}$ jsou -bitonické posloupnosti, - -(ii) Pro v¹echna $i,j< {n/2}$ platí $y_i < y_{j + {n/2}}$. - -Separátor nám tedy jednu bitonickou posloupnost na~vstupu rozdìlí na~dvì -bitonické posloupnosti, pøièem¾ navíc ka¾dý prvek první posloupnosti ($y_0,\dots, y_{n/2 -1}$) -je men¹í nebo roven prvkùm druhé posloupnosti ($y_{n/2}, \dots, y_{n-1}$). - -\>Ne¾ pøistoupíme k dùkazu lemmatu, uka¾me si, k èemu se nám bude hodit. - - -\s{Definice:} {\I Bitonická tøídièka $B_n$} je obvod sestavený ze separátorù, který dostane-li na vstupu bitonickou posloupnost délky $n$ (BÚNO konstruujeme tøídièku pro $n=2^k$), vydá setøídìnou zadanou posloupnost délky $n$. - -Tøídièka dostane na~vstupu bitonickou posloupnost. Separátor~$S_n$ ji pak dle lemmatu rozdìlí na~dvì bitonické posloupnosti, kdy je ka¾dý prvek z~první posloupnosti men¹í ne¾ libovolný prvek z~druhé. Tyto poloviny pak dal¹í separátory rozdìlí na~ètvrtiny, ..., a¾~na~konci zbudou pouze jednoduché posloupnosti délky jedna (zjevnì setøídìné), které mezi sebou mají po¾adovanou nerovnost -- tedy ka¾dá posloupnost (nebo spí¹e prvek) nalevo je $\leq$ ne¾ prvek napravo od~nìj. - -\centerline{\epsfbox{sortnet.5}} - -Jak je vidìt, bitonická tøídièka nám libovolnou bitonickou posloupnost délky~$n$ -setøídí na~$\Theta(\log n)$ hladin. - -Nyní se dá odvodit, ¾e pokud umíme tøídit bitonické posloupnosti, umíme setøídit v¹echno. -Vzpomeòme si na~tøídìní sléváním -- Merge sort. To funguje tak, ¾e zaène s~jednoprvkovými posloupnostmi, které jsou evidentnì setøídìné, a~poté v¾dy dvì setøídìné posloupnosti slévá do~jedné. Kdybychom nyní umìli paralelnì slévat, mohli bychom vytvoøit i~paralelní Merge sort. Jinými slovy, potøebujeme dvì rostoucí posloupnosti nìjak efektivnì slít do~jedné setøídìné. Uvìdomme si, ¾e to zvládneme jednodu¹e -- staèí druhou z~posloupností obrátit a~\uv{pøilepit} za~první, èím¾ vznikne bitonická posloupnost, kterou poté mù¾eme setøídit na¹í bitonickou tøídièkou. - -\s{Pøíklad:} {\sl Merge sort} - -Bitonická tøídièka se tedy dá pou¾ít ke~slévání setøídìných posloupností. -Uka¾me si, jak s~její pomocí sestavíme souèástky {\I slévaèky} $M_n$: - -Setøídìné posloupnosti $x_0,\dots, x_{n-1}$ a~$y_0,\dots, y_{n-1}$ spojíme do jedné bitonické -posloupnosti $x_0,\dots, x_{n-1},y_{n-1},\dots, y_0$. Z~této posloupnosti vytvoøíme pomocí bitonické tøídièky -$B_{2n}$ setøídìnou posloupnost. Vytvoøíme tedy blok $M_{2n}$, který se ov¹em sestává de~facto pouze z~bloku $B_{2n}$, jeho¾ druhá polovina vstupù je zapojena v~obráceném poøadí. -\figure{sortnet.6}{Paralelní MergeSort.}{3in} - -Nyní se pokusme odhadnout èasovou slo¾itost. Ná¹ MergeSort bude mít øádovì hloubku blokù $\log n$. -V ka¾dém bloku $M_n$ je navíc ukryta bitonická tøídièka s takté¾ logaritmickou hloubkou. -Celková hloubka tedy bude $\log 2 + \log4 + \dots + \log 2^k + \dots + \log n$. -Po seètení nakonec dostáváme výslednou èasovou slo¾itost $\Theta (\log^2 n)$. - -Dodejme je¹tì, ¾e existuje i~tøídicí algoritmus, kterému staèí jen ${\O}(\log n)$ hladin. -Jeho multiplikativní konstanta je v¹ak pøíli¹ veliká, tak¾e je v~praxi nepou¾itelný. - -Vra»me se nyní k dùkazu lemmatu, který jsme na pøedminulé stránce vynechali. - -\h{Dùkaz Lemmatu:} -(i) Nejprve nahlédneme, ¾e lemma platí, je-li vstupem èistì bitonická -posloupnost. Dále BÚNO pøedpokládejme, ¾e vrchol posloupnosti je v~první polovinì (kdyby -byl vrchol za~polovinou, staèilo by zrcadlovì obrátit posloupnost i~komparátory a~øe¹ili -bychom stejný problém). Nyní si definujme $k := \min j: x_j > x_{j+n/2}$. (Pokud -by~takové~$k$ neexistovalo, znamenalo by~to, ¾e vstupní posloupnost je monotónní. -Separátor by tedy nic nedìlal a~pouze zkopíroval vstup na~výstup, co¾ jistì lemma splòuje.) Nyní si v¹imìme, -¾e jakmile jednou zaène platit, ¾e prvek na~levé stranì je men¹í ne¾ na~pravé, bude -nám tato relace platit a¾~do~konce. Oznaème vrchol vstupní posloupnosti jako~$x_m$. -Pak~$k$ bude jistì men¹í ne¾~$m$ a~$k+{n/2}$ bude vìt¹í ne¾~$m$. Mezi~$k$ a~$m$ je tedy -vstupní posloupnost neklesající, mezi $k+{n/2}$ a~$n-1$ nerostoucí. - -Do pozice~$k$ tedy separátor bude pouze kopírovat vstup na~výstup, od~pozice~$k$ -dál u¾~jen prohazuje. Pro ka¾dé~$i$, $(k\leq i\leq {n/2}-1)$ se prvky -$x_i$ a~$x_{i+{n/2}}$ prohodí. Úsek mezi~$k$ a~${n/2}-1$ tedy -nahradíme nerostoucí posloupností, první polovina výstupu tedy bude -(dokonce èistì) bitonická. Podobnì úsek $k+{n/2}$ a¾~$n-1$ nahradíme èistì -bitonickou posloupností. Obì poloviny tedy budou bitonické. - -Dostaneme-li na vstupu obecnou bitonickou posloupnost, pøedstavíme si, -¾e je to èistì bitonická posloupnost zrotovaná o~$r$ prvkù (BÚNO -doprava). Zjistíme, ¾e v~komparátorech se porovnávají tyté¾ prvky, -jako kdyby zrotovaná nebyla. Výstup se od výstupu èistì bitonické -posloupnosti zrotovaného o~$r$ bude li¹it prohozením úsekù $x_0$ a¾ -$x_{r-1}$ a~$x_{n/2}$ a¾ $x_{{n/2}+r-1}$. Obì výstupní -posloupnosti tedy budou zrotované o~$r$ prvkù, ale na jejich -bitoniènosti se nic nezmìní. - -(ii) Z dùkazu (i) pro èistì bitonickou posloupnost víme, ¾e $y_0\dots y_{n/2-1}$ je èistì bitonická a bude rovna $x_0\dots x_{k-1},x_{k+n/2}\dots x_{n-1}$ pro vhodné $k$ a navíc bude mít maximum v $x_{k-1}$ nebo $x_k+{n/2}$. Mezi tìmito body ov¹em ve vstupní posloupnosti urèitì nele¾el ¾ádný $x_i$ men¹í ne¾ $x_k-1$ nebo $x_k+{n/2}$ (jak je vidìt z obrázku) a posloupnost $x_k \dots x_{k-1+{n/2}}$ je rovna $y_{n/2}\dots y_{n-1}$. Pro obecné bitonické posloupnosti uká¾eme stejnì jako v (i). -\qed - -\medskip - -\centerline{\epsfbox{sortnet.7}} - - \h{Paralelní násobení} Podobnì jako u~sèítání si vzpomeneme na~¹kolní algoritmus -- tentokráte v¹ak pro násobení. To fungovalo tak, ¾e~jsme si jedno ze~dvou binárních èísel na~vstupu (øíkejme mu tøeba $x$) $n$-krát posouvali. Tam kde pak byly v~èísle~$y$ jednièky, pøíslu¹né kopie $x$ jsme seèetli. Jinými slovy tedy násobení umíme pøevést na~nìjaké posuny (ty lze realizovat pouze \uv{pøedrátováním} -- nic nás nestojí), násobení jedním bitem (co¾ je -{\sc and} ) a~nakonec potøebujeme výsledných~$n$ èísel seèíst. +{\csc and} ) a~nakonec potøebujeme výsledných~$n$ èísel seèíst. \figure{skolni_scitani.eps}{©kolní sèítání.}{2in} Jak nyní seèíst $n$ $n$-bitových èísel..? Nabízí se vyu¾ít osvìdèený \uv{stromeèek} -- sèítat dvojice èísel, výsledky pak opìt po~dvojicích seèíst, a¾ na~konci vyjde jediný výsledek. @@ -307,6 +313,6 @@ Pokud jsme m Seètení v¹ech $n$ èísel tedy zabere $\Theta (\log n)$ hladin. -Kdy¾ se nyní vrátíme k~násobení, zbývá nám vyøe¹it posouvání a~{\sc and}ování. Uvìdomme si, ¾e to je plnì paralelení a~zvládneme ho za~konstantnì mnoho hladin. Celé násobení tedy zvládneme v~logaritmickém èase. +Kdy¾ se nyní vrátíme k~násobení, zbývá nám vyøe¹it posouvání a~{\csc and}ování. Uvìdomme si, ¾e to je plnì paralelení a~zvládneme ho za~konstantnì mnoho hladin. Celé násobení tedy zvládneme v~logaritmickém èase. \bye diff --git a/old/4-hradla/Makefile b/5-hradla/Makefile similarity index 66% rename from old/4-hradla/Makefile rename to 5-hradla/Makefile index 65a25ae..9d4d631 100644 --- a/old/4-hradla/Makefile +++ b/5-hradla/Makefile @@ -1,3 +1,3 @@ -P=4-hradla +P=5-hradla include ../Makerules diff --git a/old/5-addsort/blok_scitani.eps b/5-hradla/blok_scitani.eps similarity index 100% rename from old/5-addsort/blok_scitani.eps rename to 5-hradla/blok_scitani.eps diff --git a/old/5-addsort/blok_scitani.svg b/5-hradla/blok_scitani.svg similarity index 100% rename from old/5-addsort/blok_scitani.svg rename to 5-hradla/blok_scitani.svg diff --git a/old/5-addsort/bloky_1bit.eps b/5-hradla/bloky_1bit.eps similarity index 100% rename from old/5-addsort/bloky_1bit.eps rename to 5-hradla/bloky_1bit.eps diff --git a/old/5-addsort/bloky_1bit.svg b/5-hradla/bloky_1bit.svg similarity index 100% rename from old/5-addsort/bloky_1bit.svg rename to 5-hradla/bloky_1bit.svg diff --git a/old/4-hradla/chytry_or.eps b/5-hradla/chytry_or.eps similarity index 100% rename from old/4-hradla/chytry_or.eps rename to 5-hradla/chytry_or.eps diff --git a/old/4-hradla/chytry_or.svg b/5-hradla/chytry_or.svg similarity index 100% rename from old/4-hradla/chytry_or.svg rename to 5-hradla/chytry_or.svg diff --git a/old/5-addsort/deleni_bloku.eps b/5-hradla/deleni_bloku.eps similarity index 100% rename from old/5-addsort/deleni_bloku.eps rename to 5-hradla/deleni_bloku.eps diff --git a/old/5-addsort/hloupe_scitani.eps b/5-hradla/hloupe_scitani.eps similarity index 100% rename from old/5-addsort/hloupe_scitani.eps rename to 5-hradla/hloupe_scitani.eps diff --git a/old/5-addsort/hloupe_scitani.svg b/5-hradla/hloupe_scitani.svg similarity index 100% rename from old/5-addsort/hloupe_scitani.svg rename to 5-hradla/hloupe_scitani.svg diff --git a/old/4-hradla/hloupy_or.eps b/5-hradla/hloupy_or.eps similarity index 100% rename from old/4-hradla/hloupy_or.eps rename to 5-hradla/hloupy_or.eps diff --git a/old/4-hradla/hloupy_or.svg b/5-hradla/hloupy_or.svg similarity index 100% rename from old/4-hradla/hloupy_or.svg rename to 5-hradla/hloupy_or.svg diff --git a/old/4-hradla/hradlo_and.eps b/5-hradla/hradlo_and.eps similarity index 100% rename from old/4-hradla/hradlo_and.eps rename to 5-hradla/hradlo_and.eps diff --git a/old/4-hradla/hradlo_and.svg b/5-hradla/hradlo_and.svg similarity index 100% rename from old/4-hradla/hradlo_and.svg rename to 5-hradla/hradlo_and.svg diff --git a/old/4-hradla/hradlo_ternbior.eps b/5-hradla/hradlo_ternbior.eps similarity index 100% rename from old/4-hradla/hradlo_ternbior.eps rename to 5-hradla/hradlo_ternbior.eps diff --git a/old/4-hradla/hradlo_ternbior.svg b/5-hradla/hradlo_ternbior.svg similarity index 100% rename from old/4-hradla/hradlo_ternbior.svg rename to 5-hradla/hradlo_ternbior.svg diff --git a/old/4-hradla/hradlo_ternor.eps b/5-hradla/hradlo_ternor.eps similarity index 100% rename from old/4-hradla/hradlo_ternor.eps rename to 5-hradla/hradlo_ternor.eps diff --git a/old/4-hradla/hradlo_ternor.svg b/5-hradla/hradlo_ternor.svg similarity index 100% rename from old/4-hradla/hradlo_ternor.svg rename to 5-hradla/hradlo_ternor.svg diff --git a/old/4-hradla/hradlova_sit.eps b/5-hradla/hradlova_sit.eps similarity index 100% rename from old/4-hradla/hradlova_sit.eps rename to 5-hradla/hradlova_sit.eps diff --git a/old/4-hradla/hradlova_sit.svg b/5-hradla/hradlova_sit.svg similarity index 100% rename from old/4-hradla/hradlova_sit.svg rename to 5-hradla/hradlova_sit.svg diff --git a/old/5-addsort/obvod.eps b/5-hradla/obvod.eps similarity index 100% rename from old/5-addsort/obvod.eps rename to 5-hradla/obvod.eps diff --git a/old/5-addsort/obvod.svg b/5-hradla/obvod.svg similarity index 100% rename from old/5-addsort/obvod.svg rename to 5-hradla/obvod.svg diff --git a/old/5-addsort/obvod_real.eps b/5-hradla/obvod_real.eps similarity index 100% rename from old/5-addsort/obvod_real.eps rename to 5-hradla/obvod_real.eps diff --git a/old/5-addsort/obvod_real.svg b/5-hradla/obvod_real.svg similarity index 100% rename from old/5-addsort/obvod_real.svg rename to 5-hradla/obvod_real.svg diff --git a/old/5-addsort/skolni_scitani.eps b/5-hradla/skolni_scitani.eps similarity index 100% rename from old/5-addsort/skolni_scitani.eps rename to 5-hradla/skolni_scitani.eps diff --git a/old/5-addsort/skolni_scitani.svg b/5-hradla/skolni_scitani.svg similarity index 100% rename from old/5-addsort/skolni_scitani.svg rename to 5-hradla/skolni_scitani.svg diff --git a/old/5-addsort/sl_stromecek.eps b/5-hradla/sl_stromecek.eps similarity index 100% rename from old/5-addsort/sl_stromecek.eps rename to 5-hradla/sl_stromecek.eps diff --git a/old/5-addsort/sl_stromecek.svg b/5-hradla/sl_stromecek.svg similarity index 100% rename from old/5-addsort/sl_stromecek.svg rename to 5-hradla/sl_stromecek.svg diff --git a/old/5-addsort/stromecek.eps b/5-hradla/stromecek.eps similarity index 100% rename from old/5-addsort/stromecek.eps rename to 5-hradla/stromecek.eps diff --git a/old/5-addsort/stromecek.svg b/5-hradla/stromecek.svg similarity index 100% rename from old/5-addsort/stromecek.svg rename to 5-hradla/stromecek.svg diff --git a/old/5-addsort/tabulka_skladani_bloku.eps b/5-hradla/tabulka_skladani_bloku.eps similarity index 100% rename from old/5-addsort/tabulka_skladani_bloku.eps rename to 5-hradla/tabulka_skladani_bloku.eps diff --git a/old/5-addsort/tabulka_skladani_bloku.svg b/5-hradla/tabulka_skladani_bloku.svg similarity index 100% rename from old/5-addsort/tabulka_skladani_bloku.svg rename to 5-hradla/tabulka_skladani_bloku.svg diff --git a/old/4-hradla/vypocet_site.eps b/5-hradla/vypocet_site.eps similarity index 100% rename from old/4-hradla/vypocet_site.eps rename to 5-hradla/vypocet_site.eps diff --git a/old/4-hradla/vypocet_site.svg b/5-hradla/vypocet_site.svg similarity index 100% rename from old/4-hradla/vypocet_site.svg rename to 5-hradla/vypocet_site.svg diff --git a/6-bitonic/6-bitonic.tex b/6-bitonic/6-bitonic.tex new file mode 100644 index 0000000..549e2f8 --- /dev/null +++ b/6-bitonic/6-bitonic.tex @@ -0,0 +1,130 @@ +\input ../lecnotes.tex + +\prednaska{6}{Bitonické tøídìní}{} + +Nyní se podíváme na~druhý problém, a~to na~problém tøídìní. Ji¾ známe pomìrnì efektivní sekvenèní algoritmy, které dovedou tøídit v~èase $\O(n\log n)$. Byli bychom jistì rádi, kdybychom to zvládli je¹tì rychleji. Pojïme se podívat, zda by nám v tom nepomohlo problém paralelizovat. + +Budeme pøi tom pracovat ve~výpoèetním modelu, kterému se øíká komparátorová sí». Ta je postavená z~hradel, kterým se øíká komparátory. + +\s{Definice:} {\I Komparátorová sí»} je kombinaèní obvod, jeho¾ hradla jsou +komparátory. + +\figure{sortnet.0}{Komparátor}{0.7in} + +Komparátor umí porovnat dvì hodnoty a~rozhodnout, která z~nich je vìt¹í +a~která men¹í. Nevrací v¹ak booleovský výsledek jako bì¾né hradlo, ale má dva +výstupy, pøièem¾ na~jednom vrátí men¹í ze~vstupních hodnot a~na~druhém vìt¹í. + +Výstupy komparátorù se nevìtví. Nemù¾eme tedy jeden výstup \uv{rozdvojit} a~pøipojit ho na~dva vstupy. (Vìtvení by dokonce ani nemìlo smysl, proto¾e zatímco rozdvojit bychom mohli, slouèit u¾~ne. Pokud tedy chceme, aby sí» mìla $n$~vstupù i~$n$~výstupù, rozdvojení stejnì nesmíme provést, i kdybychom jej mìli povolené.) + +\s{Pøíklad:} {\sl Bubble sort} + +Obrázek Bubble 1 ilustruje pou¾ití komparátorù pro tøídìní Bubble sortem. +©ipky pøedstavují jednotlivé komparátory. Výpoèet v¹ak je¹tì mù¾eme vylep¹it. + +\twofigures{sortnet.1}{Bubble 1}{143pt}{sortnet.2}{Bubble 2}{143pt} + +Sna¾íme se výpoèet co nejvíce paralelizovat (viz obrázek Bubble 2). +Jak je vidìt, komparátory na sebe nemusejí èekat. Tím mù¾eme výpoèet urychlit a místo èasu $\Theta{(n^2)}$ docílit èasové slo¾itosti $\Theta{(n)}$. V obou pøípadech je zachován kvadratický prostor. + +Nyní si uká¾eme je¹tì rychlej¹í tøídící algoritmus. Pùjdeme na nìj v¹ak trochu \uv{od lesa}. Nejdøíve vymyslíme sí», která bude umìt tøídit jenom nìco -- toti¾ bitonické posloupnosti. Bez újmy na obecnosti budeme pøedpokládat, ¾e ka¾dé dva prvky na vstupu jsou navzájem rùzné. + +\medskip +\s{Definice:} Øekneme, ¾e posloupnost $x_0,\dots,x_{n-1} $ je {\I èistì bitonická} právì tehdy, kdy¾ +pro nìjaké $x_k, k\in\{0, \dots, n-1\} $ platí, ¾e~v¹echny prvky pøed ním (vèetnì jeho samotného) +tvoøí rostoucí poslopnost, kde¾to prvky stojící za~ním tvoøí poslopnost klesající. +Formálnì zapsáno musí platit, ¾e: +$$x_0\leq x_1\leq \dots \leq x_k \geq x_{k+1}\geq\dots \geq x_{n-1}.$$ + +\s{Definice:} Posloupnost $x_0 \dots x_{n-1}$ je {\I bitonická}, právì kdy¾ $\exists~j\in \{0,\dots ,n-1\}$, pro +které je rotace pùvodní posloupnosti o $j$ prvkù, tedy posloupnost +$$x_j,x_{(j+1) \bmod n},\dots, x_{(j+n-1) \bmod n},$$ èistì bitonická. + +\s{Definice:} {\I Separátor $S_n$} je sí», ve které jsou v¾dy~$i$-tý a~$(i+{n/2})$-tý prvek vstupu +(pro $i=0,\dots, {n/2}-1$) propojeny komparátorem. Minimum se pak stane~$i$-tým, +maximum $(i+{n/2})$-tým prvkem výstupu. +\figure{sortnet.3}{$(y_i, y_{i+{n/2}}) = \(x_i, x_{i+{n/2}})$} {300pt} + +\s{Lemma:} Pokud separátor dostane na~vstupu bitonickou posloupnost, pak jeho výstup $y_0, \dots, y_{n-1}$ +splòuje: + +(i) $y_0,\dots, y_{n/2 -1}$ a~$y_{n/2},\dots, y_{n-1}$ jsou +bitonické posloupnosti, + +(ii) Pro v¹echna $i,j< {n/2}$ platí $y_i < y_{j + {n/2}}$. + +Separátor nám tedy jednu bitonickou posloupnost na~vstupu rozdìlí na~dvì +bitonické posloupnosti, pøièem¾ navíc ka¾dý prvek první posloupnosti ($y_0,\dots, y_{n/2 -1}$) +je men¹í nebo roven prvkùm druhé posloupnosti ($y_{n/2}, \dots, y_{n-1}$). + +\>Ne¾ pøistoupíme k dùkazu lemmatu, uka¾me si, k èemu se nám bude hodit. + + +\s{Definice:} {\I Bitonická tøídièka $B_n$} je obvod sestavený ze separátorù, který dostane-li na vstupu bitonickou posloupnost délky $n$ (BÚNO konstruujeme tøídièku pro $n=2^k$), vydá setøídìnou zadanou posloupnost délky $n$. + +Tøídièka dostane na~vstupu bitonickou posloupnost. Separátor~$S_n$ ji pak dle lemmatu rozdìlí na~dvì bitonické posloupnosti, kdy je ka¾dý prvek z~první posloupnosti men¹í ne¾ libovolný prvek z~druhé. Tyto poloviny pak dal¹í separátory rozdìlí na~ètvrtiny, ..., a¾~na~konci zbudou pouze jednoduché posloupnosti délky jedna (zjevnì setøídìné), které mezi sebou mají po¾adovanou nerovnost -- tedy ka¾dá posloupnost (nebo spí¹e prvek) nalevo je $\leq$ ne¾ prvek napravo od~nìj. + +\centerline{\epsfbox{sortnet.5}} + +Jak je vidìt, bitonická tøídièka nám libovolnou bitonickou posloupnost délky~$n$ +setøídí na~$\Theta(\log n)$ hladin. + +Nyní se dá odvodit, ¾e pokud umíme tøídit bitonické posloupnosti, umíme setøídit v¹echno. +Vzpomeòme si na~tøídìní sléváním -- Merge sort. To funguje tak, ¾e zaène s~jednoprvkovými posloupnostmi, které jsou evidentnì setøídìné, a~poté v¾dy dvì setøídìné posloupnosti slévá do~jedné. Kdybychom nyní umìli paralelnì slévat, mohli bychom vytvoøit i~paralelní Merge sort. Jinými slovy, potøebujeme dvì rostoucí posloupnosti nìjak efektivnì slít do~jedné setøídìné. Uvìdomme si, ¾e to zvládneme jednodu¹e -- staèí druhou z~posloupností obrátit a~\uv{pøilepit} za~první, èím¾ vznikne bitonická posloupnost, kterou poté mù¾eme setøídit na¹í bitonickou tøídièkou. + +\s{Pøíklad:} {\sl Merge sort} + +Bitonická tøídièka se tedy dá pou¾ít ke~slévání setøídìných posloupností. +Uka¾me si, jak s~její pomocí sestavíme souèástky {\I slévaèky} $M_n$: + +Setøídìné posloupnosti $x_0,\dots, x_{n-1}$ a~$y_0,\dots, y_{n-1}$ spojíme do jedné bitonické +posloupnosti $x_0,\dots, x_{n-1},y_{n-1},\dots, y_0$. Z~této posloupnosti vytvoøíme pomocí bitonické tøídièky +$B_{2n}$ setøídìnou posloupnost. Vytvoøíme tedy blok $M_{2n}$, který se ov¹em sestává de~facto pouze z~bloku $B_{2n}$, jeho¾ druhá polovina vstupù je zapojena v~obráceném poøadí. +\figure{sortnet.6}{Paralelní MergeSort.}{3in} + +Nyní se pokusme odhadnout èasovou slo¾itost. Ná¹ MergeSort bude mít øádovì hloubku blokù $\log n$. +V ka¾dém bloku $M_n$ je navíc ukryta bitonická tøídièka s takté¾ logaritmickou hloubkou. +Celková hloubka tedy bude $\log 2 + \log4 + \dots + \log 2^k + \dots + \log n$. +Po seètení nakonec dostáváme výslednou èasovou slo¾itost $\Theta (\log^2 n)$. + +Dodejme je¹tì, ¾e existuje i~tøídicí algoritmus, kterému staèí jen ${\O}(\log n)$ hladin. +Jeho multiplikativní konstanta je v¹ak pøíli¹ veliká, tak¾e je v~praxi nepou¾itelný. + +Vra»me se nyní k dùkazu lemmatu, který jsme na pøedminulé stránce vynechali. + +\h{Dùkaz Lemmatu:} +(i) Nejprve nahlédneme, ¾e lemma platí, je-li vstupem èistì bitonická +posloupnost. Dále BÚNO pøedpokládejme, ¾e vrchol posloupnosti je v~první polovinì (kdyby +byl vrchol za~polovinou, staèilo by zrcadlovì obrátit posloupnost i~komparátory a~øe¹ili +bychom stejný problém). Nyní si definujme $k := \min j: x_j > x_{j+n/2}$. (Pokud +by~takové~$k$ neexistovalo, znamenalo by~to, ¾e vstupní posloupnost je monotónní. +Separátor by tedy nic nedìlal a~pouze zkopíroval vstup na~výstup, co¾ jistì lemma splòuje.) Nyní si v¹imìme, +¾e jakmile jednou zaène platit, ¾e prvek na~levé stranì je men¹í ne¾ na~pravé, bude +nám tato relace platit a¾~do~konce. Oznaème vrchol vstupní posloupnosti jako~$x_m$. +Pak~$k$ bude jistì men¹í ne¾~$m$ a~$k+{n/2}$ bude vìt¹í ne¾~$m$. Mezi~$k$ a~$m$ je tedy +vstupní posloupnost neklesající, mezi $k+{n/2}$ a~$n-1$ nerostoucí. + +Do pozice~$k$ tedy separátor bude pouze kopírovat vstup na~výstup, od~pozice~$k$ +dál u¾~jen prohazuje. Pro ka¾dé~$i$, $(k\leq i\leq {n/2}-1)$ se prvky +$x_i$ a~$x_{i+{n/2}}$ prohodí. Úsek mezi~$k$ a~${n/2}-1$ tedy +nahradíme nerostoucí posloupností, první polovina výstupu tedy bude +(dokonce èistì) bitonická. Podobnì úsek $k+{n/2}$ a¾~$n-1$ nahradíme èistì +bitonickou posloupností. Obì poloviny tedy budou bitonické. + +Dostaneme-li na vstupu obecnou bitonickou posloupnost, pøedstavíme si, +¾e je to èistì bitonická posloupnost zrotovaná o~$r$ prvkù (BÚNO +doprava). Zjistíme, ¾e v~komparátorech se porovnávají tyté¾ prvky, +jako kdyby zrotovaná nebyla. Výstup se od výstupu èistì bitonické +posloupnosti zrotovaného o~$r$ bude li¹it prohozením úsekù $x_0$ a¾ +$x_{r-1}$ a~$x_{n/2}$ a¾ $x_{{n/2}+r-1}$. Obì výstupní +posloupnosti tedy budou zrotované o~$r$ prvkù, ale na jejich +bitoniènosti se nic nezmìní. + +(ii) Z dùkazu (i) pro èistì bitonickou posloupnost víme, ¾e $y_0\dots y_{n/2-1}$ je èistì bitonická a bude rovna $x_0\dots x_{k-1},x_{k+n/2}\dots x_{n-1}$ pro vhodné $k$ a navíc bude mít maximum v $x_{k-1}$ nebo $x_k+{n/2}$. Mezi tìmito body ov¹em ve vstupní posloupnosti urèitì nele¾el ¾ádný $x_i$ men¹í ne¾ $x_k-1$ nebo $x_k+{n/2}$ (jak je vidìt z obrázku) a posloupnost $x_k \dots x_{k-1+{n/2}}$ je rovna $y_{n/2}\dots y_{n-1}$. Pro obecné bitonické posloupnosti uká¾eme stejnì jako v (i). +\qed + +\medskip + +\centerline{\epsfbox{sortnet.7}} + +\bye diff --git a/old/5-addsort/Makefile b/6-bitonic/Makefile similarity index 64% rename from old/5-addsort/Makefile rename to 6-bitonic/Makefile index 4f7be80..496cb3d 100644 --- a/old/5-addsort/Makefile +++ b/6-bitonic/Makefile @@ -1,3 +1,3 @@ -P=5-addsort +P=6-bitonic include ../Makerules diff --git a/old/5-addsort/sortnet.0 b/6-bitonic/sortnet.0 similarity index 100% rename from old/5-addsort/sortnet.0 rename to 6-bitonic/sortnet.0 diff --git a/old/5-addsort/sortnet.1 b/6-bitonic/sortnet.1 similarity index 100% rename from old/5-addsort/sortnet.1 rename to 6-bitonic/sortnet.1 diff --git a/old/5-addsort/sortnet.2 b/6-bitonic/sortnet.2 similarity index 100% rename from old/5-addsort/sortnet.2 rename to 6-bitonic/sortnet.2 diff --git a/old/5-addsort/sortnet.3 b/6-bitonic/sortnet.3 similarity index 100% rename from old/5-addsort/sortnet.3 rename to 6-bitonic/sortnet.3 diff --git a/old/5-addsort/sortnet.4 b/6-bitonic/sortnet.4 similarity index 100% rename from old/5-addsort/sortnet.4 rename to 6-bitonic/sortnet.4 diff --git a/old/5-addsort/sortnet.5 b/6-bitonic/sortnet.5 similarity index 100% rename from old/5-addsort/sortnet.5 rename to 6-bitonic/sortnet.5 diff --git a/old/5-addsort/sortnet.6 b/6-bitonic/sortnet.6 similarity index 100% rename from old/5-addsort/sortnet.6 rename to 6-bitonic/sortnet.6 diff --git a/old/5-addsort/sortnet.7 b/6-bitonic/sortnet.7 similarity index 100% rename from old/5-addsort/sortnet.7 rename to 6-bitonic/sortnet.7 diff --git a/old/5-addsort/sortnet.mp b/6-bitonic/sortnet.mp similarity index 100% rename from old/5-addsort/sortnet.mp rename to 6-bitonic/sortnet.mp diff --git a/old/5-addsort/sortnet.mpx b/6-bitonic/sortnet.mpx similarity index 100% rename from old/5-addsort/sortnet.mpx rename to 6-bitonic/sortnet.mpx diff --git a/old/4-hradla/4-hradla.tex b/old/4-hradla/4-hradla.tex deleted file mode 100644 index ccb0c50..0000000 --- a/old/4-hradla/4-hradla.tex +++ /dev/null @@ -1,139 +0,0 @@ -\input ../lecnotes.tex - -\prednaska{4}{Hradlové sítì}{(zapsal: Petr Jankovský)} - -\def\land{\mathbin{\&}} - -Výkon poèítaèù nelze zvy¹ovat donekoneèna a pøesto¾e ji¾ pìkných pár let platí, -¾e se jejich rychlost s~èasem exponenciálnì zvìt¹uje, jednou urèitì narazíme -pøinejmen¹ím na~fyzikální limity. - -Kdy¾ tedy nemù¾eme zvy¹ovat rychlost jednoho procesoru, jak poèítat rychleji? -Øe¹ením by mohlo být poøídit si procesorù víc. U¾~dnes na~bì¾ném PéCéèku máme -k~dispozici vícejádrové procesory, díky nim¾ mù¾eme vyu¾ít pararelní poèítání -a úlohu øe¹it tak, ¾e práci ¹ikovnì rozdìlíme mezi procesory (èi jádra) a -zamìstnáme je pøi~výpoètu v¹echny. - -My se podíváme na~abstraktní výpoèetní model, který je je¹tì paralelnìj¹í. -Techniky, které si uká¾eme na~tomto modelu, se v¹ak dají pøekvapivì vyu¾ít i~pøi~reálném -paralelizování na~nìkolika málo procesorech. Konec koncù i proto, ¾e vnitøní -architektura procesoru se na¹emu modelu velmi podobá. Budeme se zabývat -jednoduchým modelem paralelního poèítaèe, toti¾ hradlovou sítí. - -\h{Hradlové sítì} - -\s{Definice:} {\I Hradlo} je prvek, který umí vyhodnocovat nìjakou funkci -nad~koneènou abecedou $\Sigma$. - -Obecnì se na~hradlo díváme jako na~funkci $f: {\Sigma}^{k} \rightarrow \Sigma$, která dostane $k$ vstupù -a~vrátí jeden výstup, pøièem¾ hodnoty, nad~kterými pracuje, budou z~nìjaké koneèné -abecedy -- tedy z~nìjaké koneèné mno¾iny symbolù $\Sigma$. Písmenku $k$ zde øíkáme {\I arita -hradla}. - -\s{Pøíklad:} Èasto studujeme hradla booleovská (pracující nad abecedou $\{0,1\}$), která poèítají logické funkce. - -Z~nich nejèastìji potkáme: - -\itemize\ibull -\:nulární: to jsou konstanty (FALSE=0, TRUE=1), -\:unární: napø. negace (znaèíme~$\lnot$), -\:binární: logický souèin ({\sc and},~$\land$), souèet ({\sc or},~$\lor$), ... -\endlist - -\>Hradla kreslíme tøeba následovnì: - -\figure{hradlo_and.eps}{Binární hradlo provádící logickou operaci {\sc and}.}{1in} - -Jednotlivá hradla mù¾eme navzájem urèitým zpùsobem propojovat a vytváøet -z nich {\I hradlové sítì}. Pokud pou¾íváme pouze booleovská hradla, øíkáme takto vytvoøeným -sítím {\I booleovské obvody}. Pokud pracujeme s~operacemi nad nìjakou obecnìj¹í (ale koneènou) -mno¾inou symbolù (abecedou), nazývají se {\I kombinaèní obvody.} - -Ka¾dá hradlová sí» má nìjaké vstupy, nìjaké výstupy a uvnitø jsou propojovaná -hradla. Ka¾dý vstup hradla je pøipojen buïto na~nìkterý ze~vstupù sítì nebo -na~výstup jiného hradla. Výstupy hradel mohou být propojeny na~vstupy dal¹ích -hradel (mohou se vìtvit), nebo na výstupy sítì. Pøitom máme zakázáno vytváøet -cykly. - -Ne¾ si øekneme formální definici, podívejme se na obrázek. - -\figure{hradlova_sit.eps}{Hradlová sí» -- tøívstupová verze funkce {\I majorita}.}{3in} - -Obrazek znázoròuje hradlovou sí», která poèítá, zda je alespoò na~dvou ze~vstupù -jednièka. Pojïme si ale {\I hradlovou sí»} definovat formálnì. - -\s{Definice:} {\I Hradlová sí»} je urèena: -\itemize\ibull -\:{\I abecedou} $\Sigma$ (to je nìjaká koneèná mno¾ina symbolù, obvykle $\Sigma=\{0,1\}$); -\:po dvou disjunktními koneènými mno¾inami $I$~({\I vstupy}), $O$~({\I výstupy}) \hfil\break a~$H$~({\I hradla}); -\:acyklickým orientovaným multigrafem~$(V,E)$, kde~$V = I \cup O \cup H$; -\:zobrazením~$F$, které ka¾dému hradlu $h\in H$ pøiøadí nìjakou funkci~$F(h): - \Sigma^{a(h)} \rightarrow \Sigma$, co¾ je funkce, kterou toto hradlo vykonává. - Èíslu $a(h)$ øíkáme {\I arita} hradla~$h$; -\:zobrazením~$z: E \rightarrow {\bb N}$, které ka¾dé hranì vedoucí do~nìjakého - hradla pøiøazuje nìkterý ze vstupù tohoto hradla. -\endlist - -\>Pøitom jsou splnìny následující podmínky: - -\itemize\ibull -\:$\forall i \in I: \deg^{in}(i)=0$ (do~vstupù nic nevede); -\:$\forall o \in O: \deg^{in}(o)=1~\land~\deg^{out}(o)=0$ (z~výstupù nic nevede a do~ka¾dého vede právì jedna hrana); -\:$\forall h \in H: \deg^{in}(v)=a(v)$ (do~ka¾dého hradla vede tolik hran, kolik je jeho arita); -\:$\forall h \in H~\forall j: 1\le j\le a(h)$ existuje právì jedena hrana~$e$ taková, ¾e~$e$ konèí v~$h$ a~$z(e)=j$, - (v¹echny vstupy hradel jsou zapojeny). -\endlist - -\s{Pozorování:} Kdybychom pøipustili hradla s~libovolnì vysokým poètem vstupù, mohli -bychom libovolný problém se vstupem délky~$n$ vyøe¹it jedním hradlem o~$n$~vstupech, -kterému bychom pøiøadili funkci, která by na¹i úlohu rovnou vyøe¹ila. Tento model -v¹ak není ani realistický, ani pìkný. Proto pøijmìme omezení, ¾e~arity v¹ech hradel -budou omezeny nìjakou pevnou konstantou $k$ (uká¾e se, ¾e nám bude staèit dvojka -a~vystaèíme si tedy pouze s nulárními, unárními a binárními hradly). -Následující obrázky ukazují, jak hradla o~více vstupech nahradit dvouvstupovými: - -\twofigures{hradlo_ternor.eps}{Trojvstupové hradlo \sc or.}{0.5in}{hradlo_ternbior.eps}{Jeho nahrazení 2-vstupovými hradly.}{0.6in} - - -Nyní bychom je¹tì mìli definovat, co taková hradlová sí» vlastnì poèítá a~jak -její výpoèet probíhá. - -\s{Definice:} {\I Výpoèet sítì} probíhá po~{\I taktech.} V nultém taktu jsou definovány pouze -hodnoty na~vstupech sítì a na~výstupech hradel arity 0. Mù¾eme si to pøedstavit -tak, ¾e na~zaèátku nemá ¾ádné hradlo definovánu výstupní hodnotu (a¾ na ji¾ -zmínìná hradla nulární). V~ka¾dém dal¹ím taktu pak vydají výstup hradla, která -na~konci minulého taktu mìla definovány v¹echny hodnoty na vstupech. Jakmile -budou po~nìjakém koneèném poètu taktù definované i hodnoty v¹ech výstupù, sí» -se zastaví a~vydá výsledek. - -\s{Pozorování:} Proto¾e je sí» acyklická, je jasné, ¾e jakmile jednou nìjaké hradlo vydá -výstup, tak se tento výstup bìhem dal¹ího výpoètu sítì ji¾ nezmìní. - -\figure{vypocet_site.eps}{Výpoèet hradlové sítì.}{6cm} - -\>Podle toho, jak sí» poèítá, si ji mù¾eme rozdìlit na~vrstvy: - -\s{Definice:} {\I $i$-tá vrstva $S_i$} obsahuje právì takové vrcholy~$v$, pro~které nejdel¹í cesta ze~vstupù -sítì do $v$ má délku rovnou~$i$. - -\s{Pozorování:} V¹imnìme si, ¾e v $i$-tém taktu vydají hodnoty právì hradla z $S_i$. - -Dává tedy smysl prohlásit za~{\I èasovou slo¾itost} sítì poèet -jejích vrstev. Podobnì {\I prostorovou slo¾itost} definujeme jako poèet hradel v~síti. - -\s{Pøíklad:} Sestrojme sí», která zjistí, zda se mezi jejími~$n$ vstupy -vyskytuje alespoò jedna jednièka. - -\>{\I První øe¹ení:} zapojíme hradla za~sebe (sériovì). Èasová i prostorová -slo¾itost odpovídají~$\Theta(n)$. Zde ov¹em vùbec nevyu¾íváme toho, ¾e by mohlo poèítat více -hradel souèasnì. - -\figure{hloupy_or.eps}{Hradlová sí», která zjistí, zdali je na vstupu alespoò jedna jednièka.}{0.7in} - -\>{\I Druhé øe¹ení:} Hradla budeme spojovat do~dvojic, pak výsledky z~tìchto dvojic opìt -do~dvojic a tak dále. Díky paralelnímu zapojení dosáhneme èasové slo¾itosti $\Theta(\log n)$, -prostorová slo¾itost zùstane lineární. - -\figure{chytry_or.eps}{Chytøej¹í øe¹ení stejného problému pro vstup velikosti 16.}{3in} - -\bye -- 2.39.5