3 \prednaska{5}{Hradlové sítì}{}
5 \def\land{\mathbin{\&}}
7 ®ivot nám pøiná¹í stále vìt¹í problémy, které obvykle vy¾adují stále více
8 výpoèetního výkonu. Rychlost poèítaèù sice posledních pár desetiletí stále
9 roste exponenciálnì, ale tento rùst se urèitì nìkdy zastaví (napøíklad proto,
10 ¾e vesmír je koneèný) a podle v¹eho u¾ k~tomuto bodu jsme docela blízko
11 (nará¾íme na nejrùznìj¹í fyzikální limity, napøíklad není jasné, jak vyrábìt
12 transistory men¹í ne¾ jeden atom).
14 Jak si tedy s~obrovskými daty poradíme? Jedna z~lákavých mo¾ností je prostì
15 do~výpoètu zapøáhnout více ne¾ jeden procesor. Ostatnì, vícejádrové procesory,
16 které dneska najdeme ve~svých stolních poèítaèích, nejsou nic jiného ne¾
17 víceprocesorový systém na jednom èipu.
19 Nabízí se tedy obtí¾nou úlohu rozdìlit na nìkolik èástí, nechat ka¾dý
20 procesor (èi jádro) poèítat jednu z~èástí a nakonec jejich výsledky spojit
21 dohromady. To se snadno øekne, ale s~výjimkou triviálních úloh u¾ obtí¾nìji
24 Pojïme se podívat na nìkolik zajímavých paralelních algoritmù. Abychom se
25 nemuseli zabývat detaily hardwaru konkrétního víceprocesorového poèítaèe,
26 zavedeme si pomìrnì abstraktní výpoèetní model, toti¾ hradlové sítì. Tento
27 model je daleko paralelnìj¹í ne¾ skuteèný poèítaè, ale pøesto se techniky,
28 které si uká¾eme, dají snadno vyu¾ít i prakticky. Konec koncù sama vnitøní
29 architektura procesorù se na¹emu modelu velmi podobá.
33 Hradlové sítì jsou tvoøeny navzájem propojenými {\I hradly.} Ka¾dé hradlo pøitom
34 poèítá nìjakou (obecnì libovolnou) funkci $\Sigma^k \rightarrow \Sigma$, kde~$\Sigma$
35 je koneèná abeceda (stejná pro celou sí») a~$k$ pøirozené èíslo (poèet vstupù hradla,
36 jinak té¾ jeho {\I arita}).
38 \s{Pøíklad:} Èasto studujeme hradla {\I booleovská} (pracující nad abecedou $\Sigma=\{0,1\}$).
39 Ta poèítají jednotlivé logické funkce, mezi nejbì¾nìj¹í patøí:
42 \:nulární: to jsou konstanty ($\hbox{\csc false}=0$, $\hbox{\csc true}=1$),
43 \:unární: identita a negace ({\csc not},~$\lnot$),
44 \:binární: logický souèin ({\csc and},~$\land$), souèet ({\csc or},~$\lor$), \dots
47 Propojením hradel pak vznikne {\I hradlová sí».} Ne¾ vyøkneme formální definici,
48 pojïme se podívat na pøíklad jedné takové sítì:
50 \figure{hradlova_sit.eps}{Hradlová sí» -- tøívstupová verze funkce {\I majorita}}{3in}
52 Na¹e sí» má tøi vstupy, vnitøní booleovská hradla a jeden výstup. Na výstupu
53 je pøitom jednièka právì tehdy, jsou-li jednièky pøítomny na alespoò dvou
54 vstupech. Jinými slovy vrací {\I majoritu} ze~vstupù, tedy hodnotu, která
57 Obecnì ka¾dá hradlová sí» má nìjaké vstupy, hradla a výstupy.
58 Ka¾dý vstup hradla je pøitom pøipojen buïto na~nìkterý ze~vstupù sítì
59 nebo na~výstup jiného hradla. Výstupy hradel mohou být propojeny na~vstupy
60 dal¹ích hradel (mohou se vìtvit), nebo na výstupy sítì. Pøitom máme zakázáno
63 Nyní toté¾ formálnìji:
65 \s{Definice:} {\I Hradlová sí»} je urèena:
67 \:{\I abecedou} $\Sigma$, co¾ je nìjaká koneèná mno¾ina symbolù;
68 \:po dvou disjunktními koneènými mno¾inami \hfil\break
69 $I$~({\I vstupy}), $O$~({\I výstupy}) a~$H$~({\I hradla});
70 \:acyklickým orientovaným multigrafem~$(V,E)$, kde~$V = I \cup O \cup H$;\foot{Proè
71 potøebujeme multigraf? Napøíklad chceme-li výstup jednoho hradla pøipojit souèasnì
72 na více rùzných vstupù druhého hradla.}
73 \:zobrazením~$F$, které ka¾dému hradlu $h\in H$ pøiøadí nìjakou funkci~$F(h):
74 \Sigma^{a(h)} \rightarrow \Sigma$, co¾ je funkce, kterou toto hradlo vykonává.
75 Èíslu $a(h)$ øíkáme {\I arita} hradla~$h$;
76 \:zobrazením~$z: E \rightarrow {\bb N}$, je¾ o~hranách vedoucích do hradel øíká,
77 kolikátému argumentu funkce odpovídají;\foot{Na hranách vedoucích do výstupù
78 necháváme hodnotu této funkce nevyu¾itu.}
81 \>Pøitom jsou splnìny následující podmínky:
84 \:$\forall i \in I: \deg^+(i)=0$ {\sl (do~vstupù nic nevede);}
85 \:$\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);}
86 \:$\forall h \in H: \deg^+(v)=a(v)$ {\sl (do~ka¾dého hradla vede tolik hran, kolik je jeho arita);}
87 \:$\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$
88 {\sl (v¹echny vstupy hradel jsou zapojeny).}
91 \s{Poznámka:} Nìkdy se hradlovým sítím také øíká {\I kombinaèní obvody} a pokud pracují
92 nad abecedou $\Sigma = \{0,1\}$, pak {\I booleovské obvody}.
94 \s{Definice:} {\I Výpoèet sítì} postupnì pøiøazuje hodnoty z~abecedy~$\Sigma$
95 vrcholùm grafu. Výpoèet probíhá po~{\I taktech.} V~nultém taktu jsou definovány
96 pouze hodnoty na~vstupech sítì a v~hradlech arity~0 (konstanty). V~ka¾dém
97 dal¹ím taktu pak ohodnotíme vrcholy, jejich¾ v¹echny vstupní hrany vedou
98 z~vrcholù s~ji¾ definovanou hodnotou.
100 Hodnotu hradla~$h$ pøitom spoèteme funkcí~$F(h)$ z~hodnot na jeho vstupech
101 uspoøádaných podle funkce~$z(h)$. Výstup sítì pouze zkopíruje hodnotu, která do
104 Jakmile budou po~nìjakém poètu taktù definované hodnoty v¹ech výstupù, výpoèet
105 se zastaví a~sí» vydá výsledek -- ohodnocení výstupù.
107 Podle prùbìhu výpoètu mù¾eme vrcholy sítì rozdìlit do vrstev:
109 \s{Definice:} {\I $i$-tá vrstva $S_i$} obsahuje právì takové vrcholy~$v$,
110 pro~které nejdel¹í z~cest z~libovolného vrcholu se~vstupním stupnìm~0
111 do~$v$ má délku rovnou právì~$i$.
113 \figure{vypocet_site.eps}{Prùbìh výpoètu a rozdìlení sítì na vrstvy}{6cm}
115 \s{Pár pozorování} o~prùbìhu výpoètu:
118 \:V~$i$-té vrstvì jsou tedy právì ty vrcholy, které poprvé ohodnotíme v~$i$-tém
120 \:Jeliko¾ sí» je acyklická, tak platí, ¾e jakmile vrchol ohodnotíme, u¾ se
121 jeho ohodnocení nikdy nemù¾e zmìnit.
122 \:Kdy¾ se vydáme z~libovolného vrcholu proti smìru hran, po~koneènì mnoha
123 krocích dojdeme do~vrcholu s~nulovým vstupním stupnìm (vstupu sítì nebo
124 konstantního hradla). Proto ka¾dý vrchol le¾í v~nìjaké vrstvì.
125 \:Vrstvy jsou disjunktní, tak¾e poèet neprázdných vrstev je nutnì koneèný.
126 V~kombinaci s~pøedchozím pozorováním dostaneme, ¾e výpoèet sítì se v¾dy zastaví.
127 \:Navíc poslední neprázdná vrstva je právì ta, kde se výpoèet zastaví -- z~ka¾dého
128 dal¹ího vrcholu by toti¾ bylo mo¾né po~hranách dojít do vrcholu s~výstupním
129 stupnìm~0 a jediné takové vrcholy jsou výstupy sítì. Ty by tedy musely také
130 le¾et v~nìkteré z~následujících vrstev, co¾ ov¹em není mo¾né, nebo» výpoèet
134 \>To nás motivuje k~následující definici:
136 \s{Definice:} {\I Èasovou slo¾itost} sítì definujeme jako poèet jejích neprázdných
137 vrstev. Podobnì {\I prostorovou slo¾itost} urèíme jako poèet hradel v~síti.
139 \s{Poznámka o~aritách:}
140 Kdybychom pøipustili hradla s~libovolnì vysokým poètem vstupù, mohli bychom
141 libovolný problém se vstupem délky~$n$ a výstupem délky~$\ell$ vyøe¹it v~jedné
142 vrstvì pomocí $\ell$~kusù $n$-vstupových hradel. Ka¾dému bychom prostì
143 pøiøadili funkci, která poèítá pøíslu¹ný bit výsledku ze~v¹ech bitù vstupu.
145 To v¹ak není ani realistické, ani pìkné. Jak z~toho ven? Pøijmeme prostì
146 omezení, ¾e~arity v¹ech hradel budou omezeny nìjakou pevnou konstantou,
147 tøeba dvojkou. Budeme tedy pou¾ívat výhradnì nulární, unární a binární hradla.
149 Poznamenejme je¹tì, ¾e realistický model (by» s~trochu jinými vlastnostmi)
150 by vznikl také tehdy, kdybychom místo arity omezily typy funkcí, øeknìme
151 na {\csc and}, {\csc or} a {\csc not}.
153 \s{Poznámka o~uniformitì:}
154 Dodejme, ¾e od~bì¾ných výpoèetním modelùm, jako je tøeba RAM, se hradlové
155 sítì li¹í jednou podstatnou vlastností -- ka¾dá sí» zpracovává výhradnì vstupy
156 jedné konkrétní velikosti. Chceme tedy najít nìjaký obecný pøedpis, který
157 pro ka¾dou velikost vstupu sestrojí pøíslu¹nou sí». Takovým výpoèetním modelùm
158 se øíká {\I neuniformní.}
160 A~co myslíme oním pøedpisem pro sestrojení sítì? Bude to pro nás prostì
161 nìjaký algoritmus (klasický, neparalelní) bì¾ící v~polynomiálním èase.
162 (Kdybychom dovolili i pomalej¹í algoritmy, mohli bychom bìhem konstrukce
163 provádìt nìjaký nároèný pøedvýpoèet a jeho výsledek zabudovat do struktury
166 \h{Hledá se jednièka}
168 Abychom si nový výpoèetní model osahali, zkusme nejprve sestrojit obvod,
169 který zjistí, zda se mezi jeho~$n$ vstupy vyskytuje alespoò jedna jednièka.
170 Jinými slovy vypoèítat $n$-vstupovou funkci {\csc or}.
172 \>{\I První øe¹ení:} zapojíme hradla za~sebe (sériovì). Èasová i prostorová
173 slo¾itost èiní $\Theta(n)$. Zde ov¹em vùbec nevyu¾íváme toho, ¾e by mohlo poèítat více
176 \>{\I Druhé øe¹ení:} Hradla budeme spojovat do~dvojic, pak výsledky z~tìchto dvojic opìt
177 do~dvojic a tak dále. Díky paralelnímu zapojení dosáhneme èasové slo¾itosti $\Theta(\log n)$,
178 prostorová slo¾itost zùstane lineární.
180 \twofigures{hloupy_or.eps}{Sériové øe¹ení}{1in}{chytry_or.eps}{Paralelní øe¹ení}{3in}
182 \h{Sèítání binárních èísel}
184 Zajímavìj¹í úlohou, její¾ paralelizace u¾ nebude tak triviální, je obyèejné
185 sèítání dvojkových èísel. Mìjme dvì èísla $x$ a $y$ zapsané ve~dvojkové soustavì. Jejich èíslice oznaème
186 $x_{n-1}\ldots x_0$ a $y_{n-1}\ldots y_0$, kde $i$-tý øád má váhu $2^i$.
188 K~seètení se~ihned nabízí pou¾ít starý dobrý \uv{¹kolní algoritmus sèítání pod sebou}, který
189 funguje ve~dvojkové soustavì stejnì dobøe jako v~desítkové. Sèítáme èísla zprava doleva,
190 v¾dy seèteme~$x_i$ s~$y_i$ a~pøièteme pøenos z~ni¾¹ího øádu. Tím dostaneme jednu èíslici
191 výsledku a~pøenos do~vy¹¹ího øádu. Formálnì bychom to mohli zapsat tøeba takto:
193 z_i=x_i \oplus y_i \oplus c_i,
195 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}
196 z~$(i-1)$-ního øádu do~$i$-tého. Pøenos pøitom nastane tehdy, pokud se~nám potkají
197 dvì jednièky pod~sebou, nebo kdy¾ se~vyskytne alespoò jedna jednièka a~k~tomu
198 pøenos z~ni¾¹ího øádu. To je tehdy, kdy¾ mezi tøemi xorovanými èíslicemi jsou alespoò
199 dvì jednièky -- k~tomu se nám hodí ji¾ známý obvod pro majoritu:
203 c_{i+1} &= (x_i~\&~y_i)\lor(x_i~\&~c_i)\lor(y_i~\&~c_i).\cr
207 O~tomto pøedpisu snadno doká¾eme, ¾e funguje (zkuste si to), nicménì pokud podle
208 nìj postavíme hradlovou sí», bude pomìrnì pomalá. Sí» si mù¾eme pøedstavit tak,
209 ¾e je slo¾ena z~nìjakých podsítí (\uv{krabièek}), které budou mít na~vstupu $x_i$,
210 $y_i$ a~$c_i$ a jejich výstupem bude $z_i$ a~$c_{i+1}$:
212 \figure{hloupe_scitani.eps}{Sèítání ¹kolním algoritmem}{1.5in}
214 Ka¾dá krabièka má sice uvnitø konstantní hloubku, ale její výstupy závisí na pøenosu
215 vypoèítaném pøedcházející krabièkou. Jednotlivé krabièky tedy musí urèitì le¾et
216 v~rùzných vrstvách sítì. Celkovì má tedy sí» $\Theta(n)$ hladin a také $\Theta(n)$
217 hradel. Oproti sekvenènímu algoritmu jsme si tedy vùbec nepomohli.
219 \h{Pøenosy v~blocích}
221 Jak sèítání zrychlit? To, co nás pøi sèítání brzdí, jsou evidentnì pøenosy mezi
222 jednotlivými øády. Kdybychom je dokázali spoèítat rychleji, máme vyhráno -- souèet
223 u¾ získáme jednoduchým {\csc xor}ováním, které zvládneme paralelnì v~èase $\Theta(1)$.
224 Uva¾ujme tedy nad zpùsobem, jak pøenosy spoèítat paralelnì.
226 Podívejme se na~libovolný {\I blok} v~na¹em souètu. Tak budeme øíkat èíslùm
227 $x_j\ldots x_i$ a $y_j\ldots y_i$ v~nìjakém intervalu indexù $\left<i,j\right>$. Pøenos $c_{j+1}$ vystupující z~tohoto bloku závisí mimo hodnot sèítancù u¾ pouze na~pøenosu $c_{i}$, který do bloku vstupuje.
229 \figure{blok_scitani.eps}{Blok souètu}{3in}
231 Pro konkrétní sèítance se tedy mù¾eme na blok dívat jako na nìjakou funkci,
232 která dostane jednobitový vstup (pøenos zespoda) a vydá jednobitový výstup (pøenos
233 nahoru). To je nám milé, nebo» takové funkce existují pouze ètyøi:
234 $$\vbox{\halign{$f(x) = #$\hfil &\qquad # \hfil\cr
235 0&konstantní {\bo 0}, blok {\I pohlcuje} pøenos \cr
236 1&konstantní {\bo 1}, blok {\I vytváøí} pøenos \cr
237 x&identita (znaèíme {\tt <}), blok {\I kopíruje} pøenos \cr
238 \neg{x}&negace, uká¾eme, ¾e nenastane \cr
240 Této funkci budeme øíkat {\I chování} pøíslu¹ného bloku.
242 {\I Jednobitové bloky} se pøitom chovají velice jednodu¹e:
244 \figure{bloky_1bit.eps}{Tabulka triviálních blokù}{1.1in}
246 Blok prvního druhu v¾dy pøedává nulový pøenos, a» u¾ do~nìj vstoupí jakýkoliv.
247 Poslední blok naopak sám o~sobì pøenos vytváøí, a» dostane cokoliv.
248 Oba bloky prostøední se chovají tak, ¾e samy o~sobì ¾ádný pøenos nevytvoøí,
249 ale~pokud do~nich nìjaký pøijde, tak~také odejde.
251 {\I Vìt¹í bloky} mù¾eme rozdìlit na èásti a podle jejich chování urèit,
252 jak se chová celý blok. Mìjme blok~$B$ slo¾ený z~men¹ích podblokù~$H$ (horní)
253 a~$D$ (dolní), jejich¾ chování u¾ známe. Z~toho mù¾eme odvodit, jak se chová celý blok:
255 \figure{tabulka_skladani_bloku.eps}{Skládání chování blokù}{1.3in}
257 Pokud vy¹¹í blok pøenos pohlcuje, pak a»~se u¾~ni¾¹í blok chová jakkoli, slo¾ení
258 obou blokù musí v¾dy pohlcovat. V~prvním øádku tabulky jsou tudí¾ nuly. Analogicky,
259 pokud vy¹¹í blok generuje pøenos, tak~ten ni¾¹í na~tom nic nezmìní. V~druhém
260 øádku tabulky jsou tedy samé jednièky. Zajímavìj¹í pøípad nastává, pokud vy¹¹í blok
261 kopíruje -- tehdy zále¾í èistì na~chování ni¾¹ího bloku.
263 V¹imnìme si, ¾e~skládání chování blokù je vlastnì úplnì obyèejné skládání
264 funkcí. Nyní bychom mohli prohlásit, ¾e~budeme poèítat nad~tøíprvkovou abecedou,
265 a~¾e~celou tabulku doká¾eme spoèítat jedním jediným hradlem. Pojïme si v¹ak
266 rozmyslet, jak~bychom takovouto vìc popsali èistì binárnì. Jak tedy tyto tøi stavy
267 popisovat pouze nìkolika bity?
269 Evidentnì nám k tomuto binárnímu zakódování tøí stavù budou staèit bity dva.
270 Oznaème si je jako $p$ a $q$. Tato dvojice mù¾e nabývat hned ètyø mo¾ných hodnot,
271 kterým pøiøadíme tøi mo¾ná chování bloku. Toto kódování mù¾eme zvolit zcela
272 libovolnì, ale pokud si ho zvolíme ¹ikovnì, u¹etøíme si dále práci pøi kompozici.
273 Zvolme si tedy kódování takto:
275 (1,*) = \hbox{\tt <} \qquad
276 (0,0) = \hbox{\bo 0} \qquad
277 (0,1) = \hbox{\bo 1}.
279 Tomu, ¾e blok kopíruje, odpovídá dvojice $p = 1$, $q = \<cokoliv.>$ V~ostatních
280 pøípadech bude~$p$ nulové a~$q$ nám bude øíkat, co je na~výstupu pøíslu¹ného bloku.
281 Jinými slovy $p = 0$ znamená, ¾e funkce je konstanta, pøièem¾ $q$ øíká jaká; naproti
282 tomu $p = 1$~znamená, ¾e funkce je identita, a»~u¾~je $q$ cokoli.
284 V~tomto kódování mù¾eme na¹i tabulku popsat následovnì:
286 p_B &= p_H \land p_D,\cr
287 q_B &= (\neg{p_H} \land q_H) \lor (p_H \land q_D).
290 \h{Paralelní sèítání}
292 Z~popisu chování blokù u¾ je jenom krùèek k~paralelnímu pøedpovídání pøenosù,
293 a~tím i k~paralelní sèítaèce. Bez újmy na~obecnosti budeme pøedpokládat,
294 ¾e~poèet bitù vstupních èísel je mocnina dvojky, jinak si vstup doplníme
295 nulami, co¾ výsledný èas bìhu algoritmu zhor¹í maximálnì konstanta-krát.
297 Algoritmus bude rozdìlen na~dvì èásti. V~první èásti spoèítá chování
298 v¹ech {\I pøirozených blokù} -- tak budeme øíkat blokùm, jejich¾ velikost
299 je mocnina dvojky a pozice je dìlitelná velikostí. Nejprve v~konstantním
300 èase spoèítá chování blokù velikosti~1, ty pak spojí do dvojic, dvojice
301 zase do dvojic atd., obecnì v~$i$-tém kroku spoète chování v¹ech pøirozených
302 blokù velikosti~$2^i$.
304 V~druhé èásti pak dopoèítává pøenosy, a~to tak, aby v~$i$-tém kroku byly známy
305 pøenosy do~øádù dìlitelných~$2^{\log n - i}$. V~nultém kroku tedy pouze $c_0=0$
306 a~$c_n$, který spoèítá z~$c_0$ pomocí chování bloku $\left< 0,n \right>$.
307 V~prvním kroku pomocí $\left< 0,n/2 \right>$ dopoèítá $c_{n/2}$,
308 v~druhém pomocí $\left< 0,n/4 \right>$ spoèítá $c_{n/4}$ a pomocí
309 $\left< n/2,3/4\cdot n \right>$ dostane $c_{3/4\cdot n}$ atd.
310 Obecnì v~$i$-tém kroku pou¾ívá chování blokù velikosti $2^{\log n - i}$.
312 \s{Sèítací sí»} tedy bude vypadat takto:
314 \:$\Theta(1)$ hladin výpoètu chování blokù velikosti~1.
315 \:$\Theta(\log n)$ hladin poèítajících chování pøirozených blokù velikosti~$2^i$.
316 \:$\Theta(\log n)$ hladin dopoèítávajících pøenosy \uv{zahu¹»ováním}.
317 \:$\Theta(1)$ hladin na samotné seètení: $\forall i: z_i = x_i \oplus y_i \oplus c_i$.
320 \figure{deleni_bloku.eps}{Výpoèet pøenosu}{2.5in}
322 Algoritmus tedy pracuje v~èase $\Theta(\log n)$. Hradel je pou¾ito lineárnì: pøi
323 výpoètu chování blokù na jednotlivých hladinách poèet hradel exponenciálnì klesá
324 od~$n$ k~1, bìhem zahu¹»ování pøenosù naopak exponenciálnì stoupá od~1 k~$n$.
325 Obì geometrické øady se seètou na $\Theta(n)$.
327 \h{Paralelní násobení}
329 Je¹tì si rozmysleme, jak rychle by bylo mo¾né èísla násobit. Opìt se inspirujeme
330 ¹kolním algoritmem: pokud násobíme dvì $n$-ciferná èísla $x$ a~$y$, uvá¾íme
331 v¹ech~$n$ posunutí èísla~$y$, ka¾dé z~nich vynásobíme pøíslu¹nou èíslicí v~$y$
332 a výsledky posèítáme.
334 \figure{skolni_nasobeni.eps}{©kolní násobení}{2in}
336 Ve~dvojkové soustavì je to je¹tì jednodu¹¹í: násobení jednou èíslicí je prostý
337 {\csc and.} Paralelnì tedy vytvoøíme v¹echna posunutí a spoèítáme v¹echny {\csc and}y.
338 To v¹e stihneme za 1~takt výpoètu.
340 Zbývá seèíst $n$~èísel, z~nich¾ ka¾dé má $\Theta(n)$ bitù. Mohli bychom opìt
341 pou¾ít osvìdèený trik: sèítat dvojice èísel, pak dvojice souètù dvojic, atd.
342 Taková sí» by mìla tvar binárního stromu hloubky $\log n$, jeho¾ ka¾dý vrchol
343 obsahuje jednu sèítaèku a na tu, jak víme, postaèí $\Theta(\log n)$ hladin.
344 Celý výpoèet tedy bì¾í v~èase $\Theta(\log^2 n)$.
346 Jde to ale rychleji, pou¾ijeme-li jednoduchý, témìø kouzelnický trik.
347 Sestrojíme {\I kompresor} -- to bude obvod konstantní hloubky, který na~vstupu
348 dostane tøi èísla a vypoète z~nich dvì èísla mající stejný souèet jako zadaná
351 K~èemu je to dobré? Máme-li seèíst $n$~èísel, v~konstantním èase doká¾eme tento
352 úkol pøevést na seètení $\lceil 2/3\cdot n\rceil$ èísel, to pak opìt v~konstantním èase
353 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
354 zbudou dvì èísla a ta seèteme klasickou sèítaèkou. Zbývá vymyslet kompresor.
356 \s{Konstrukce kompresoru:}
357 Oznaème vstupy kompresoru $x$, $y$ a~$z$ a výstupy $p$ a~$q$.
358 Pro ka¾dý øád~$i$ spoèteme souèet $x_i + y_i + z_i$. To je nìjaké
359 dvoubitové èíslo, tak¾e mù¾eme jeho ni¾¹í bit prohlásit za~$p_i$
360 a vy¹¹í za~$q_{i+1}$.
362 Jinými slovy jsme v¹echna tøi èísla normálnì seèetli, ale místo abychom
363 pøenosy posílali do vy¹¹ího øádu, vytvoøili jsme z~nich dal¹í èíslo,
364 které má být k~výsledku èasem pøièteno.
366 \figure{add_3to2.eps}{Kompresor}{0.9in}
368 \s{Shrnutí:} Na¹e sí» pro paralelní násobení pracuje v~èase $\Theta(\log n)$
369 -- nejdøíve v~konstantním èase vytváøíme mezivýsledky, pak pou¾ijeme $\Theta(\log n)$
370 hladin kompresorù konstantní hloubky a nakonec jednu sèítaèku hloubky $\Theta(\log n)$.
371 Jistou vadou na kráse ov¹em je, ¾e na to potøebujeme $\Theta(n^2)$ hradel.
375 Je¹tì zkusíme paralelizovat jeden klasický problém, toti¾ tøídìní.
376 Budeme k~tomu pou¾ívat {\I komparátorovou sí»} -- to je hradlová sí»
377 slo¾ená z~{\I komparátorù.}
379 Jeden komparátor umí porovnat dvì hodnoty a~rozhodnout, která z~nich je vìt¹í
380 a~která men¹í. Nevrací v¹ak booleovský výsledek jako bì¾né hradlo, ale má dva
381 výstupy: na~jednom z~nich vrací men¹í ze~vstupních hodnot a~na~druhém tu vìt¹í.
383 \figure{sortnet.0}{Komparátor}{0.7in}
385 V~na¹em formalismu hradlových sítí bychom mohli komparátor reprezentovat dvojicí
386 hradel: jedno z~nich by poèítalo minimum, druhé maximum. Hodnoty, které tøídíme,
387 bychom prostì pova¾ovali za prvky abecedy.\foot{Komparátorovou sí» mù¾eme také snadno
388 pøelo¾it na booleovský obvod. Ka¾dý prvek abecedy reprezentujeme èíslem
389 o~$b=\lceil\log_2 \Sigma\rceil$ bitech. Zpùsobem podobným paralelní sèítaèce
390 lze z~booleovských hradel sestrojit komparátor hloubky $\Theta(\log b)$. Zkuste to.}
392 Je¹tì se dohodnìme, ¾e výstupy komparátorù se nikdy nebudou vìtvit. Ka¾dý
393 z~nich pøivedeme na~vstup jiného komparátoru nebo na~výstup sítì. Vìtvení
394 by nám ostatnì k~nièemu nebylo, proto¾e na~výstupu potøebujeme vydat stejný
395 poèet hodnot, jako byl na vstupu, a nemáme ¾ádné hradlo, kterým bychom mohli
396 pøípadných více vìtví slouèit opìt do~jedné.
398 \s{Pøíklad:} Zkusíme do øeèi komparátorových sítí pøelo¾it {\I bublinkové tøídìní.}
399 Z~nìj získáme obvod na~levém obrázku (¹ipky pøedstavují jednotlivé komparátory).
400 Toto nakreslení ov¹em ponìkud klame -- pokud sí» necháme poèítat, mnohá porovnání
401 budou probíhat paralelnì. Skuteèný prùbìh výpoètu znázoròuje pravý obrázek,
402 na~nìm¾ jsme v¹echny operace provádìné souèasnì znázornili vedle sebe.
403 Ihned vidíme, ¾e paralelní bublinkové tøídìní pracuje v~èase $\Theta(n)$
404 a potøebuje kvadratický poèet komparátorù.
406 \twofigures{sortnet.1}{Bubblesort}{143pt}{sortnet.2}{Skuteèný prùbìh výpoètu}{143pt}
408 Nyní si pøedvedeme rychlej¹í tøídící algoritmus. Pùjdeme na nìj jak se øíká \uv{od lesa}.
409 Nejdøíve vymyslíme sí», která bude umìt tøídit jenom nìco -- toti¾ bitonické posloupnosti.
410 Pak z~ní teprve sestrojíme obecné tøidìní. Bez újmy na obecnosti pøitom budeme
411 pøedpokládat, ¾e ka¾dé dva prvky na vstupu jsou navzájem rùzné a ¾e velikost vstupu
414 \s{Definice:} Posloupnost $x_0,\dots,x_{n-1} $ je {\I èistì bitonická,} pokud ji mù¾eme
415 rozdìlit na nìjaké pozici $k\in\{0, \dots, n-1\}$ tak, ¾e prvky $x_0,\ldots,x_k$ tvoøí rostoucí
416 poslopnost, zatímco prvky $x_k,\ldots,x_{n-1}$ tvoøí posloupnost klesající.
418 \s{Definice:} Posloupnost $x_0,\dots,x_{n-1}$ je {\I bitonická}, pokud ji lze získat
419 rotací (cyklickým posunutím) nìjaké èistì bitonické posloupnosti. Jinými slovy pokud existuje
420 $0\le j<n$ takové, ¾e posloupnost $x_j,x_{(j+1) \bmod n},\dots, x_{(j+n-1) \bmod n}$
423 \s{Definice:} {\I Separátor øádu~$n$} je komparátorová sí»~$S_n$ se vstupy $x_0,\ldots,x_{n-1}$
424 a výstupy $y_0,\ldots,y_{n-1}$, která dostane-li na~vstupu bitonickou posloupnost,
425 vydá na výstup její permutaci s~následujícími vlastnostmi:
428 \:$y_0,\ldots,y_{n/2-1}$ a $y_{n/2},\ldots,y_{n-1}$ jsou bitonické posloupnosti;
429 \:$y_i < y_j$, kdykoliv $0\le i<n/2$ a $n/2\le j<n$.
432 \>Jinak øeèeno, separátor rozdìlí bitonickou posloupnost na dvì polovièní
433 a navíc jsou v¹echny prvky v~první polovinì men¹í ne¾ v¹echny v~té druhé.
435 \s{Lemma:} Pro ka¾dé sudé~$n$ existuje separátor~$S_n$ konstantní hloubky,
436 slo¾ený z~$\Theta(n)$ komparátorù.
438 Dùkaz tohoto lemmatu si necháme na konec kapitoly. Nejprve pøedvedeme, k~èemu jsou
441 \s{Definice:} {\I Bitonická tøídièka øádu~$n$} je komparátorová sí»~$B_n$,
442 která dostane-li na vstupu bitonickou posloupnost délky~$n$, vydá ji setøídìnou.
444 \s{Lemma:} Pro libovolné $n=2^k$ existuje bitonická tøidièka~$B_n$ hloubky $\Theta(\log n)$
445 s~$\Theta(n\log n)$ komparátory.
448 Konstrukce bitonické tøidièky je snadná: nejprve separátorem~$S_n$ zadanou bitonickou
449 posloupnost rozdìlíme na dvì bitonické posloupnosti délky $n/2$,
450 pak ka¾dou z~nich separátorem~$S_{n/2}$ na dvì délky $n/4$, atd.,
451 a¾ získáme jednoprvkové bitonické posloupnosti ve~správném poøadí.
452 Celkem pou¾ijeme~$\log n$ hladin slo¾ených z~$n$ separátorù, ka¾dá
453 hladina má pøitom konstantní hloubku.
456 \figure{sortnet.5}{Bitonická tøidièka $B_n$}{\epsfxsize}
458 Bitonické tøidièky nám nyní pomohou ke~konstrukci tøidièky na obecné posloupnosti.
459 Ta bude zalo¾ena na tøídìní sléváním -- nejprve se tedy musíme nauèit slít dvì
460 setøídìné posloupnosti do jedné.
462 \s{Definice:} {\I Slévaèka øádu~$n$} je komparátorová sí»~$M_n$ s~$2\times n$
463 vstupy a~$n$ výstupy, která dostane-li dvì setøídìné posloupnosti délky~$n$,
464 vydá posloupnost vzniklou jejich slitím.
466 \s{Lemma:} Pro $n=2^k$ existuje slévaèka~$M_n$ hloubky $\Theta(\log n)$
467 s~$\Theta(n\log n)$ komparátory.
470 Staèí jednu vstupní posloupnost obrátit a \uv{pøilepit} za tu druhou. Tím vznikne
471 bitonická posloupnost, jí¾ setøídíme bitonickou tøidièkou~$B_{2n}$.
474 \s{Definice:} {\I Tøídící sí» øádu~$n$} je komparátorová sí»~$T_n$ s~$n$~vstupy
475 a~$n$~výstupy, která pro ka¾dý vstup vydá jeho setøídìnou permutaci.
477 \s{Lemma:} Pro $n=2^k$ existuje tøídící sí»~$T_n$ hloubky $\Theta(\log^2 n)$
478 slo¾ená z~$\Theta(n\log^2 n)$ komparátorù.
481 Sí» bude tøídit sléváním. Vstup rozdìlí na~$n$ jednoprvkových posloupností.
482 Ty jsou jistì setøídìné, tak¾e je slévaèkami~$M_1$ mù¾eme slít do dvouprvkových
483 setøídìných posloupností. Na ty pak aplikujeme slévaèky $M_2$, $M_4$, \dots, $M_{n/2}$,
484 a¾ v¹echny èásti slijeme do jedné, setøídìné.
486 Celkem provedeme $\log n$~krokù slévání, $i$-tý z~nich obsahuje slévaèky $M_{2^i}$
487 a ty, jak u¾ víme, mají hloubku $\Theta(i)$. Celkový poèet vrstev tedy èiní
488 $\Theta(1+2+3+\ldots+\log n) = \Theta(\log^2 n)$. Ka¾dý krok pøitom potøebuje
489 $\Theta(n\log n)$ komparátorù, co¾ dává celkem $\Theta(n \log^2 n)$ komparátorù.
492 \figure{sortnet.6}{Tøidièka $T_8$}{\epsfxsize}
494 \s{Konstrukce separátoru:} Zbývá dokázat, ¾e existují separátory konstantní
495 hloubky. Vypadají pøekvapivì jednodu¹e: pro $i=0,\ldots,n/2-1$ zapojíme
496 komparátor se vstupy $x_i$, $x_{i+n/2}$, jeho¾ minimum pøivedeme na~$y_i$
497 a maximum na~$y_{i+n/2}$.
499 \figure{sortnet.3}{Konstrukce separátoru}{\epsfxsize}
501 Proè separátor separuje? Nejprve pøedpokládejme, ¾e vstupem je èistì bitonická
502 posloupnost. Oznaème~$m$ polohu maxima této posloupnosti; maximum bez újmy
503 na obecnosti le¾í v~první polovinì (jinak celý dùkaz provedeme \uv{zrcadlovì}).
504 Oznaème dále~$k$ nejmen¹í index, pro který komparátor mezi $x_k$ a~$x_{k+n/2}$
505 hodnoty prohodí, tedy $k=\min \{ i \mid x_i > x_{i+n/2} \}.$
507 Jeliko¾ maximum je jedineèné, musí platit $x_m > x_{m+n/2}$, tak¾e~$k$
508 existuje a navíc $0\le k\le m < n/2$. Také platí, ¾e pro ka¾dé~$i$ mezi
509 $k$ a~$n/2$ u¾ komparátory musí prohazovat, proto¾e od~$x_k$ je posloupnost
510 a¾ do konce klesající, tak¾e $x_i > x_{i+n/2}$.
512 Separátor se tedy chová velice jednodu¹e: první polovina výstupu vznikne
513 slepením rostoucího úseku $x_0,\ldots,x_{k-1}$ s~klesajícím úsekem $x_{n/2+k},\ldots,x_{n-1}$;
514 druhou polovinu tvoøí spojení klesajícího úseku $x_{n/2},\ldots,x_{n/2+k-1}$, rostoucího
515 úseku $x_k,\ldots,x_m$ a klesajícího úseku $x_m,\ldots,x_{n/2-1}$. První polovina
516 je èistì bitonická a jeliko¾ $x_{n/2-1} > x_{n/2}$, je druhá polovina bitonická
517 (ov¹em obvykle ne èistì).
519 \figure{sortnet.7}{Ilustrace èinnosti separátoru}{\epsfxsize}
521 Doplòme, co se stane, pokud vstup není èistì bitonický. Zde vyu¾ijeme
522 toho, ¾e pokud vstup separátoru zrotujeme o~$p$ pozic, dostaneme o~$p$ pozic
523 zrotované i obì poloviny výstupu. Podle definice ov¹em pro ka¾dou bitonickou
524 posloupnost existuje její rotace, která je èistì bitonická, a~pro ní¾, jak
525 u¾ víme, separátor funguje. Tak¾e pro neèistou bitonickou posloupnost musí
526 vydat výsledek pouze zrotovaný, co¾ ov¹em na jeho správnosti nic nemìní.
529 Ukázali jsme tedy paralelní tøídící algoritmus o~slo¾itosti $\Theta(\log^2 n)$
530 slo¾ený z~$\Theta(n\log^2 n)$ komparátorù.
532 Dodejme je¹tì, ¾e existuje i~tøídicí algoritmus, kterému staèí jen $\O(\log n)$
533 hladin. Jeho multiplikativní konstanta je v¹ak pøíli¹ veliká, tak¾e je v~praxi