From 4692c5ca083d0ea1c0eab3e52f5a52bf22c4f5c6 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Wed, 9 Dec 2009 23:44:12 +0100 Subject: [PATCH] Dalsi revize. --- 5-addsort/5-addsort.tex | 85 ++++++++++++++++++++++------------------- 1 file changed, 46 insertions(+), 39 deletions(-) diff --git a/5-addsort/5-addsort.tex b/5-addsort/5-addsort.tex index 4e8bf81..d4c400e 100644 --- a/5-addsort/5-addsort.tex +++ b/5-addsort/5-addsort.tex @@ -2,15 +2,17 @@ \prednaska{5}{Paralelní sèítání, bitonické tøídìní}{(zapsal: Petr Jankovský)} +Minule jsme si zavedli paralelní výpoèetní model, ve kterém si nyní nìco naprogramujeme \dots + \h{Sèítání binárních èísel} Mìjme dvì èísla $x$ a $y$ zapsané ve~dvojkové soustavì. Jejich èíslice oznaème -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 +$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 seèíst. K tomuto úèelu se~ihned nabízí pou¾ít starý dobrý \uv{¹kolní algoritmus}, který funguje ve~dvojkové soustavì stejnì dobøe jako v~desítkové. Zkrátka sèítáme èísla -od~prava doleva. V¾dy seèteme pøíslu¹né èíslice pod~sebou a~pøièteme pøenos z~ni¾¹ího +z~prava doleva. V¾dy seèteme pøíslu¹né èíslice pod~sebou 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: $$ @@ -20,22 +22,22 @@ kde $z_i$ je $i$-t 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. Jinými slovy tehdy, kdy¾ ze~tøí xorovaných èíslic jsou alespoò -dvì jednièky (pomocí obvodu pro Majoritu z minulé pøedná¹ky lehce zkonstruujeme): +dvì jednièky (pomocí obvodu pro majoritu z minulé pøedná¹ky lehce zkonstruujeme): $$ \eqalign{ -c_{0} &= 0 \cr +c_{0} &= 0, \cr c_{i+1} &= (x_i~\&~y_i)\lor(x_i~\&~c_i)\lor(y_i~\&~c_i).\cr } $$ Takovéto sèítání sice perfektnì funguje, nicménì je bohu¾el pomìrnì pomalé. Pokud bychom stavìli hradlovou sí» podle tohoto pøedpisu, byla by slo¾ená z~nìjakých -podsítí (\uv{krabièek}), které budou mít na~vstupu $x_i$, $y_i$ a~$c_i$, jejich výstupem +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} -V¹imìme si, ¾e~ka¾dá krabièka závisí na~výstupu té pøedcházející. V¹echny +V¹imìme si, ¾e~ka¾dá krabièka závisí na~výstupu té pøedcházející. Jednotlivé krabièky tedy musí urèitì le¾et na~rùzných hladinách. Celkovì bychom museli pou¾ít $\Theta{(n)}$ hladin a~jeliko¾ je ka¾dá krabièka konsantnì velká, také $\Theta{(n)}$ hradel. To dává lineární èasovou i~prostorovou slo¾itost, èili oproti sekvenènímu algoritmu jsme si nepomohli. @@ -92,7 +94,7 @@ rozmyslet, jak~bychom takovouto v 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_i$ a $q_i$. Tato dvojice mù¾e nábývat hned ètyø mo¾ných hodnot, +Oznaème si je jako $p$ a $q$. Tato dvojice mù¾e nábý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øime si dále práci pøi kompozici. Zvolme si tedy kódování takto: @@ -103,14 +105,14 @@ Zvolme si tedy k \:$(0,1) = 1$ \endlist -Tomu, ¾e blok kopíruje, odpovídá dvojice $p_i = 1$; $q_i = cokoliv$. V~ostatních -pøípadech bude~$p_i$ nulové a~$q_i$ nám bude øíkat, co je na~výstupu pøíslu¹ného bloku. -Jinými slovy $p_i = 0$ znamená, ¾e funkce je konstanta, pøièem¾ $q_i$ øíká jaká; naproti -tomu $p_i = 1$~znamená, ¾e funkce je identita, a»~u¾~je $q_i$ cokoli. +Tomu, ¾e blok kopíruje, odpovídá dvojice $p = 1$; $q =$ \. 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. Pojïme si nyní ukázat, jak bude celé skládání blokù vypadat. Rozmysleme si, kdy je~$p$ celého dvojbloku jednièkové, tedy kdy celý dvojblok kopíruje. To nastane -tehdy, pokud kopírují obì jeho èásti a tedy $p = p_a~\&~p_b$. Dále $q$ bude rovno jednièce, +tehdy, pokud kopírují obì jeho èásti, a tedy $p = p_a~\&~p_b$. Dále $q$ bude rovno jednièce, pokud $q = (\neg{p_a}~\&~q_a) \lor (p_a~\&~q_b)$. Skládání chování blokù lze tedy popsat buï ternárnì -- tabulkou, ale lze to @@ -128,13 +130,13 @@ konstanta-kr \algo \:Spoèteme chování blokù velikosti~1. ($\O(1)$ hladin) -\: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$. +\: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$. ($\O(\log n)$ hladin, na~nich¾ se skládají bloky) \:$c_0 \leftarrow 0$ (pøenos do nejni¾¹ího øádu je v¾dy 0) \:Urèíme $c_n$ podle $c_0$ a chování (jediného) bloku velikosti~$n$. \:Postupnì dopoèítáme pøenosy na~hranicích dìlitelných $2^k$ \uv{zahu¹»ováním}: jakmile víme $c_{2^k}$, mù¾eme dopoèítat $c_{2^k+2^{k-1}}$ podle - chování bloku $\left< 2^k+2^{k-1},2^k\right>$. ($\O(\log n)$ hladin, + chování bloku $\left< 2^k, 2^k+2^{k-1}\right>$. ($\O(\log n)$ hladin, na~nich¾ se dosazuje) \:Seèteme: $\forall i: z_i = x_i \oplus y_i \oplus c_i$. \endalgo @@ -147,9 +149,9 @@ exponenci \h{Tøídìní} -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í. +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. -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. +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. \s{Definice:} {\I Komparátorová sí»} je kombinaèní obvod, jeho¾ hradla jsou komparátory. @@ -160,7 +162,7 @@ Kompar a~která men¹í. Nevrací v¹ak booleovský výsledek jako bì¾né hradlo, ale má dva výstupy, pøièem¾ na~jednom vrátí men¹í ze~vstupních hodnot a~na~druhém vìt¹í. -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é.) +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é.) \s{Pøíklad:} {\sl Bubble sort} @@ -172,14 +174,16 @@ Obr Sna¾íme se výpoèet co nejvíce paralelizovat (viz obrázek Bubble 2). 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. +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. + \medskip -\s{Definice:} Øekneme, ¾e posloupnost $x_0,\dots,x_{n-1} $ je {\I èistì bitonická}, právì tehdy, kdy¾ +\s{Definice:} Øekneme, ¾e posloupnost $x_0,\dots,x_{n-1} $ je {\I èistì bitonická} právì tehdy, kdy¾ pro nìjaké $x_k\in\{0, \dots, n-1\} $ platí, ¾e~v¹echny prvky pøed ním (vèetnì jeho samotného) -tvoøí rostoucí poslopnost, kde¾to prvky stojící za~ním, tvoøí poslopnost klesající. +tvoøí rostoucí poslopnost, kde¾to prvky stojící za~ním tvoøí poslopnost klesající. Formálnì zapsáno musí platit, ¾e: $$x_0\leq x_1\leq \dots \leq x_k \geq x_{k+1}\geq\dots \geq x_{n-1}.$$ -\s{Definice:} Posloupnost je {\I bitonická}, právì kdy¾ $\exists~j\in \{0,\dots ,n-1\}$, pro +\s{Definice:} Posloupnost $x_0 \dots x_{n-1}$je {\I bitonická}, právì kdy¾ $\exists~j\in \{0,\dots ,n-1\}$, pro které je rotace pùvodní posloupnosti o $j$ prvkù (posloupnost $x_j,x_{(j+1) \bmod n},\dots, x_{(j+n-1) \bmod n}$) èistì bitonická. @@ -188,8 +192,8 @@ $x_j,x_{(j+1) \bmod n},\dots, x_{(j+n-1) \bmod n}$) maximum $(i+{n/2})$-ním prvkem výstupu. \figure{sortnet.3}{$(y_i, y_{i+{n/2}}) = \(x_i, x_{i+{n/2}})$} {300pt} -\s{Lemma:} Pokud vstup separátoru je bitonická posloupnost, pak výstup -$y_0,\dots, y_{n-1}$ je posloupnost, která splòuje: +\s{Lemma:} Pokud je vstup separátoru bitonická posloupnost, pak jeho výstup $y_0, \dots, y_{n-1}$ +splòuje: (i) $y_0,\dots, y_{n/2 -1}$ a~$y_{n/2},\dots, y_{n-1}$ jsou bitonické posloupnosti, @@ -198,14 +202,14 @@ bitonick Separátor nám tedy jednu bitonickou posloupnost na~vstupu rozdìlí na~dvì bitonické posloupnosti, pøièem¾ navíc ka¾dý prvek první posloupnosti ($y_0,\dots, y_{n/2 -1}$) -je men¹í nebo roven prvkùm druhé posloupnosti. +je men¹í nebo roven prvkùm druhé posloupnosti ($y_{n/2}, \dots, y_{n-1}$). \>Ne¾ pøistoupíme k dùkazu lemmatu, uka¾me si, k èemu se nám bude hodit. \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$. -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. +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. \centerline{\epsfbox{sortnet.5}} @@ -213,7 +217,7 @@ Jak je vid setøídí na~$\Theta(\log n)$ hladin. Nyní se dá odvodit, ¾e pokud umíme tøídit bitonické posloupnosti, umíme setøídit v¹echno. -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. +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. \s{Pøíklad:} {\sl Merge sort} @@ -223,9 +227,9 @@ Uka Setøídìné posloupnosti $x_0,\dots, x_{n-1}$ a~$y_0,\dots, y_{n-1}$ spojíme do jedné bitonické posloupnosti $x_0,\dots, x_{n-1},y_{n-1},\dots, y_0$. Z~této posloupnosti vytvoøíme pomocí bitonické tøídièky $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í. -\figure{sortnet.6}{Slévaèka $M_n$.}{3in} +\figure{sortnet.6}{Paralelní MergeSort.}{3in} -Nyní se pokusme odhadnout èasovou slo¾itost. Na¹e slévaèka, bude mít øádovì hloubku $\log n$. +Nyní se pokusme odhadnout èasovou slo¾itost. Ná¹ MergeSort bude mít øádovì hloubku blokù $\log n$. V ka¾dém bloku $M_n$ je navíc ukryta bitonická tøídièka s takté¾ logaritmickou hloubkou. Celková hloubka tedy bude $\log 2 + \log4 + \dots + \log 2^k + \dots + \log n$. Po seètení nakonec dostáváme výslednou èasovou slo¾itost $\Theta (\log^2 n)$. @@ -233,20 +237,22 @@ Po se Dodejme je¹tì, ¾e existuje i~tøídicí algoritmus, kterému staèí jen ${\O}(\log n)$ hladin. Jeho multiplikativní konstanta je v¹ak pøíli¹ veliká, tak¾e je v~praxi nepou¾itelný. +Vra»me se nyní k dùkazu lemmatu, který jsme na pøedminulé stránce vynechali. + \h{Dùkaz Lemmatu:} (i) Nejprve nahlédneme, ¾e lemma platí, je-li vstupem èistì bitonická posloupnost. Dále BÚNO pøedpokládejme, ¾e vrchol posloupnosti je v~první polovinì (kdyby -byl vrchol za~polovinou, staèilo by zradlovì obrátit posloupnost s~komparátory a~øe¹ili +byl vrchol za~polovinou, staèilo by zrcadlovì obrátit posloupnost i~komparátory a~øe¹ili bychom stejný problém). Nyní si definujme $k := \min j: x_j > x_{j+n/2}$. (Pokud by~takové~$k$ neexistovalo, znamenalo by~to, ¾e vstupní posloupnost je monotónní. -Separátor by tedy nic nedìlal a~pouze zkopíroval vstup na~výstup.) Nyní si v¹imìme, +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, ¾e jakmile jednou zaène platit, ¾e prvek na~levé stranì je men¹í ne¾ na~pravé, bude nám tato relace platit a¾~do~konce. Oznaème vrchol vstupní posloupnosti jako~$x_m$. Pak~$k$ bude jistì men¹í ne¾~$m$ a~$k+{n/2}$ bude vìt¹í ne¾~$m$. Mezi~$k$ a~$m$ je tedy vstupní posloupnost neklesající, mezi $k+{n/2}$ a~$n-1$ nerostoucí. Do pozice~$k$ tedy separátor bude pouze kopírovat vstup na~výstup, od~pozice~$k$ -dál pak u¾~jen prohazuje. Pro ka¾dé~$i$, $k\leq i\leq {n/2}-1$ se prvky +dál u¾~jen prohazuje. Pro ka¾dé~$i$, $(k\leq i\leq {n/2}-1)$ se prvky $x_i$ a~$x_{i+{n/2}}$ prohodí. Úsek mezi~$k$ a~${n/2}-1$ tedy nahradíme nerostoucí posloupností, první polovina výstupu tedy bude (dokonce èistì) bitonická. Podobnì úsek $k+{n/2}$ a¾~$n-1$ nahradíme èistì @@ -272,34 +278,35 @@ bitoni \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, 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. +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 +{\sc 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)$. To je dle na¹ich mìøítek -jistì docela efektivní. Pøekvapivì to jde ale je¹tì lépe - toti¾ na~$\Theta (\log n)$. Této +Toto øe¹ení by v¹ak vedlo na~èasovou slo¾itost $\Theta (\log^2 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, který na~vstupu dostane tøi èísla. Odpoví pak dvìma èísly +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. +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.95in} +\figure{sl_stromecek.eps}{Slo¾itìj¹í stromeèek}{0.9in} -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. +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. -Celé sèítání $n$ $n$-bitových èísel nám tedy zabere $\Theta (\log n)$. +Celé sèítání $n$ $n$-bitových èísel nám 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~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. +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. \bye -- 2.39.2