\input ../lecnotes.tex

\prednaska{6}{Bitonické 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 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.

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

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

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.

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. Bez újmy na obecnosti budeme pøedpokládat, ¾e ka¾dé dva prvky na vstupu jsou navzájem rùzné.

\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, 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í.
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 $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ù, tedy 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 se pak stane~$i$-tým,
maximum  $(i+{n/2})$-tým prvkem výstupu.
\figure{sortnet.3}{$(y_i, y_{i+{n/2}}) = \<CMP>(x_i, x_{i+{n/2}})$} {300pt}

\s{Lemma:} Pokud separátor dostane na~vstupu bitonickou 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,

(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í posloupnosti ($y_0,\dots, y_{n/2 -1}$)
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 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}}

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}{Paralelní MergeSort.}{3in}

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

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 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, 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 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
