\prednaska{5}{Hradlové sítì}{}
-\def\land{\mathbin{\&}}
-
-®ivot nám pøiná¹í stále vìt¹í problémy, které obvykle vy¾adují stále více
-výpoèetního výkonu. Rychlost poèítaèù sice posledních pár desetiletí stále
-roste exponenciálnì, ale tento rùst se urèitì nìkdy zastaví (napøíklad proto,
-¾e vesmír je koneèný) a podle v¹eho u¾ k~tomuto bodu jsme docela blízko
-(nará¾íme na nejrùznìj¹í fyzikální limity, napøíklad není jasné, jak vyrábìt
-transistory men¹í ne¾ jeden atom).
+\def\NOT{{\csc not}}
+\def\AND{{\csc and}}
+\def\OR{{\csc or}}
+\def\XOR{{\csc xor}}
+\def\and{\mathbin{\&}}
+
+Pomocí poèítaèù øe¹íme stále slo¾itìj¹í a rozsáhlej¹í úlohy a potøebujeme
+k~tomu èím dál víc výpoèetního výkonu. Rychlost a kapacita poèítaèù zatím
+rostla exponenciálnì, tak¾e se zdá, ¾e staèí chvíli poèkat. Jen¾e tento rùst
+se urèitì nìkdy zastaví -- napøíklad není jasné, jestli pùjde vyrábìt transistory
+men¹í ne¾ jeden atom.
Jak si tedy s~obrovskými daty poradíme? Jedna z~lákavých mo¾ností je prostì
do~výpoètu zapøáhnout více ne¾ jeden procesor. Ostatnì, vícejádrové procesory,
Ta poèítají jednotlivé logické funkce, mezi nejbì¾nìj¹í patøí:
\itemize\ibull
-\:nulární: to jsou konstanty ($\hbox{\csc false}=0$, $\hbox{\csc true}=1$),
-\:unární: identita a negace ({\csc not},~$\lnot$),
-\:binární: logický souèin ({\csc and},~$\land$), souèet ({\csc or},~$\lor$), \dots
+\:nulární funkce: to jsou konstanty ($\hbox{\csc false}=0$, $\hbox{\csc true}=1$),
+\:unární funkce: identita a negace (\NOT,~$\lnot$),
+\:binární funkce: logický souèin (\AND,~$\and$), souèet (\OR,~$\lor$), \dots
\endlist
Propojením hradel pak vznikne {\I hradlová sí».} Ne¾ vyøkneme formální definici,
\figure{hradlova_sit.eps}{Hradlová sí» -- tøívstupová verze funkce {\I majorita}}{3in}
-Na¹e sí» má tøi vstupy, vnitøní booleovská hradla a jeden výstup. Na výstupu
+Na¹e sí» má tøi vstupy, pìt booleovských hradel a jeden výstup. Na výstupu
je pøitom jednièka právì tehdy, jsou-li jednièky pøítomny na alespoò dvou
vstupech. Jinými slovy vrací {\I majoritu} ze~vstupù, tedy hodnotu, která
pøeva¾uje.
Obecnì ka¾dá hradlová sí» má nìjaké vstupy, hradla a výstupy.
Ka¾dý vstup hradla je pøitom 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
+dal¹ích hradel (mohou se vìtvit), nebo na výstupy sítì. Libovolnì, jen nesmíme
vytváøet cykly.
Nyní toté¾ formálnìji:
$I$~({\I vstupy}), $O$~({\I výstupy}) a~$H$~({\I hradla});
\:acyklickým orientovaným multigrafem~$(V,E)$, kde~$V = I \cup O \cup H$;\foot{Proè
potøebujeme multigraf? Napøíklad chceme-li výstup jednoho hradla pøipojit souèasnì
- na více rùzných vstupù druhého hradla.}
+ na více rùzných vstupù jiného hradla.}
\: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$;
\>Pøitom jsou splnìny následující podmínky:
\itemize\ibull
-\:$\forall i \in I: \deg^+(i)=0$ {\sl (do~vstupù nic nevede);}
-\:$\forall o \in O: \deg^+(o)=1, \deg^-(o)=0$ {\sl (z~výstupù nic nevede a do~ka¾dého vede právì jedna hrana);}
-\:$\forall h \in H: \deg^+(v)=a(v)$ {\sl (do~ka¾dého hradla vede tolik hran, kolik je jeho arita);}
-\:$\forall h \in H~\forall j \in \{1,\ldots,a(h)\}$ existuje právì jedna hrana~$e$ taková, ¾e $e$~konèí v~$h$ a~$z(e)=j$
- {\sl (v¹echny vstupy hradel jsou zapojeny).}
+\:Do vstupù nevedou ¾ádné hrany.
+\:Z~výstupù nevedou ¾ádné hrany a do ka¾dého výstupu vede právì jedna hrana.
+\:Do ka¾dého hradla vede tolik hran, kolik je jeho arita.
+\:V¹echny vstupy hradel jsou zapojeny. Tedy pro ka¾dé hradlo~$h$ a ka¾dý
+ jeho vstup $j\in \{1,\ldots,a(h)\}$ existuje právì jedna hrana~$e$, která
+ vede do hradla~$h$ a~$z(e)=j$.
\endlist
\s{Poznámka:} Nìkdy se hradlovým sítím také øíká {\I kombinaèní obvody} a pokud pracují
z~vrcholù s~ji¾ definovanou hodnotou.
Hodnotu hradla~$h$ pøitom spoèteme funkcí~$F(h)$ z~hodnot na jeho vstupech
-uspoøádaných podle funkce~$z(h)$. Výstup sítì pouze zkopíruje hodnotu, která do
+uspoøádaných podle funkce~$z$. Výstup sítì pouze zkopíruje hodnotu, která do
nìj po~hranì pøi¹la.
Jakmile budou po~nìjakém poètu taktù definované hodnoty v¹ech výstupù, výpoèet
Podle prùbìhu výpoètu mù¾eme vrcholy sítì rozdìlit do vrstev:
-\s{Definice:} {\I $i$-tá vrstva $S_i$} obsahuje právì takové vrcholy~$v$,
+\s{Definice:} {\I $i$-tá vrstva $S_i$} obsahuje právì ty vrcholy~$v$,
pro~které nejdel¹í z~cest z~libovolného vrcholu se~vstupním stupnìm~0
do~$v$ má délku rovnou právì~$i$.
\>To nás motivuje k~následující definici:
\s{Definice:} {\I Èasovou slo¾itost} sítì definujeme jako poèet jejích neprázdných
-vrstev. Podobnì {\I prostorovou slo¾itost} urèíme jako poèet hradel v~síti.
+vrstev. Podobnì {\I prostorovou slo¾itost} polo¾íme rovnu poètu hradel v~síti.
\s{Poznámka o~aritách:}
Kdybychom pøipustili hradla s~libovolnì vysokým poètem vstupù, mohli bychom
-libovolný problém se vstupem délky~$n$ a výstupem délky~$\ell$ vyøe¹it v~jedné
+jakýkoliv problém se vstupem délky~$n$ a výstupem délky~$\ell$ vyøe¹it v~jedné
vrstvì pomocí $\ell$~kusù $n$-vstupových hradel. Ka¾dému bychom prostì
pøiøadili funkci, která poèítá pøíslu¹ný bit výsledku ze~v¹ech bitù vstupu.
-To v¹ak není ani realistické, ani pìkné. Jak z~toho ven? Pøijmeme prostì
-omezení, ¾e~arity v¹ech hradel budou omezeny nìjakou pevnou konstantou,
-tøeba dvojkou. Budeme tedy pou¾ívat výhradnì nulární, unární a binární hradla.
+To v¹ak není ani realistické, ani pìkné. Jak z~toho ven? Pøidáme pravidlo,
+které omezí arity v¹ech hradel nìjakou pevnou konstantou, tøeba dvojkou.
+Budeme tedy pou¾ívat výhradnì nulární, unární a binární hradla.
Poznamenejme je¹tì, ¾e realistický model (by» s~trochu jinými vlastnostmi)
by vznikl také tehdy, kdybychom místo arity omezily typy funkcí, øeknìme
-na {\csc and}, {\csc or} a {\csc not}.
+na \AND, \OR{} a \NOT.
\s{Poznámka o~uniformitì:}
-Dodejme, ¾e od~bì¾ných výpoèetním modelùm, jako je tøeba RAM, se hradlové
+Dodejme, ¾e od~bì¾ných výpoèetních modelù, jako je tøeba RAM, se hradlové
sítì li¹í jednou podstatnou vlastností -- ka¾dá sí» zpracovává výhradnì vstupy
jedné konkrétní velikosti. Chceme tedy najít nìjaký obecný pøedpis, který
pro ka¾dou velikost vstupu sestrojí pøíslu¹nou sí». Takovým výpoèetním modelùm
se øíká {\I neuniformní.}
A~co myslíme oním pøedpisem pro sestrojení sítì? Bude to pro nás prostì
-nìjaký algoritmus (klasický, neparalelní) bì¾ící v~polynomiálním èase.
+jakýkoliv algoritmus (klasický, neparalelní) bì¾ící v~polynomiálním èase.
(Kdybychom dovolili i pomalej¹í algoritmy, mohli bychom bìhem konstrukce
provádìt nìjaký nároèný pøedvýpoèet a jeho výsledek zabudovat do struktury
-sítì.)
+sítì. To obvykle není ¾ádoucí.)
\h{Hledá se jednièka}
Abychom si nový výpoèetní model osahali, zkusme nejprve sestrojit obvod,
který zjistí, zda se mezi jeho~$n$ vstupy vyskytuje alespoò jedna jednièka.
-Jinými slovy vypoèítat $n$-vstupovou funkci {\csc or}.
+To znamená vypoèítat $n$-vstupovou funkci \OR.
-\>{\I První øe¹ení:} zapojíme hradla za~sebe (sériovì). Èasová i prostorová
+\>{\I První øe¹ení:} Zapojíme hradla za~sebe (sériovì). Èasová i prostorová
slo¾itost èiní $\Theta(n)$. Zde ov¹em vùbec nevyu¾íváme toho, ¾e by mohlo poèítat více
hradel souèasnì.
-\>{\I Druhé øe¹ení:} Hradla budeme spojovat do~dvojic, pak výsledky z~tìchto dvojic opìt
+\>{\I Druhé øe¹ení:} Hradla budeme spojovat do~dvojic, pak výsledky 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í.
+pøièem¾ prostorová slo¾itost zùstane lineární.
\twofigures{hloupy_or.eps}{Sériové øe¹ení}{1in}{chytry_or.eps}{Paralelní øe¹ení}{3in}
Zajímavìj¹í úlohou, její¾ paralelizace u¾ nebude tak triviální, je obyèejné
sèítání dvojkových èísel. Mìjme dvì èísla $x$ a $y$ zapsané ve~dvojkové soustavì. Jejich èíslice oznaème
-$x_{n-1}\ldots x_0$ a $y_{n-1}\ldots y_0$, kde $i$-tý øád má váhu $2^i$.
+$x_{n-1}\ldots x_0$ a $y_{n-1}\ldots y_0$, pøièem¾ $i$-tý øád má váhu $2^i$.
-K~seètení se~ihned nabízí pou¾ít starý dobrý \uv{¹kolní algoritmus sèítání pod sebou}, který
+Ihned se nabízí pou¾ít starý dobrý \uv{¹kolní algoritmus sèítání pod sebou}. Ten
funguje ve~dvojkové soustavì stejnì dobøe jako v~desítkové. Sèítáme èísla zprava doleva,
v¾dy seèteme~$x_i$ s~$y_i$ a~pøièteme pøenos z~ni¾¹ího øádu. Tím dostaneme jednu èíslici
výsledku a~pøenos do~vy¹¹ího øádu. Formálnì bychom to mohli zapsat tøeba takto:
$$
z_i=x_i \oplus y_i \oplus c_i,
$$
-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í
+kde $z_i$ je $i$-tá èíslice souètu, $\oplus$ znaèí operaci \XOR{} (souèet modulo~2) a~$c_i$ je {\I pøenos}
+z~$(i-1)$-ního øádu do~$i$-tého. Pøenos do vy¹¹ího øádu 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. To je tehdy, kdy¾ mezi tøemi xorovanými èíslicemi jsou alespoò
dvì jednièky -- k~tomu se nám hodí ji¾ známý obvod pro majoritu:
\figure{hloupe_scitani.eps}{Sèítání ¹kolním algoritmem}{1.5in}
-Ka¾dá krabièka má sice uvnitø konstantní hloubku, ale její výstupy závisí na pøenosu
-vypoèítaném pøedcházející krabièkou. Jednotlivé krabièky tedy musí urèitì le¾et
-v~rùzných vrstvách sítì. Celkovì má tedy sí» $\Theta(n)$ hladin a také $\Theta(n)$
-hradel. Oproti sekvenènímu algoritmu jsme si tedy vùbec nepomohli.
+Ka¾dá krabièka má sama o~sobì konstantní hloubku, ov¹em k~výpoètu potøebuje pøenos
+vypoèítaný pøedcházející krabièkou. Jednotlivé krabièky proto musí le¾et
+v~rùzných vrstvách sítì. Vrstev tedy je $\Theta(n)$ a stejnì tak hradel.
+Oproti sekvenènímu algoritmu jsme si bohu¾el ani trochu nepomohli.
\h{Pøenosy v~blocích}
Jak sèítání zrychlit? To, co nás pøi sèítání brzdí, jsou evidentnì pøenosy mezi
jednotlivými øády. Kdybychom je dokázali spoèítat rychleji, máme vyhráno -- souèet
-u¾ získáme jednoduchým {\csc xor}ováním, které zvládneme paralelnì v~èase $\Theta(1)$.
+u¾ získáme jednoduchým xorováním, které zvládneme paralelnì v~èase $\Theta(1)$.
Uva¾ujme tedy nad zpùsobem, jak pøenosy spoèítat paralelnì.
Podívejme se na~libovolný {\I blok} v~na¹em souètu. Tak budeme øíkat èíslùm
0&konstantní {\bo 0}, blok {\I pohlcuje} pøenos \cr
1&konstantní {\bo 1}, blok {\I vytváøí} pøenos \cr
x&identita (znaèíme {\tt <}), blok {\I kopíruje} pøenos \cr
-\neg{x}&negace, uká¾eme, ¾e nenastane \cr
+\neg{x}&negace, uká¾eme, ¾e u~¾ádného bloku nenastane \cr
}}$$
Této funkci budeme øíkat {\I chování} pøíslu¹ného bloku.
\figure{bloky_1bit.eps}{Tabulka triviálních blokù}{1.1in}
-Blok prvního druhu v¾dy pøedává nulový pøenos, a» u¾ do~nìj vstoupí jakýkoliv.
-Poslední blok naopak sám o~sobì pøenos vytváøí, a» dostane cokoliv.
-Oba bloky prostøední se chovají tak, ¾e samy o~sobì ¾ádný pøenos nevytvoøí,
+Blok prvního druhu v¾dy pøedává nulový pøenos, a» u¾ do~nìj vstoupí jakýkoliv
+-- pøenos tedy pohlcuje. Poslední blok naopak sám o~sobì pøenos vytváøí,
+a» dostane cokoliv. Oba bloky prostøední se chovají tak, ¾e samy o~sobì ¾ádný pøenos nevytvoøí,
ale~pokud do~nich nìjaký pøijde, tak~také odejde.
-{\I Vìt¹í bloky} mù¾eme rozdìlit na èásti a podle jejich chování urèit,
-jak se chová celý blok. Mìjme blok~$B$ slo¾ený z~men¹ích podblokù~$H$ (horní)
-a~$D$ (dolní), jejich¾ chování u¾ známe. Z~toho mù¾eme odvodit, jak se chová celý blok:
+{\I Vìt¹í bloky} mù¾eme rozdìlit na èásti a podle chování èástí urèit,
+jak se chová celý blok. Mìjme blok~$B$ slo¾ený z~men¹ích podblokù~$H$ (horní èást)
+a~$D$ (dolní). Chování celku závisí na chování èástí takto:
\figure{tabulka_skladani_bloku.eps}{Skládání chování blokù}{1.3in}
Pokud vy¹¹í blok pøenos pohlcuje, pak a»~se u¾~ni¾¹í blok chová jakkoli, slo¾ení
-obou blokù musí v¾dy pohlcovat. V~prvním øádku tabulky jsou tudí¾ nuly. Analogicky,
+obou blokù musí v¾dy pohlcovat. V~prvním øádku tabulky jsou tudí¾ nuly. Analogicky
pokud vy¹¹í blok generuje pøenos, tak~ten ni¾¹í na~tom nic nezmìní. V~druhém
øádku tabulky jsou tedy samé jednièky. Zajímavìj¹í pøípad nastává, pokud vy¹¹í blok
kopíruje -- tehdy zále¾í èistì na~chování ni¾¹ího bloku.
V¹imnìme si, ¾e~skládání chování blokù je vlastnì úplnì obyèejné skládání
funkcí. Nyní bychom mohli prohlásit, ¾e~budeme poèítat nad~tøíprvkovou abecedou,
-a~¾e~celou tabulku doká¾eme spoèítat jedním jediným hradlem. Pojïme si v¹ak
-rozmyslet, jak~bychom takovouto vìc popsali èistì binárnì. Jak tedy tyto tøi stavy
-popisovat pouze nìkolika bity?
-
-Evidentnì nám k tomuto binárnímu zakódování tøí stavù budou staèit bity dva.
-Oznaème si je jako $p$ a $q$. Tato dvojice mù¾e nabývat hned ètyø mo¾ných hodnot,
-kterým pøiøadíme tøi mo¾ná chování bloku. Toto kódování mù¾eme zvolit zcela
-libovolnì, ale pokud si ho zvolíme ¹ikovnì, u¹etøíme si dále práci pøi kompozici.
-Zvolme si tedy kódování takto:
+a~¾e~celou tabulku doká¾eme spoèítat jedním jediným hradlem. Pojïme si pøeci jen
+rozmyslet, jak~bychom takovou operaci popsali èistì binárnì.
+
+Tøi stavy mù¾eme zakódovat pomocí dvou bitù, øíkejme jim tøeba $p$ a~$q$.
+Dvojice $(p,q)$ pøitom mù¾e nabývat hned ètyø mo¾ných hodnot, my dvìma z~nich
+pøiøadíme stejný význam:
$$
(1,*) = \hbox{\tt <} \qquad
(0,0) = \hbox{\bo 0} \qquad
(0,1) = \hbox{\bo 1}.
$$
-Tomu, ¾e blok kopíruje, odpovídá dvojice $p = 1$, $q = \<cokoliv.>$ V~ostatních
-pøípadech bude~$p$ nulové a~$q$ nám bude øíkat, co je na~výstupu pøíslu¹ného bloku.
-Jinými slovy $p = 0$ znamená, ¾e funkce je konstanta, pøièem¾ $q$ øíká jaká; naproti
-tomu $p = 1$~znamená, ¾e funkce je identita, a»~u¾~je $q$ cokoli.
-
-V~tomto kódování mù¾eme na¹i tabulku popsat následovnì:
+Kdykoliv $p=1$, blok kopíruje pøenos. Naopak $p=0$ odpovídá tomu, ¾e blok
+posílá do~vy¹¹ího øádu konstantní pøenos, a $q$~pak urèuje, jaký.
+Kombinování blokù (skládání funkcí) pak mù¾eme popsat následovnì:
$$\eqalign{
- p_B &= p_H \land p_D,\cr
- q_B &= (\neg{p_H} \land q_H) \lor (p_H \land q_D).
+ p_B &= p_H \and p_D,\cr
+ q_B &= (\neg{p_H} \and q_H) \lor (p_H \and q_D).
}$$
+A~prùchod pøenosu blokem (dosazení hodnoty funkce) takto:
+$$
+ c_{j+1} = (p \and c_i) \lor (\neg p \and q).
+$$
+Rozmyslete si, ¾e tyto formule odpovídají vý¹e uvedené tabulce.
\h{Paralelní sèítání}
-Z~popisu chování blokù u¾ je jenom krùèek k~paralelnímu pøedpovídání pøenosù,
+Od~popisu chování blokù je u¾ jenom krùèek k~paralelnímu pøedpovídání pøenosù,
a~tím i k~paralelní sèítaèce. Bez újmy na~obecnosti budeme pøedpokládat,
-¾e~poèet bitù vstupních èísel je mocnina dvojky, jinak si vstup doplníme
-nulami, co¾ výsledný èas bìhu algoritmu zhor¹í maximálnì konstanta-krát.
+¾e~poèet bitù vstupních èísel je mocnina dvojky; jinak vstup doplníme zleva
+nulami.
+
+Algoritmus bude rozdìlen na~dvì èásti:
-Algoritmus bude rozdìlen na~dvì èásti. V~první èásti spoèítá chování
-v¹ech {\I pøirozených blokù} -- tak budeme øíkat blokùm, jejich¾ velikost
-je mocnina dvojky a pozice je dìlitelná velikostí. Nejprve v~konstantním
-èase spoèítá chování blokù velikosti~1, ty pak spojí do dvojic, dvojice
-zase do dvojic atd., obecnì v~$i$-tém kroku spoète chování v¹ech pøirozených
-blokù velikosti~$2^i$.
+{\I První èást} spoèítá chování v¹ech {\I pøirozených blokù} -- tak budeme øíkat
+blokùm, jejich¾ velikost je mocnina dvojky a pozice je dìlitelná velikostí
+(bloky té¾e velikosti se tedy nepøekrývají). Nejprve v~konstantním èase stanoví
+chování blokù velikosti~1, ty pak spojí do dvojic, dvojice zase do dvojic atd.,
+obecnì v~$i$-tém kroku spoète chování v¹ech pøirozených blokù velikosti~$2^i$.
-V~druhé èásti pak dopoèítává pøenosy, a~to tak, aby v~$i$-tém kroku byly známy
+{\I Druhá èást} pak dopoèítá pøenosy, a~to tak, aby v~$i$-tém kroku byly známy
pøenosy do~øádù dìlitelných~$2^{\log n - i}$. V~nultém kroku tedy pouze $c_0=0$
a~$c_n$, který spoèítá z~$c_0$ pomocí chování bloku $\left< 0,n \right>$.
-V~prvním kroku pomocí $\left< 0,n/2 \right>$ dopoèítá $c_{n/2}$,
+V~prvním kroku pomocí bloku $\left< 0,n/2 \right>$ dopoèítá $c_{n/2}$,
v~druhém pomocí $\left< 0,n/4 \right>$ spoèítá $c_{n/4}$ a pomocí
$\left< n/2,3/4\cdot n \right>$ dostane $c_{3/4\cdot n}$ atd.
Obecnì v~$i$-tém kroku pou¾ívá chování blokù velikosti $2^{\log n - i}$.
\s{Sèítací sí»} tedy bude vypadat takto:
\algo
\:$\Theta(1)$ hladin výpoètu chování blokù velikosti~1.
-\:$\Theta(\log n)$ hladin poèítajících chování pøirozených blokù velikosti~$2^i$.
+\:$\Theta(\log n)$ hladin poèítajících chování v¹ech pøirozených blokù.
\:$\Theta(\log n)$ hladin dopoèítávajících pøenosy \uv{zahu¹»ováním}.
\:$\Theta(1)$ hladin na samotné seètení: $\forall i: z_i = x_i \oplus y_i \oplus c_i$.
\endalgo
-\figure{1_9_deleni_bloku.eps}{Výpoèet pøenosu}{2.5in}
+\figure{deleni_bloku.eps}{Výpoèet pøenosu}{2.5in}
-Algoritmus tedy pracuje v~èase $\Theta(\log n)$. Hradel je pou¾ito lineárnì: pøi
-výpoètu chování blokù na jednotlivých hladinách poèet hradel exponenciálnì klesá
+Algoritmus tedy pracuje v~èase $\Theta(\log n)$. Vyu¾ívá k~tomu lineárnì mnoho hradel:
+pøi výpoètu chování blokù na jednotlivých hladinách poèet hradel exponenciálnì klesá
od~$n$ k~1, bìhem zahu¹»ování pøenosù naopak exponenciálnì stoupá od~1 k~$n$.
-Obì geometrické øady mají souèet $\Theta(n)$.
+Obì geometrické øady se seètou na $\Theta(n)$.
\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
-{\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.
-\figure{stromecek.eps}{Stromeèek}{1.4in}
-
-Toto øe¹ení by v¹ak vedlo na~èasovou slo¾itost $\Theta (\log^2 n)$, nebo» sèítat umíme v~èase $\Theta (\log n)$. To je sice dle na¹ich mìøítek
-docela efektivní, ale pøekvapivì to jde je¹tì lépe -- toti¾ na~$\Theta (\log n)$ hladin. Této
-slo¾itosti dosáhneme malým trikem.
+Je¹tì si rozmysleme, jak rychle by bylo mo¾né èísla násobit. Opìt se inspirujeme
+¹kolním algoritmem: pokud násobíme dvì $n$-ciferná èísla $x$ a~$y$, uvá¾íme
+v¹ech~$n$ posunutí èísla~$x$, ka¾dé z~nich vynásobíme pøíslu¹nou èíslicí v~$y$
+a výsledky posèítáme.
+
+\figure{skolni_nasobeni.eps}{©kolní násobení}{2in}
+
+Ve~dvojkové soustavì je to je¹tì jednodu¹¹í: násobení jednou èíslicí je prostý
+\AND. Paralelnì tedy vytvoøíme v¹echna posunutí a spoèítáme v¹echny \AND{}y.
+To v¹e stihneme za 1~takt výpoètu.
+
+Zbývá seèíst $n$~èísel, z~nich¾ ka¾dé má $\Theta(n)$ bitù. Mohli bychom opìt
+sáhnout po~osvìdèeném triku: sèítat dvojice èísel, pak dvojice tìchto souètù, atd.
+Taková sí» by mìla tvar binárního stromu hloubky $\log n$, jeho¾ ka¾dý vrchol
+by obsahoval jednu sèítaèku, a na tu, jak víme, postaèí $\Theta(\log n)$ hladin.
+Celý výpoèet tedy bì¾í v~èase $\Theta(\log^2 n)$.
+
+Jde to ale rychleji, pou¾ijeme-li jednoduchý, témìø kouzelnický trik.
+Sestrojíme {\I kompresor} -- to bude obvod konstantní hloubky, který na~vstupu
+dostane tøi èísla a vypoète z~nich dvì èísla mající stejný souèet jako zadaná
+trojice.
+
+K~èemu je to dobré? Máme-li seèíst $n$~èísel, v~konstantním èase doká¾eme tento
+úkol pøevést na seètení $\lceil 2/3\cdot n\rceil$ èísel, to pak opìt v~konstantním èase
+na seètení $\lceil (2/3)^2\cdot n\rceil$ èísel atd., a¾ nám po $\lceil\log_{3/2} n\rceil = \Theta(\log n)$ krocích
+zbudou dvì èísla a ta seèteme klasickou sèítaèkou. Zbývá vymyslet kompresor.
+
+\s{Konstrukce kompresoru:}
+Oznaème vstupy kompresoru $x$, $y$ a~$z$ a výstupy $p$ a~$q$.
+Pro ka¾dý øád~$i$ spoèteme souèet $x_i + y_i + z_i$. To je nìjaké
+dvoubitové èíslo, tak¾e mù¾eme jeho ni¾¹í bit prohlásit za~$p_i$
+a vy¹¹í za~$q_{i+1}$.
+
+Jinými slovy v¹echna tøi èísla jsme normálnì seèetli, ale místo abychom
+pøenosy posílali do vy¹¹ího øádu, vytvoøili jsme z~nich dal¹í èíslo,
+které má být k~výsledku èasem pøièteno.
+
+\figure{add_3to2.eps}{Kompresor}{0.9in}
+
+\s{Shrnutí:} Na¹e sí» pro paralelní násobení pracuje v~èase $\Theta(\log n)$
+-- nejdøíve v~konstantním èase vytváøíme mezivýsledky, pak pou¾ijeme $\Theta(\log n)$
+hladin kompresorù konstantní hloubky a nakonec jednu sèítaèku hloubky $\Theta(\log n)$.
+Jistou vadou na kráse ov¹em je, ¾e na to potøebujeme $\Theta(n^2)$ hradel.
+
+\h{Tøídící sítì}
+
+Je¹tì zkusíme paralelizovat jeden klasický problém, toti¾ tøídìní.
+Budeme k~tomu pou¾ívat {\I komparátorovou sí»} -- to je hradlová sí»
+slo¾ená z~{\I komparátorù.}
+
+Jeden 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: na~jednom z~nich vrací men¹í ze~vstupních hodnot a~na~druhém tu vìt¹í.
+
+\figure{sortnet.0}{Komparátor}{0.7in}
+
+V~na¹em formalismu hradlových sítí bychom mohli komparátor reprezentovat dvojicí
+hradel: jedno z~nich by poèítalo minimum, druhé maximum. Hodnoty, které tøídíme,
+bychom pøitom pova¾ovali za prvky abecedy.\foot{Komparátorovou sí» mù¾eme také snadno
+pøelo¾it na booleovský obvod. Ka¾dý prvek abecedy reprezentujeme èíslem
+o~$b=\lceil\log_2 \Sigma\rceil$ bitech. Zpùsobem podobným paralelní sèítaèce
+lze z~booleovských hradel sestrojit komparátor hloubky $\Theta(\log b)$. Zkuste to.}
+
+Je¹tì se dohodnìme, ¾e výstupy komparátorù se nikdy nebudou vìtvit. Ka¾dý
+z~nich pøivedeme na~vstup jiného komparátoru nebo na~výstup sítì. Vìtvení
+by nám ostatnì k~nièemu nebylo, proto¾e na~výstupu potøebujeme vydat stejný
+poèet hodnot, jako byl na vstupu, a nemáme ¾ádné hradlo, kterým bychom mohli
+pøípadných vícero vìtví slouèit opìt do~jedné.
+
+\s{Pøíklad:} Zkusíme do øeèi komparátorových sítí pøelo¾it {\I bublinkové tøídìní.}
+Z~nìj získáme obvod na~levém obrázku (¹ipky pøedstavují jednotlivé komparátory).
+Toto nakreslení ov¹em ponìkud klame -- pokud sí» necháme poèítat, mnohá porovnání
+budou probíhat paralelnì. Skuteèný prùbìh výpoètu znázoròuje pravý obrázek,
+na~nìm¾ jsme v¹echny operace provádìné souèasnì znázornili vedle sebe.
+Ihned vidíme, ¾e paralelní bublinkové tøídìní pracuje v~èase $\Theta(n)$
+a potøebuje kvadratický poèet komparátorù.
+
+\twofigures{sortnet.1}{Bubblesort}{143pt}{sortnet.2}{Skuteèný prùbìh výpoètu}{143pt}
+
+Nyní si pøedvedeme rychlej¹í tøídící algoritmus. Pùjdeme na nìj jak se øíká \uv{od lesa}.
+Nejdøíve vymyslíme sí», která bude umìt tøídit jenom nìco -- toti¾ bitonické posloupnosti.
+Pak z~ní teprve sestrojíme obecné tøidìní. Bez újmy na obecnosti pøitom budeme
+pøedpokládat, ¾e ka¾dé dva prvky na vstupu jsou navzájem rùzné a ¾e velikost vstupu
+je mocnina dvojky.
+
+\s{Definice:} Posloupnost $x_0,\dots,x_{n-1} $ je {\I èistì bitonická,} pokud ji mù¾eme
+rozdìlit na nìjaké pozici $k\in\{0, \dots, n-1\}$ tak, ¾e prvky $x_0,\ldots,x_k$ tvoøí rostoucí
+poslopnost, zatímco prvky $x_k,\ldots,x_{n-1}$ tvoøí posloupnost klesající.
+
+\s{Definice:} Posloupnost $x_0,\dots,x_{n-1}$ je {\I bitonická}, jestli¾e ji lze získat
+rotací (cyklickým posunutím) nìjaké èistì bitonické posloupnosti. Tedy pokud existuje
+$0\le j<n$ takové, ¾e posloupnost $x_j,x_{(j+1) \bmod n},\dots, x_{(j+n-1) \bmod n}$
+je èistì bitonická.
+
+\s{Definice:} {\I Separátor øádu~$n$} je komparátorová sí»~$S_n$ se vstupy $x_0,\ldots,x_{n-1}$
+a výstupy $y_0,\ldots,y_{n-1}$, která dostane-li na~vstupu bitonickou posloupnost,
+vydá na výstup její permutaci s~následujícími vlastnostmi:
-Vymyslíme obvod konstantní hloubky, který na~vstupu dostane tøi èísla. Odpoví pak dvìma èísly
-takovými, ¾e budou mít stejný souèet jako pùvodní tøi èísla. Jinými slovy pomocí
-tohoto obvodu budeme umìt seètení tøí èísel pøevést na seètení dvou èísel.
-
-\figure{obvod.eps}{$x+y+z = p+q$}{0.3in}
-
-V¹imnìme si, ¾e~kdy¾ sèítáme tøi bity, mù¾e být pøenos do~vy¹¹ího øádu nula èi~jednièka. Vezmeme si tedy bity $x_i$, $y_i$, $z_i$ a~ty seèteme. To nám dá dvoubitový výsledek, pøièem¾ ni¾¹í bit z~tohoto výsledku po¹leme do~èísla~$p$, vy¹¹í do~èísla~$q$.
-
-\figure{obvod_real.eps}{Redukování sèítání}{1.2in}
-
-Toto zredukování sèítání nám nyní umo¾ní opìt stavit strom, by» o malièko slo¾itìj¹í.
-
-\figure{sl_stromecek.eps}{Slo¾itìj¹í stromeèek}{0.9in}
-
-Pokud jsme mìli na~zaèátku $n$ èísel, po~první redukci nám jich zbývá jen $2/3 \cdot n$ a~obecnì v~$k$-té hladiné $(2/3)^k \cdot n$. Znamená to, ¾e èísel nám ubývá exponenciálnì, tak¾e poèet hladin bude logaritmický. Redukující obvod je pøi tom jen konstantnì hluboký, tak¾e celé redukování zvládneme v~èase $\Theta (\log n)$. Na~konci Slo¾itìj¹ího stromeèku pak máme umístìnou jednu obyèejnou sèítaèku, která zbývající dvì èísla seète v~logaritmickém èase.
+\itemize\ibull
+\:$y_0,\ldots,y_{n/2-1}$ a $y_{n/2},\ldots,y_{n-1}$ jsou bitonické posloupnosti;
+\:$y_i < y_j$, kdykoliv $0\le i<n/2 \le j<n$.
+\endlist
-Seètení v¹ech $n$ èísel tedy zabere $\Theta (\log n)$ hladin.
+\>Jinak øeèeno, separátor rozdìlí bitonickou posloupnost na dvì polovièní
+a navíc jsou v¹echny prvky v~první polovinì men¹í ne¾ v¹echny v~té druhé.
+
+\s{Lemma:} Pro ka¾dé sudé~$n$ existuje separátor~$S_n$ konstantní hloubky,
+slo¾ený z~$\Theta(n)$ komparátorù.
-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ì paralelní a~zvládneme ho za~konstantnì mnoho hladin. Celé násobení tedy zvládneme v~logaritmickém èase.
+Dùkaz tohoto lemmatu si necháme na konec kapitoly. Nejprve pøedvedeme, k~èemu jsou
+separátory dobré.
+
+\s{Definice:} {\I Bitonická tøídièka øádu~$n$} je komparátorová sí»~$B_n$,
+která dostane-li na vstupu bitonickou posloupnost délky~$n$, vydá ji setøídìnou.
+
+\s{Lemma:} Pro libovolné $n=2^k$ existuje bitonická tøidièka~$B_n$ hloubky $\Theta(\log n)$
+s~$\Theta(n\log n)$ komparátory.
+
+\proof
+Konstrukce bitonické tøidièky je snadná: nejprve separátorem~$S_n$ zadanou bitonickou
+posloupnost rozdìlíme na dvì bitonické posloupnosti délky $n/2$, ka¾dou z~nich pak separátorem~$S_{n/2}$
+na dvì èásti délky $n/4$, atd., a¾ získáme jednoprvkové posloupnosti ve~správném poøadí.
+Celkem pou¾ijeme~$\log n$ hladin slo¾ených z~$n$ separátorù, ka¾dá
+hladina má pøitom konstantní hloubku.
+\qed
+
+\figure{sortnet.5}{Bitonická tøidièka $B_n$}{\epsfxsize}
+
+Bitonické tøidièky nám nyní pomohou ke~konstrukci tøidièky na obecné posloupnosti.
+Ta bude zalo¾ena na tøídìní sléváním -- nejprve se tedy musíme nauèit slít dvì
+setøídìné posloupnosti do jedné.
+
+\s{Definice:} {\I Slévaèka øádu~$n$} je komparátorová sí»~$M_n$ s~$2\times n$
+vstupy a~$n$ výstupy, která dostane-li dvì setøídìné posloupnosti délky~$n$,
+vydá posloupnost vzniklou jejich slitím.
+
+\s{Lemma:} Pro $n=2^k$ existuje slévaèka~$M_n$ hloubky $\Theta(\log n)$
+s~$\Theta(n\log n)$ komparátory.
+
+\proof
+Staèí jednu vstupní posloupnost obrátit a \uv{pøilepit} za tu druhou. Tím vznikne
+bitonická posloupnost, jí¾ setøídíme bitonickou tøidièkou~$B_{2n}$.
+\qed
+
+\s{Definice:} {\I Tøídící sí» øádu~$n$} je komparátorová sí»~$T_n$ s~$n$~vstupy
+a~$n$~výstupy, která pro ka¾dý vstup vydá jeho setøídìnou permutaci.
+
+\s{Lemma:} Pro $n=2^k$ existuje tøídící sí»~$T_n$ hloubky $\Theta(\log^2 n)$
+slo¾ená z~$\Theta(n\log^2 n)$ komparátorù.
+
+\proof
+Sí» bude tøídit sléváním. Vstup rozdìlí na~$n$ jednoprvkových posloupností.
+Ty jsou jistì setøídìné, tak¾e je slévaèkami~$M_1$ mù¾eme slít do dvouprvkových
+setøídìných posloupností. Na ty pak aplikujeme slévaèky $M_2$, $M_4$, \dots, $M_{n/2}$,
+a¾ v¹echny èásti slijeme do jedné, setøídìné.
+
+Celkem provedeme $\log n$~krokù slévání, $i$-tý z~nich obsahuje slévaèky $M_{2^i}$
+a ty, jak u¾ víme, mají hloubku $\Theta(i)$. Celkový poèet vrstev tedy èiní
+$\Theta(1+2+3+\ldots+\log n) = \Theta(\log^2 n)$. Ka¾dý krok pøitom potøebuje
+$\Theta(n\log n)$ komparátorù, co¾ dává celkem $\Theta(n \log^2 n)$ komparátorù.
+\qed
+
+\figure{sortnet.6}{Tøidièka $T_8$}{\epsfxsize}
+
+\s{Konstrukce separátoru:} Zbývá dokázat, ¾e existují separátory konstantní
+hloubky. Vypadají pøekvapivì jednodu¹e: pro $i=0,\ldots,n/2-1$ zapojíme
+komparátor se vstupy $x_i$, $x_{i+n/2}$, jeho¾ minimum pøivedeme na~$y_i$
+a maximum na~$y_{i+n/2}$.
+
+\figure{sortnet.3}{Konstrukce separátoru}{\epsfxsize}
+
+Proè separátor separuje? Nejprve pøedpokládejme, ¾e vstupem je èistì bitonická
+posloupnost. Oznaème~$m$ polohu maxima této posloupnosti; maximum bez újmy
+na obecnosti le¾í v~první polovinì (jinak celý dùkaz provedeme \uv{zrcadlovì}).
+Oznaème dále~$k$ nejmen¹í index, pro který komparátor zapojený mezi $x_k$ a~$x_{k+n/2}$
+hodnoty prohodí, tedy $k=\min \{ i \mid x_i > x_{i+n/2} \}.$
+
+Jeliko¾ maximum je jedineèné, musí platit $x_m > x_{m+n/2}$, tak¾e~$k$
+existuje a navíc $0\le k\le m < n/2$. Také platí, ¾e pro ka¾dé~$i$ mezi
+$k$ a~$n/2$ u¾ komparátory musí prohazovat, proto¾e od~$x_k$ je posloupnost
+a¾ do konce klesající, a~proto $x_i > x_{i+n/2}$.
+
+Separátor se tedy chová velice jednodu¹e: první polovina výstupu vznikne
+slepením rostoucího úseku $x_0,\ldots,x_{k-1}$ s~klesajícím úsekem $x_{n/2+k},\ldots,x_{n-1}$;
+druhou polovinu tvoøí spojení klesajícího úseku $x_{n/2},\ldots,x_{n/2+k-1}$, rostoucího
+úseku $x_k,\ldots,x_m$ a klesajícího úseku $x_m,\ldots,x_{n/2-1}$.
+
+Snadno tedy ovìøíme, ¾e se separátor chová podle definice: První polovina
+je èistì bitonická a jeliko¾ $x_{n/2-1} > x_{n/2}$, je druhá polovina bitonická
+(obvykle ne èistì). Navíc víme, ¾e nejvy¹¹ím bodem první èásti je~$x_k$
+a nejni¾¹ím bodem druhé èásti~$x_{n/2+k} > x_k$, tak¾e v¹echny prvky první
+èásti musí být men¹í ne¾ v¹echny v~té druhé.
+
+\figure{sortnet.7}{Ilustrace èinnosti separátoru}{\epsfxsize}
+
+Doplòme, co se stane, pokud vstup není èistì bitonický. Zde vyu¾ijeme toho,
+¾e separátor je symetrický, tudí¾ zrotujeme-li jeho vstup o~$p$ pozic, dostaneme
+o~$p$ pozic zrotované i obì poloviny výstupu. Podle definice ov¹em pro ka¾dou bitonickou
+posloupnost existuje její rotace, která je èistì bitonická, a~pro ní¾, jak
+u¾ víme, separátor funguje. Tak¾e pro neèistou bitonickou posloupnost musí
+vydat výsledek pouze zrotovaný, co¾ ov¹em na jeho správnosti nic nemìní.
+\qed
+
+\s{Závìrem:} Nalezli jsme paralelní tøídící algoritmus o~èasové slo¾itosti $\Theta(\log^2 n)$,
+který vyu¾ívá $\Theta(n\log^2 n)$ komparátorù. Dodejme, ¾e jsou známé i tøídící sítì
+hloubky $\Theta(\log n)$, ale jejich konstrukce je mnohem komplikovanìj¹í a dává
+obrovské multiplikativní konstanty, které brání praktickému pou¾ití.
+
+Pomocí dolního odhadu slo¾itosti tøídìní (viz minulý semestr) navíc mù¾eme
+snadno dokázat, ¾e logaritmický poèet hladin je nejni¾¹í mo¾ný. Máme-li toti¾
+libovolnou tøídící sí» hloubky~$h$, mù¾eme ji simulovat po~hladinách a získat
+tak sekvenèní tøídící algoritmus. Jeliko¾ na ka¾dé hladinì mù¾e le¾et nejvý¹e~$n/2$
+komparátorù, ná¹ algoritmus provede maximálnì $hn/2$ porovnání. My ov¹em víme, ¾e pro
+ka¾dý tøídící algoritmus existují vstupy, na~kterých porovná $\Omega(n\log n)$-krát.
+Proto $h=\Omega(\log n)$.
\bye
projects / ads2.git / blobdiff