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