Hradla: Prepsano podle dnesni prednasky

[ads2.git] / 5-hradla / 5-hradla.tex

\input ../lecnotes.tex

\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).

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,
které dneska najdeme ve~svých stolních poèítaèích, nejsou nic jiného ne¾
víceprocesorový systém na jednom èipu.

Nabízí se tedy obtí¾nou úlohu rozdìlit na nìkolik èástí, nechat ka¾dý
procesor (èi jádro) poèítat jednu z~èástí a nakonec jejich výsledky spojit
dohromady. To se snadno øekne, ale s~výjimkou triviálních úloh u¾ obtí¾nìji
provede.

Pojïme se podívat na nìkolik zajímavých paralelních algoritmù. Abychom se
nemuseli zabývat detaily hardwaru konkrétního víceprocesorového poèítaèe,
zavedeme si pomìrnì abstraktní výpoèetní model, toti¾ hradlové sítì. Tento
model je daleko paralelnìj¹í ne¾ skuteèný poèítaè, ale pøesto se techniky,
které si uká¾eme, dají snadno vyu¾ít i prakticky. Konec koncù sama vnitøní
architektura procesorù se na¹emu modelu velmi podobá.

\h{Hradlové sítì}

Hradlové sítì jsou tvoøeny navzájem propojenými {\I hradly.} Ka¾dé hradlo pøitom
poèítá nìjakou (obecnì libovolnou) funkci $\Sigma^k \rightarrow \Sigma$, kde~$\Sigma$
je koneèná abeceda (stejná pro celou sí») a~$k$ pøirozené èíslo (poèet vstupù hradla,
jinak té¾ jeho {\I arita}).

\s{Pøíklad:} Èasto studujeme hradla {\I booleovská} (pracující nad abecedou $\Sigma=\{0,1\}$).
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
\endlist

Propojením hradel pak vznikne {\I hradlová sí».} Ne¾ vyøkneme formální definici,
pojïme se podívat na pøíklad jedné takové sítì:

\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
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
vytváøet cykly.

Nyní toté¾ formálnìji:

\s{Definice:} {\I Hradlová sí»} je urèena:
\itemize\ibull
\:{\I abecedou} $\Sigma$, co¾ je nìjaká koneèná mno¾ina symbolù;
\:po dvou disjunktními koneènými mno¾inami \hfil\break
  $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.}
\:zobrazením~$F$, které ka¾dému hradlu $h\in H$ pøiøadí nìjakou funkci~$F(h):
  \Sigma^{a(h)} \rightarrow \Sigma$, co¾ je funkce, kterou toto hradlo vykonává.
  Èíslu $a(h)$ øíkáme {\I arita} hradla~$h$;
\:zobrazením~$z: E \rightarrow {\bb N}$, je¾ o~hranách vedoucích do hradel øíká,
  kolikátému argumentu funkce odpovídají;\foot{Na hranách vedoucích do výstupù
  necháváme hodnotu této funkce nevyu¾itu.}
\endlist

\>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).}
\endlist

\s{Poznámka:} Nìkdy se hradlovým sítím také øíká {\I kombinaèní obvody} a pokud pracují
nad abecedou $\Sigma = \{0,1\}$, pak {\I booleovské obvody}.

\s{Definice:} {\I Výpoèet sítì} postupnì pøiøazuje hodnoty z~abecedy~$\Sigma$
vrcholùm grafu. Výpoèet probíhá po~{\I taktech.} V~nultém taktu jsou definovány
pouze hodnoty na~vstupech sítì a v~hradlech arity~0 (konstanty). V~ka¾dém
dal¹ím taktu pak ohodnotíme vrcholy, jejich¾ v¹echny vstupní hrany vedou
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
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
se zastaví a~sí» vydá výsledek -- ohodnocení výstupù.

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$,
pro~které nejdel¹í z~cest z~libovolného vrcholu se~vstupním stupnìm~0
do~$v$ má délku rovnou právì~$i$.

\figure{vypocet_site.eps}{Prùbìh výpoètu a rozdìlení sítì na vrstvy}{6cm}

\s{Pár pozorování} o~prùbìhu výpoètu:

\itemize\ibull
\:V~$i$-té vrstvì jsou tedy právì ty vrcholy, které poprvé ohodnotíme v~$i$-tém
  taktu výpoètu.
\:Jeliko¾ sí» je acyklická, tak platí, ¾e jakmile vrchol ohodnotíme, u¾ se
  jeho ohodnocení nikdy nemù¾e zmìnit.
\:Kdy¾ se vydáme z~libovolného vrcholu proti smìru hran, po~koneènì mnoha
  krocích dojdeme do~vrcholu s~nulovým vstupním stupnìm (vstupu sítì nebo
  konstantního hradla). Proto ka¾dý vrchol le¾í v~nìjaké vrstvì.
\:Vrstvy jsou disjunktní, tak¾e poèet neprázdných vrstev je nutnì koneèný.
  V~kombinaci s~pøedchozím pozorováním dostaneme, ¾e výpoèet sítì se v¾dy zastaví.
\:Navíc poslední neprázdná vrstva je právì ta, kde se výpoèet zastaví -- z~ka¾dého
  dal¹ího vrcholu by toti¾ bylo mo¾né po~hranách dojít do vrcholu s~výstupním
  stupnìm~0 a jediné takové vrcholy jsou výstupy sítì. Ty by tedy musely také
  le¾et v~nìkteré z~následujících vrstev, co¾ ov¹em není mo¾né, nebo» výpoèet
  se u¾ zastavil.
\endlist

\>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.

\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é
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.

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}.

\s{Poznámka o~uniformitì:}
Dodejme, ¾e od~bì¾ných výpoèetním modelùm, 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.
(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ì.)

\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}.

\>{\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
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í.

\twofigures{hloupy_or.eps}{Sériové øe¹ení}{1in}{chytry_or.eps}{Paralelní øe¹ení}{3in}

\h{Sèítání binárních èísel}

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$.

K~seètení se~ihned nabízí pou¾ít starý dobrý \uv{¹kolní algoritmus sèítání pod sebou}, který
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í
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:
$$
\eqalign{
c_{0} &= 0, \cr
c_{i+1} &= (x_i~\&~y_i)\lor(x_i~\&~c_i)\lor(y_i~\&~c_i).\cr
}
$$

O~tomto pøedpisu snadno doká¾eme, ¾e funguje (zkuste si to), nicménì pokud podle
nìj postavíme hradlovou sí», bude pomìrnì pomalá. Sí» si mù¾eme pøedstavit tak,
¾e je slo¾ena z~nìjakých podsítí (\uv{krabièek}), které budou mít na~vstupu $x_i$,
$y_i$ a~$c_i$ a jejich výstupem bude $z_i$ a~$c_{i+1}$:

\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.

\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)$.
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
$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.

\figure{blok_scitani.eps}{Blok souètu}{3in}

Pro konkrétní sèítance se tedy mù¾eme na blok dívat jako na nìjakou funkci,
která dostane jednobitový vstup (pøenos zespoda) a vydá jednobitový výstup (pøenos
nahoru). To je nám milé, nebo» takové funkce existují pouze ètyøi:
$$\vbox{\halign{$f(x) = #$\hfil &\qquad # \hfil\cr
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
}}$$
Této funkci budeme øíkat {\I chování} pøíslu¹ného bloku.

{\I Jednobitové bloky} se pøitom chovají velice jednodu¹e:

\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øí,
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:

\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,
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:
$$
  (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ì:
$$\eqalign{
   p_B &= p_H \land p_D,\cr
   q_B &= (\neg{p_H} \land q_H) \lor (p_H \land q_D).
}$$

\h{Paralelní sèítání}

Z~popisu chování blokù u¾ je 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.

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$.

V~druhé èásti pak dopoèítává 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~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 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}

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á
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)$.

\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.

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.

Seètení v¹ech $n$ èísel tedy zabere $\Theta (\log n)$ hladin.

Kdy¾ se nyní vrátíme k~násobení, zbývá nám vyøe¹it posouvání a~{\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.

\bye