3 \prednaska{5}{Paralelní sèítání, bitonické tøídìní}{(zapsal: Petr Jankovský)}
5 Minule jsme si zavedli paralelní výpoèetní model, ve kterém si nyní nìco naprogramujeme \dots
7 \h{Sèítání binárních èísel}
9 Mìjme dvì èísla $x$ a $y$ zapsané ve~dvojkové soustavì. Jejich èíslice oznaème
10 $x_{n-1}\ldots x_0$ a $y_{n-1}\ldots y_0$, kde $i$-tý øád má váhu $2^i$. Nyní budeme chtít tato èísla
13 K tomuto úèelu se~ihned nabízí pou¾ít starý dobrý \uv{¹kolní algoritmus}, který
14 funguje ve~dvojkové soustavì stejnì dobøe jako v~desítkové. Zkrátka sèítáme èísla
15 zprava doleva. V¾dy seèteme pøíslu¹né èíslice pod~sebou a~pøièteme pøenos z~ni¾¹ího
16 øádu. Tím dostaneme jednu èíslici výsledku a~pøenos do~vy¹¹ího øádu. Formálnì
17 bychom to mohli zapsat tøeba takto:
19 z_i=x_i \oplus y_i \oplus c_i,
21 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}
22 z~$(i-1)$-ního øádu do~$i$-tého. Pøenos pøitom nastane tehdy, pokud se~nám potkají
23 dvì jednièky pod~sebou, nebo kdy¾ se~vyskytne alespoò jedna jednièka a~k~tomu
24 pøenos z~ni¾¹ího øádu. Jinými slovy tehdy, kdy¾ ze~tøí xorovaných èíslic jsou alespoò
25 dvì jednièky (pomocí obvodu pro majoritu z minulé pøedná¹ky lehce zkonstruujeme):
29 c_{i+1} &= (x_i~\&~y_i)\lor(x_i~\&~c_i)\lor(y_i~\&~c_i).\cr
33 Takovéto sèítání sice perfektnì funguje, nicménì je bohu¾el pomìrnì pomalé.
34 Pokud bychom stavìli hradlovou sí» podle tohoto pøedpisu, byla by slo¾ená z~nìjakých
35 podsítí (\uv{krabièek}), které budou mít na~vstupu $x_i$, $y_i$ a~$c_i$ a jejich výstupem
36 bude $z_i$ a~$c_{i+1}$.
38 \figure{hloupe_scitani.eps}{Sèítání ¹kolním algoritmem.}{1.5in}
40 V¹imìme si, ¾e~ka¾dá krabièka závisí na~výstupu té pøedcházející. Jednotlivé
41 krabièky tedy musí urèitì le¾et na~rùzných hladinách. Celkovì bychom museli pou¾ít
42 $\Theta{(n)}$ hladin a~jeliko¾ je ka¾dá krabièka konstantnì velká, také $\Theta{(n)}$ hradel. To dává
43 lineární èasovou i~prostorovou slo¾itost, èili oproti sekvenènímu algoritmu jsme si nepomohli.
45 Zamysleme se nad tím, jak by se proces sèítání mohl zrychlit.
48 Jediné, co nás pøi sèítání brzdí, jsou pøenosy mezi jednotlivými øády. Ka¾dý øád,
49 aby~vydal souèet, musí poèkat na~to, a¾~dopoèítají v¹echny pøedcházející øády.
50 Teprve pak se~toti¾ dozví pøenos. Kdybychom ov¹em pøenosy dokázali spoèítat
51 nìjakým zpùsobem paralelnì, máme vyhráno. Jakmile známe v¹echny pøenosy, souèet
52 u¾~zvládneme dopoèítat na~konstantnì mnoho hladin -- tedy v~konstantním èase.
54 Podívejme se na~libovolný {\I blok} v~na¹em souètu. Tak budeme øíkat èíslùm
55 $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.
57 \figure{blok_scitani.eps}{Blok souètu.}{3in}
59 Z tohoto pohledu se mù¾eme na blok také dívat jako na nìjakou funkci, která
60 dostane jednobitový vstup a vydá jednobitový výstup. To je nám pøíjemné, nebo»
61 takových funkcí existují jenom ètyøi typy:
65 \:$f(x) = x$, ~~~~($<$ -- kopírování)
68 Jak se za~chvíli uká¾e, poslední pøípad, kdy by~nìjaký blok pøedával opaèný
69 pøenos, ne¾ do~nìj vstupuje, navíc nikdy nemù¾e nastat. Pojïme si to rozmyslet.
70 Jednobitové bloky se chovají velice jednodu¹e:
72 \figure{bloky_1bit.eps}{Tabulka triviálních blokù.}{1.1in}
74 Z prvního bloku evidentnì v¾dy vyleze 0, a»~do~nìj vstoupí jakýkoli pøenos.
75 Poslední blok naopak sám o~sobì pøenos vytváøí, a»~ji¾ do~nìj vleze jakýkoliv.
76 Bloky prostøední se chovají stejnì, a~to tak, ¾e~samy o~sobì ¾ádný pøenos nevytvoøí,
77 ale~pokud do~nich nìjaký pøijde, tak~také odejde.
79 Mìjme nyní nìjaký vìt¹í blok~$C$ slo¾ený ze~dvou men¹ích podblokù $A$ a~$B$, jejich¾
80 chování u¾ známe. Z~toho mù¾eme odvodit, jak se chová celý blok:
82 \figure{tabulka_skladani_bloku.eps}{Skládání chování blokù.}{1.3in}
84 Pokud vy¹¹í blok pøenos pohlcuje, pak a»~se u¾~ni¾¹í blok chová jakkoli, slo¾ení
85 tìchto blokù musí v¾dy pohlcovat. V~prvním øádku tabulky jsou tudí¾ nuly. Analogicky,
86 pokud vy¹¹í blok generuje pøenos, tak~ten ni¾¹í na~tom nic nezmìní. V~druhém
87 øádku tabulky jsou tedy samé jednièky. Zajímavìj¹í pøípad nastává, pokud vy¹¹í blok
88 kopíruje -- tehdy zále¾í èistì na~chování ni¾¹ího bloku.
90 V¹imnìme si, ¾e~skládání chování blokù je vlastnì úplnì obyèejné skládání
91 funkcí. Nyní bychom mohli prohlásit, ¾e~budeme poèítat nad~tøíprvkovou abecedou,
92 a~¾e~celou tabulku doká¾eme spoèítat jedním jediným hradlem. Pojïmì si v¹ak
93 rozmyslet, jak~bychom takovouto vìc popsali èistì binárnì. Jak tedy tyto tøi stavy
94 popisovat pouze nìkolika bity?
96 Evidentnì nám k tomuto binárnímu zakódování tøí stavù budou staèit bity dva.
97 Oznaème si je jako $p$ a $q$. Tato dvojice mù¾e nabývat hned ètyø mo¾ných hodnot,
98 kterým pøiøadíme tøi mo¾ná chování bloku. Toto kódování mù¾eme zvolit zcela
99 libovolnì, ale pokud si ho zvolíme ¹ikovnì, u¹etøíme si dále práci pøi kompozici.
100 Zvolme si tedy kódování takto:
108 Tomu, ¾e blok kopíruje, odpovídá dvojice $p = 1$; $q =$ \<cokoliv>. V~ostatních
109 pøípadech bude~$p$ nulové a~$q$ nám bude øíkat, co je na~výstupu pøíslu¹ného bloku.
110 Jinými slovy $p = 0$ znamená, ¾e funkce je konstanta, pøièem¾ $q$ øíká jaká; naproti
111 tomu $p = 1$~znamená, ¾e funkce je identita, a»~u¾~je $q$ cokoli.
113 Pojïme si nyní ukázat, jak bude celé skládání blokù vypadat. Rozmysleme si,
114 kdy je~$p$ celého dvojbloku jednièkové, tedy kdy celý dvojblok kopíruje. To nastane
115 tehdy, pokud kopírují obì jeho èásti, a tedy $p = p_a~\&~p_b$. Dále $q$ bude rovno jednièce,
116 pokud $q = (\neg{p_a}~\&~q_a) \lor (p_a~\&~q_b)$.
118 Skládání chování blokù lze tedy popsat buï ternárnì -- tabulkou, ale lze to
119 i~binárnì vý¹e uvedeným pøedpisem.
121 Nyní si tedy mù¾eme dopøedu vypoèítat chování bloku velikosti jedna, poté
122 z~nich skládáním blokù velikosti dva, dál velikosti ètyøi, osm, atd \dots
124 \h{Paralelní sèítání}
126 Paralelní algoritmus na~sèítání u¾~zkonstruujeme pomìrnì snadno. Bez újmy
127 na~obecnosti budeme pøedpokládat, ¾e~poèet bitù vstupních èísel je mocnina dvojky,
128 jinak si vstup doplníme nulami, co¾ výsedný èas bìhu algoritmu zhor¹í maximálnì
132 \:Spoèteme chování blokù velikosti~1. ($\O(1)$ hladin)
133 \:Postupnì poèítáme chování blokù\foot{myslíme \uv{pøirozenì zarovnané} bloky, tedy takové, jejich¾ poloha je násobkem velikosti} velikosti 2, 4, 8, ..., $2^k$.
134 ($\O(\log n)$ hladin, na~nich¾ se skládají bloky)
135 \:$c_0 \leftarrow 0$ (pøenos do nejni¾¹ího øádu je v¾dy 0)
136 \:Urèíme $c_n$ podle $c_0$ a chování (jediného) bloku velikosti~$n$.
137 \:Postupnì dopoèítáme pøenosy na~hranicích dìlitelných $2^k$ \uv{zahu¹»ováním}:
138 jakmile víme $c_{2^k}$, mù¾eme dopoèítat $c_{2^k+2^{k-1}}$ podle
139 chování bloku $\left< 2^k, 2^k+2^{k-1}\right>$. ($\O(\log n)$ hladin,
140 na~nich¾ se dosazuje)
141 \:Seèteme: $\forall i: z_i = x_i \oplus y_i \oplus c_i$.
144 \figure{1_9_deleni_bloku.eps}{Výpoèet pøenosu.}{2.5in}
146 Algoritmus pracuje v~èase $\O(\log n)$. Hradel je pou¾ito lineárnì: na~jednotlivých
147 hladinách kroku~2 poèet hradel exponenciálnì klesá od~$n$ k~1, na~hladinách kroku~5
148 exponenciálnì stoupá od~1 k~$n$, tak¾e dohromady se seète na~$\Theta(n)$.
152 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.
154 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.
156 \s{Definice:} {\I Komparátorová sí»} je kombinaèní obvod, jeho¾ hradla jsou
159 \figure{sortnet.0}{Komparátor}{0.7in}
161 Komparátor umí porovnat dvì hodnoty a~rozhodnout, která z~nich je vìt¹í
162 a~která men¹í. Nevrací v¹ak booleovský výsledek jako bì¾né hradlo, ale má dva
163 výstupy, pøièem¾ na~jednom vrátí men¹í ze~vstupních hodnot a~na~druhém vìt¹í.
165 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é.)
167 \s{Pøíklad:} {\sl Bubble sort}
169 Obrázek Bubble 1 ilustruje pou¾ití komparátorù pro tøídìní Bubble sortem.
170 ©ipky pøedstavují jednotlivé komparátory. Výpoèet v¹ak je¹tì mù¾eme vylep¹it.
172 \twofigures{sortnet.1}{Bubble 1}{143pt}{sortnet.2}{Bubble 2}{143pt}
174 Sna¾íme se výpoèet co nejvíce paralelizovat (viz obrázek Bubble 2).
175 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.
177 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.
180 \s{Definice:} Øekneme, ¾e posloupnost $x_0,\dots,x_{n-1} $ je {\I èistì bitonická} právì tehdy, kdy¾
181 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)
182 tvoøí rostoucí poslopnost, kde¾to prvky stojící za~ním tvoøí poslopnost klesající.
183 Formálnì zapsáno musí platit, ¾e:
184 $$x_0\leq x_1\leq \dots \leq x_k \geq x_{k+1}\geq\dots \geq x_{n-1}.$$
186 \s{Definice:} Posloupnost $x_0 \dots x_{n-1}$ je {\I bitonická}, právì kdy¾ $\exists~j\in \{0,\dots ,n-1\}$, pro
187 které je rotace pùvodní posloupnosti o $j$ prvkù, tedy posloupnost
188 $$x_j,x_{(j+1) \bmod n},\dots, x_{(j+n-1) \bmod n},$$ èistì bitonická.
190 \s{Definice:} {\I Separátor $S_n$} je sí», ve které jsou v¾dy~$i$-tý a~$(i+{n/2})$-tý prvek vstupu
191 (pro $i=0,\dots, {n/2}-1$) propojeny komparátorem. Minimum se pak stane~$i$-tým,
192 maximum $(i+{n/2})$-tým prvkem výstupu.
193 \figure{sortnet.3}{$(y_i, y_{i+{n/2}}) = \<CMP>(x_i, x_{i+{n/2}})$} {300pt}
195 \s{Lemma:} Pokud separátor dostane na~vstupu bitonickou posloupnost, pak jeho výstup $y_0, \dots, y_{n-1}$
198 (i) $y_0,\dots, y_{n/2 -1}$ a~$y_{n/2},\dots, y_{n-1}$ jsou
199 bitonické posloupnosti,
201 (ii) Pro v¹echna $i,j< {n/2}$ platí $y_i < y_{j + {n/2}}$.
203 Separátor nám tedy jednu bitonickou posloupnost na~vstupu rozdìlí na~dvì
204 bitonické posloupnosti, pøièem¾ navíc ka¾dý prvek první posloupnosti ($y_0,\dots, y_{n/2 -1}$)
205 je men¹í nebo roven prvkùm druhé posloupnosti ($y_{n/2}, \dots, y_{n-1}$).
207 \>Ne¾ pøistoupíme k dùkazu lemmatu, uka¾me si, k èemu se nám bude hodit.
210 \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$.
212 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.
214 \centerline{\epsfbox{sortnet.5}}
216 Jak je vidìt, bitonická tøídièka nám libovolnou bitonickou posloupnost délky~$n$
217 setøídí na~$\Theta(\log n)$ hladin.
219 Nyní se dá odvodit, ¾e pokud umíme tøídit bitonické posloupnosti, umíme setøídit v¹echno.
220 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.
222 \s{Pøíklad:} {\sl Merge sort}
224 Bitonická tøídièka se tedy dá pou¾ít ke~slévání setøídìných posloupností.
225 Uka¾me si, jak s~její pomocí sestavíme souèástky {\I slévaèky} $M_n$:
227 Setøídìné posloupnosti $x_0,\dots, x_{n-1}$ a~$y_0,\dots, y_{n-1}$ spojíme do jedné bitonické
228 posloupnosti $x_0,\dots, x_{n-1},y_{n-1},\dots, y_0$. Z~této posloupnosti vytvoøíme pomocí bitonické tøídièky
229 $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í.
230 \figure{sortnet.6}{Paralelní MergeSort.}{3in}
232 Nyní se pokusme odhadnout èasovou slo¾itost. Ná¹ MergeSort bude mít øádovì hloubku blokù $\log n$.
233 V ka¾dém bloku $M_n$ je navíc ukryta bitonická tøídièka s takté¾ logaritmickou hloubkou.
234 Celková hloubka tedy bude $\log 2 + \log4 + \dots + \log 2^k + \dots + \log n$.
235 Po seètení nakonec dostáváme výslednou èasovou slo¾itost $\Theta (\log^2 n)$.
237 Dodejme je¹tì, ¾e existuje i~tøídicí algoritmus, kterému staèí jen ${\O}(\log n)$ hladin.
238 Jeho multiplikativní konstanta je v¹ak pøíli¹ veliká, tak¾e je v~praxi nepou¾itelný.
240 Vra»me se nyní k dùkazu lemmatu, který jsme na pøedminulé stránce vynechali.
243 (i) Nejprve nahlédneme, ¾e lemma platí, je-li vstupem èistì bitonická
244 posloupnost. Dále BÚNO pøedpokládejme, ¾e vrchol posloupnosti je v~první polovinì (kdyby
245 byl vrchol za~polovinou, staèilo by zrcadlovì obrátit posloupnost i~komparátory a~øe¹ili
246 bychom stejný problém). Nyní si definujme $k := \min j: x_j > x_{j+n/2}$. (Pokud
247 by~takové~$k$ neexistovalo, znamenalo by~to, ¾e vstupní posloupnost je monotónní.
248 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,
249 ¾e jakmile jednou zaène platit, ¾e prvek na~levé stranì je men¹í ne¾ na~pravé, bude
250 nám tato relace platit a¾~do~konce. Oznaème vrchol vstupní posloupnosti jako~$x_m$.
251 Pak~$k$ bude jistì men¹í ne¾~$m$ a~$k+{n/2}$ bude vìt¹í ne¾~$m$. Mezi~$k$ a~$m$ je tedy
252 vstupní posloupnost neklesající, mezi $k+{n/2}$ a~$n-1$ nerostoucí.
254 Do pozice~$k$ tedy separátor bude pouze kopírovat vstup na~výstup, od~pozice~$k$
255 dál u¾~jen prohazuje. Pro ka¾dé~$i$, $(k\leq i\leq {n/2}-1)$ se prvky
256 $x_i$ a~$x_{i+{n/2}}$ prohodí. Úsek mezi~$k$ a~${n/2}-1$ tedy
257 nahradíme nerostoucí posloupností, první polovina výstupu tedy bude
258 (dokonce èistì) bitonická. Podobnì úsek $k+{n/2}$ a¾~$n-1$ nahradíme èistì
259 bitonickou posloupností. Obì poloviny tedy budou bitonické.
261 Dostaneme-li na vstupu obecnou bitonickou posloupnost, pøedstavíme si,
262 ¾e je to èistì bitonická posloupnost zrotovaná o~$r$ prvkù (BÚNO
263 doprava). Zjistíme, ¾e v~komparátorech se porovnávají tyté¾ prvky,
264 jako kdyby zrotovaná nebyla. Výstup se od výstupu èistì bitonické
265 posloupnosti zrotovaného o~$r$ bude li¹it prohozením úsekù $x_0$ a¾
266 $x_{r-1}$ a~$x_{n/2}$ a¾ $x_{{n/2}+r-1}$. Obì výstupní
267 posloupnosti tedy budou zrotované o~$r$ prvkù, ale na jejich
268 bitoniènosti se nic nezmìní.
270 (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).
275 \centerline{\epsfbox{sortnet.7}}
278 \h{Paralelní násobení}
280 Podobnì jako u~sèítání si vzpomeneme na~¹kolní algoritmus -- tentokráte v¹ak pro násobení.
281 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
282 {\sc and} ) a~nakonec potøebujeme výsledných~$n$ èísel seèíst.
283 \figure{skolni_scitani.eps}{©kolní sèítání.}{2in}
285 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.
286 \figure{stromecek.eps}{Stromeèek}{1.4in}
288 Toto øe¹ení by v¹ak vedlo na~èasovou slo¾itost $\Theta (\log^2 n)$. To je sice dle na¹ich mìøítek
289 docela efektivní, ale pøekvapivì to jde je¹tì lépe -- toti¾ na~$\Theta (\log n)$ hladin. Této
290 slo¾itosti dosáhneme malým trikem.
292 Vymyslíme obvod konstantní hloubky, který na~vstupu dostane tøi èísla. Odpoví pak dvìma èísly
293 takovými, ¾e budou mít stejný souèet jako pùvodní tøi èísla. Jinými slovy pomocí
294 tohoto obvodu budeme umìt seètení tøí èísel pøevést na seètení dvou èísel.
296 \figure{obvod.eps}{$x+y+z = p+q$}{0.3in}
298 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$.
300 \figure{obvod_real.eps}{Redukování sèítání}{1.2in}
302 Toto zredukování sèítání nám nyní umo¾ní opìt stavit strom, by» o malièko slo¾itìj¹í.
304 \figure{sl_stromecek.eps}{Slo¾itìj¹í stromeèek}{0.9in}
306 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.
308 Seètení v¹ech $n$ èísel tedy zabere $\Theta (\log n)$ hladin.
310 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.