6-bitonic/6-bitonic.tex

   1 \input ../lecnotes.tex
   2
   3 \prednaska{6}{Bitonické tøídìní}{}
   4
   5 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.
   6
   7 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.
   8
   9 \s{Definice:} {\I Komparátorová sí»} je kombinaèní obvod, jeho¾ hradla jsou
  10 komparátory.
  11
  12 \figure{sortnet.0}{Komparátor}{0.7in}
  13
  14 Komparátor umí porovnat dvì hodnoty a~rozhodnout, která z~nich je vìt¹í
  15 a~která men¹í. Nevrací v¹ak booleovský výsledek jako bì¾né hradlo, ale má dva
  16 výstupy, pøièem¾ na~jednom vrátí men¹í ze~vstupních hodnot a~na~druhém vìt¹í.
  17
  18 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é.)
  19
  20 \s{Pøíklad:} {\sl Bubble sort}
  21
  22 Obrázek Bubble 1 ilustruje pou¾ití komparátorù pro tøídìní Bubble sortem.
  23 ©ipky pøedstavují jednotlivé komparátory. Výpoèet v¹ak je¹tì mù¾eme vylep¹it.
  24
  25 \twofigures{sortnet.1}{Bubble 1}{143pt}{sortnet.2}{Bubble 2}{143pt}
  26
  27 Sna¾íme se výpoèet co nejvíce paralelizovat (viz obrázek Bubble 2).
  28 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.
  29
  30 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é.
  31
  32 \medskip
  33 \s{Definice:} Øekneme, ¾e posloupnost $x_0,\dots,x_{n-1} $ je {\I èistì bitonická} právì tehdy, kdy¾
  34 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)
  35 tvoøí rostoucí poslopnost, kde¾to prvky stojící za~ním tvoøí poslopnost klesající.
  36 Formálnì zapsáno musí platit, ¾e:
  37 $$x_0\leq x_1\leq \dots \leq x_k \geq x_{k+1}\geq\dots \geq x_{n-1}.$$
  38
  39 \s{Definice:} Posloupnost $x_0 \dots x_{n-1}$ je {\I bitonická}, právì kdy¾ $\exists~j\in \{0,\dots ,n-1\}$, pro
  40 které je rotace pùvodní posloupnosti o $j$ prvkù, tedy posloupnost
  41 $$x_j,x_{(j+1) \bmod n},\dots, x_{(j+n-1) \bmod n},$$ èistì bitonická.
  42
  43 \s{Definice:} {\I Separátor $S_n$} je sí», ve které jsou v¾dy~$i$-tý a~$(i+{n/2})$-tý prvek vstupu
  44 (pro $i=0,\dots, {n/2}-1$) propojeny komparátorem. Minimum se pak stane~$i$-tým,
  45 maximum  $(i+{n/2})$-tým prvkem výstupu.
  46 \figure{sortnet.3}{$(y_i, y_{i+{n/2}}) = \<CMP>(x_i, x_{i+{n/2}})$} {300pt}
  47
  48 \s{Lemma:} Pokud separátor dostane na~vstupu bitonickou posloupnost, pak jeho výstup $y_0, \dots, y_{n-1}$
  49 splòuje:
  50
  51 (i) $y_0,\dots, y_{n/2 -1}$ a~$y_{n/2},\dots, y_{n-1}$ jsou
  52 bitonické posloupnosti,
  53
  54 (ii) Pro v¹echna $i,j< {n/2}$ platí $y_i < y_{j + {n/2}}$.
  55
  56 Separátor nám tedy jednu bitonickou posloupnost na~vstupu rozdìlí na~dvì
  57 bitonické posloupnosti, pøièem¾ navíc ka¾dý prvek první posloupnosti ($y_0,\dots, y_{n/2 -1}$)
  58 je men¹í nebo roven prvkùm druhé posloupnosti ($y_{n/2}, \dots, y_{n-1}$).
  59
  60 \>Ne¾ pøistoupíme k dùkazu lemmatu, uka¾me si, k èemu se nám bude hodit.
  61
  62
  63 \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$.
  64
  65 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.
  66
  67 \centerline{\epsfbox{sortnet.5}}
  68
  69 Jak je vidìt, bitonická tøídièka nám libovolnou bitonickou posloupnost délky~$n$
  70 setøídí na~$\Theta(\log n)$ hladin.
  71
  72 Nyní se dá odvodit, ¾e pokud umíme tøídit bitonické posloupnosti, umíme setøídit v¹echno.
  73 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.
  74
  75 \s{Pøíklad:} {\sl Merge sort}
  76
  77 Bitonická tøídièka se tedy dá pou¾ít ke~slévání setøídìných posloupností.
  78 Uka¾me si, jak s~její pomocí sestavíme souèástky {\I slévaèky} $M_n$:
  79
  80 Setøídìné posloupnosti $x_0,\dots, x_{n-1}$ a~$y_0,\dots, y_{n-1}$ spojíme do jedné bitonické
  81 posloupnosti $x_0,\dots, x_{n-1},y_{n-1},\dots, y_0$. Z~této posloupnosti vytvoøíme pomocí bitonické tøídièky
  82 $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í.
  83 \figure{sortnet.6}{Paralelní MergeSort.}{3in}
  84
  85 Nyní se pokusme odhadnout èasovou slo¾itost. Ná¹ MergeSort bude mít øádovì hloubku blokù $\log n$.
  86 V ka¾dém bloku $M_n$ je navíc ukryta bitonická tøídièka s takté¾ logaritmickou hloubkou.
  87 Celková hloubka tedy bude $\log 2 + \log4 + \dots + \log 2^k + \dots + \log n$.
  88 Po seètení nakonec dostáváme výslednou èasovou slo¾itost $\Theta (\log^2 n)$.
  89
  90 Dodejme je¹tì, ¾e existuje i~tøídicí algoritmus, kterému staèí jen ${\O}(\log n)$ hladin.
  91 Jeho multiplikativní konstanta je v¹ak pøíli¹ veliká, tak¾e je v~praxi nepou¾itelný.
  92
  93 Vra»me se nyní k dùkazu lemmatu, který jsme na pøedminulé stránce vynechali.
  94
  95 \h{Dùkaz Lemmatu:}
  96 (i) Nejprve nahlédneme, ¾e lemma platí, je-li vstupem èistì bitonická
  97 posloupnost. Dále BÚNO pøedpokládejme, ¾e vrchol posloupnosti je v~první polovinì (kdyby
  98 byl vrchol za~polovinou, staèilo by zrcadlovì obrátit posloupnost i~komparátory a~øe¹ili
  99 bychom stejný problém). Nyní si definujme $k := \min j: x_j > x_{j+n/2}$. (Pokud
 100 by~takové~$k$ neexistovalo, znamenalo by~to, ¾e vstupní posloupnost je monotónní.
 101 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,
 102 ¾e jakmile jednou zaène platit, ¾e prvek na~levé stranì je men¹í ne¾ na~pravé, bude
 103 nám tato relace platit a¾~do~konce. Oznaème vrchol vstupní posloupnosti jako~$x_m$.
 104 Pak~$k$ bude jistì men¹í ne¾~$m$ a~$k+{n/2}$ bude vìt¹í ne¾~$m$. Mezi~$k$ a~$m$ je tedy
 105 vstupní posloupnost neklesající, mezi $k+{n/2}$ a~$n-1$ nerostoucí.
 106
 107 Do pozice~$k$ tedy separátor bude pouze kopírovat vstup na~výstup, od~pozice~$k$
 108 dál u¾~jen prohazuje. Pro ka¾dé~$i$, $(k\leq i\leq {n/2}-1)$ se prvky
 109 $x_i$ a~$x_{i+{n/2}}$ prohodí. Úsek mezi~$k$ a~${n/2}-1$ tedy
 110 nahradíme nerostoucí posloupností, první polovina výstupu tedy bude
 111 (dokonce èistì) bitonická. Podobnì úsek $k+{n/2}$ a¾~$n-1$ nahradíme èistì
 112 bitonickou posloupností. Obì poloviny tedy budou bitonické.
 113
 114 Dostaneme-li na vstupu obecnou bitonickou posloupnost, pøedstavíme si,
 115 ¾e je to èistì bitonická posloupnost zrotovaná o~$r$ prvkù (BÚNO
 116 doprava). Zjistíme, ¾e v~komparátorech se porovnávají tyté¾ prvky,
 117 jako kdyby zrotovaná nebyla. Výstup se od výstupu èistì bitonické
 118 posloupnosti zrotovaného o~$r$ bude li¹it prohozením úsekù $x_0$ a¾
 119 $x_{r-1}$ a~$x_{n/2}$ a¾ $x_{{n/2}+r-1}$. Obì výstupní
 120 posloupnosti tedy budou zrotované o~$r$ prvkù, ale na jejich
 121 bitoniènosti se nic nezmìní.
 122
 123 (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).
 124 \qed
 125
 126 \medskip
 127
 128 \centerline{\epsfbox{sortnet.7}}
 129
 130 \bye