Dalsi verze geometrie.

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

\input ../lecnotes.tex

\prednaska{5}{Paralelní sèítání, bitonické tøídìní}{(zapsal: Petr Jankovský)}

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

Mìjme dvì èísla $x$ a $y$ zapsané ve~dvojkové soustavì. Jejich èíslice nazývejme
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
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
øá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 {\sc 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. Jinými slovy tehdy, kdy¾ ze~tøí xorovaných èíslic jsou alespoò
dvì jednièky:
$$
\eqalign{
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
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
krabièky tedy musí le¾et urèitì 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.

Zamysleme se nad tím, jak by se proces sèítání mohl zrychlit.

\h{Pøenosy v~blocích}
Jediné, co nás pøi sèítání brzdí, jsou pøenosy mezi jednotlivými øády. Ka¾dý øád,
aby~vydal souèet, musí poèkat na~to, a¾~dopoèítají v¹echny pøedcházející øády.
Teprve pak se~toti¾ dozví pøenos. Kdybychom ov¹em pøenosy dokázali spoèítat
nìjakým zpùsobem paralelnì, máme vyhráno. Jakmile známe v¹echny pøenosy, souèet
u¾~zvládneme dopoèítat na~konstantnì mnoho hladin - tedy v~konstantním èase.

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<j,i\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}
Z tohoto pohledu se mù¾eme na blok také dívat jako na nìjakou funkci, která
dostane jednobitový vstup a vydá jednobitový výstup. To je nám pøíjemné, nebo» 
takových funkcí existují jenom ètyøi typy:
\numlist\ndotted
\:$f(x) = 0$,  ~~~~(0)
\:$f(x) = 1$,  ~~~~(1)
\:$f(x) = x$,  ~~~~($<$)
\:$f(x) = \neg{x}$.
\endlist
Jak se za~chvíli uká¾e, poslední pøípad, kdy by~nìjaký blok pøedával opaèný
pøenos, ne¾ do~nìj vstupuje, navíc nikdy nemù¾e nastat. Pojïme si to rozmyslet.
Jednobitové bloky se chovají velice jednodu¹e:

\figure{bloky_1bit.eps}{Tabulka triviálních bitù.}{1.1in}

Z prvního bloku evidentnì v¾dy vyleze 0, a»~do~nìj vstoupí jakýkoli pøenos.
Poslední blok naopak sám o~sobì pøenos vytváøí, a»~ji¾ do~nìj vleze jakýkoliv.
Bloky prostøední se chovají stejnì a~to tak, ¾e~samy o~sobì ¾ádný pøenos nevytvoøí,
ale~pokud do~nich nìjaký pøijde, tak~také odejde.

Mìjme nyní nìjaký vìt¹í blok~$C$ slo¾ený ze~dvou men¹ích podblokù $A$ a~$B$, 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í
tìchto 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ïmì 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_i$ a $q_i$. 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:

\itemize\ibull
\:$(1,*) = <$,
\:$(0,0) = 0$,
\:$(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á funkce je konstanta, pøièem¾ $q_i$ øíká jaká, $p_i = 1$~znamená
funkce je identita, a»~u¾~je $q_i$ 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,
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
i~binárnì vý¹e uvedeným pøedpisem.

Nyní si tedy mù¾eme dopøedu vypoèítat chování bloku velikosti jedna, poté
 z~nich skládáním blokù velikosti dva, dál velikosti ètyøi, osm, atd...

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

Paralelní algoritmus na~sèítání u¾~zkonstruujeme pomìrnì snadno. 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ýsedný èas bìhu algoritmu zhor¹í maximálnì
konstanta-krát.

\algo
\:Spoèteme chování blokù velikosti~1. ($\O(1)$ hladin)
\:Postupnì poèítáme chování blokù 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,
  na~nich¾ se dosazuje)
\:$\forall i: z_i = x_i \oplus y_i \oplus c_i$.
\endalgo

\figure{1_9_deleni_bloku.eps}{Výpoèet pøenosu}{8cm}

Algoritmus pracuje v~èase $\O(\log n)$. Hradel je pou¾ito lineárnì: na~jednotlivých
hladinách kroku~2 poèet hradel exponenciálnì klesá od~$n$ k~1, na~hladinách kroku~5
exponenciálnì stoupá od~1 k~$n$, tak¾e dohromady se seète na~$\Theta(n)$.

\h{Tøídìní}

\s{Definice:} {\I Komparátorová sí»} je kombinaèní obvod, jeho¾ hradla jsou
komparátory.

\figure{sortnet.0}{Komparátor.}{0.9in}

Komparátor umí porovnat dvì hodnoty a~rozhodnout, která z~nich je vìt¹í
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í.

\s{Pøíklad:} {\sl Bubble sort}

Obrázek Bubble\_1 ilustruje pou¾ití komparátorù pro tøídìní bubble sortem.
©ipky pøedstavují jednotlivé komparátory. Výpoèet v¹ak je¹tì mù¾eme vylep¹it.

\twofigures{sortnet.1}{Bubble\_1}{143pt}{sortnet.2}{Bubble\_2}{143pt}

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.

\medskip
\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\{1, \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í.
Formálnì zaspá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 \{1,\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á.

\s{Definice:} {\I Separátor $S_n$} je sí», ve které jsou v¾dy~$i$-tý a~$(i+{n/2})$-tý prvek vstupu
(pro $i=0,\dots, {n/2}-1$) propojeny komparátorem. Minimum pak bude~$i$-tým,
maximum  $(i+{n/2})$-ním prvkem výstupu.
\figure{sortnet.3}{$(y_i, y_{i+{n/2}}) = CMP(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:

(i) $y_0,\dots, y_{n/2 -1}$ a~$y_{n/2},\dots, y_{n-1}$ jsou 
bitonické posloupnosti,

(ii) Pro v¹echna $i,j< {n/2}$ platí $y_i < y_{j + {n/2}}$.

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í poslopnosti ($y_0,\dots, y_{n/2 -1}$)
je men¹í nebo roven prvkùm druhé posloupnosti.

\>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 posloupnost délky $n$. 

\centerline{\epsfbox{sortnet.5}}

Jak je vidìt, bitonická tøídièka nám libovolnou bitonickou posloupnost délky~$n$
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.

\s{Pøíklad:} {\sl Merge sort}

Bitonická tøídièka se tedy dá pou¾ít ke~slévání setøídìných posloupností. 
Uka¾me si, jak s~její pomocí sestavíme souèástky {\I slévaèky} $M_n$:

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}

Nyní se pokusme odhadnout èasovou slo¾itost. Na¹e slévaèka, bude mít øádovì hloubku $\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^{2^k} + \dots + \log n$.
Po seètení nakonec dostáváme výslednou èasovou slo¾itost $\Theta (\log^2 n)$.

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



\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
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,
¾e jakmile jednou zaène palatit, ¾e prvek na~levé stranì je men¹í ne¾ na~pravé, bude
nám tato relace platit a¾~do~konce. Oznaème $x_m$ jako maximum vstupní posloupnosti.
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
$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ì
bitonickou posloupností. Obì poloviny tedy budou bitonické.

Dostaneme-li na vstupu obecnou bitonickou posloupnost, pøedstavíme si,
¾e je to èistì bitonická posloupnost zrotovaná o~$r$ prvkù (BÚNO
doprava). Zjistíme, ¾e v~komparátorech se porovnávají tyté¾ prvky
jako kdyby zrotovaná nebyla. Výstup se od výstupu èistì bitonické
posloupnosti zrotovaného o~$r$ bude li¹it prohozením úsekù $x_0$ a¾
$x_{r-1}$ a~$x_{n/2}$ a¾ $x_{{n/2}+r-1}$. Obì výstupní
posloupnosti tedy budou zrotované o~$r$ prvkù, ale na jejich
bitoniènosti se nic nezmìní.

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

\medskip
\centerline{\epsfbox{sortnet.7}}

\bye