2007/1-hradla/1-hradla.tex

   1 \input ../lecnotes.tex
   2
   3 \prednaska{1}{Hradlové sítì}{(zapsali Jirka Fajfr a Ján Èerný)}
   4
   5 \def\land{\mathbin{\&}}
   6
   7 Na této pøedná¹ce se budeme zabývat jednoduchým modelem paralelního poèítaèe,
   8 toti¾ hradlovou sítí, a uká¾eme si alespoò jeden efektivní paralelní algoritmus,
   9 konkrétnì sèítání dvojkových èísel v~logaritmickém èase vzhledem k~jejich délce.
  10
  11 \h{Hradlové sítì}
  12
  13 \s{Definice:} {\I Hradlo} je zaøízení, které poèítá nìjakou pevnì danou funkci
  14 s~$k$ vstupy a jedním výstupem.
  15
  16 \s{Pøíklad:} Obvykle pracujeme s~booleovskými hradly, ta pak odpovídají funkcím
  17 $f: \{0,1\}^{k} \rightarrow \{0,1\} $. Z~nich nejèastìji potkáme:
  18
  19 \itemize\ibull
  20 \:0-vstupové: to jsou konstanty {\sc true} a {\sc false},
  21 \:1-vstupové: identita (ta je vcelku k~nièemu) a negace (znaèíme~$\lnot$),
  22 \:2-vstupové: logický souèin ({\sc and},~$\land$) a souèet ({\sc or},~$\lor$).
  23 \endlist
  24
  25 \>Hradla kreslíme tøeba následovnì:
  26
  27 \figure{1_1_hradlo.eps}{Hradlo provádìjící logickou operaci {\sc and} se dvìma vstupy}{4cm}
  28
  29 Z~jednotlivých hradel pak vytváøíme hradlové sítì. Pokud pou¾íváme pouze booleovská
  30 hradla, øíkáme takovým sítím {\I booleovské obvody,} pokud operace nad nìjakou obecnìj¹í
  31 (ale koneènou) mno¾inou symbolù (abecedou), nazývají se {\I kombinaèní obvody.}
  32 Ka¾dý vstup hradla je pøipojen buïto na~nìkterý ze~vstupù sítì nebo na~výstup nìjakého
  33 jiného hradla. Výstupy hradel mohou být propojeny na výstupy sítì nebo pøivedeny
  34 na~vstupy dal¹ích hradel, pøièem¾ je zakázáno vytváøet cykly. Ne¾ si øekneme
  35 formální definici, podívejme se na obrázek.
  36
  37 \todo{OBR}
  38
  39 \s{Definice:} {\I Hradlová sí»} je urèena:
  40 \itemize\ibull
  41 \:{\I abecedou} $\Sigma$ (to je nìjaká koneèná mno¾ina symbolù, obvykle $\Sigma=\{0,1\}$);
  42 \:mno¾inou {\I hradel} $H$, {\I vstupních portù} $I$ a {\I výstupních portù} $O$;
  43 \:acyklickým orientovaným grafem~$(V,E)$, kde~$V = H \cup I \cup O$;
  44 \:zobrazením~$F$, které ka¾dému hradlu $h\in H$ pøiøadí nìjakou funkci~$F(h):
  45   \Sigma^{a(h)} \rightarrow \Sigma$. To je funkce, kterou toto hradlo vykonává,
  46   a~èíslu $a(h)$ øíkáme {\I arita} hradla~$h$;
  47 \:zobrazením~$z: E \rightarrow {\bb N}$, které ka¾dé hranì vedoucí do~nìjakého
  48   hradla pøiøazuje nìkterý ze vstupù tohoto hradla.
  49 \endlist
  50
  51 \>Pøitom jsou splnìny následující podmínky:
  52
  53 \itemize\ibull
  54 \:$\forall i \in I: \deg^{+}(i)=0$ (do~vstupù nic nevede);
  55 \:$\forall o \in O: \deg^{+}(o)=1 \land \deg^{-}(o)=0$ (z~výstupù nic nevede a do~ka¾dého vede právì jedna hrana);
  56 \:$\forall h \in H: \deg^{+}(v)=a(v)$ (do~ka¾dého hradla vede tolik hran, kolik je jeho arita);
  57 \:$\forall h \in H, 1\le j\le a(h)$ existuje právì jeden vrchol~$v$ takový, ¾e $z(vh)=j$
  58   (v¹echny vstupy hradel jsou zapojeny).
  59 \endlist
  60
  61 \s{Pozorování:} Kdybychom pøipustili hradla s~libovolnì vysokým poètem vstupù, mohli bychom
  62 libovolný problém se vstupem délky~$n$ vyøe¹it jedním hradlem o~$n$~vstupech, co¾ není
  63 ani realistické, ani pìkné. Proto pøijmìme omezení, ¾e v¹echna hradla budou mít maximálnì
  64 $k$ vstupù, kde~$k$ je nìjaká pevná konstanta, obvykle dvojka. Následující obrázky
  65 ukazují, jak hradla o~více vstupech nahradit dvouvstupovými:
  66
  67 \twofigures{1_2_vice_vstupove_hradlo.eps}{Trojvstupové hradlo \sc and}{3cm}{1_3_vice_vstupove_hradlo.eps}{Jeho nahrazení 2-vstupovými hradly}{3cm}
  68
  69 \s{Definice:} {\I Výpoèet sítì} probíhá v~{\I taktech.} V nultém taktu jsou definovány právì hodnoty
  70 vstupních portù. V~$i$-tém taktu vydají výsledek hradla, která jsou pøipojena
  71 na~porty nebo na~výstupy hradel, jejich¾ hodnota byla definována v~$(i-1)$-ním
  72 taktu. A¾ po~nìjakém koneèném poètu taktù budou definované i hodnoty výstupních
  73 portù, sí» se zastaví a vydá výsledek.
  74
  75 \figure{1_7_vypocet_site.eps}{Výpoèet hradlové sítì}{6cm}
  76
  77 \>Podle toho, jak sí» poèítá, si ji mù¾eme rozdìlit na~vrstvy:
  78
  79 \s{Definice:} {\I $i$-tá vrstva} obsahuje v¹echny vrcholy~$v$ takové, ¾e
  80 nejdel¹í z~cest z~portù sítì do~$v$ má délku právì~$i$. To jsou
  81 pøesnì vrcholy, které vydají výsledek poprvé v~$i$-tém taktu výpoètu.
  82 Dává tedy smysl prohlásit za~{\I èasovou slo¾itost} sítì poèet jejích
  83 vrstev. Podobnì {\I prostorovou slo¾itost} definujeme jako poèet hradel
  84 v~síti.
  85
  86 \s{Pøíklad:} Sestrojte sí», která zjistí, zda se mezi jejími~$n$ vstupy
  87 vyskytuje alespoò jedna jednièka.
  88
  89 \>{\I První øe¹ení:} zapojíme hradla za~sebe (sériovì). Èasová a prostorová
  90 slo¾itost jsou~$n$. Zde vùbec nevyu¾íváme toho, ¾e by mohlo poèítat více
  91 hradel souèasnì.
  92
  93 \figure{1_5_hloupy_or.eps}{Hradlová sí», která zjistí zda-li je na vstupu alespoò jedna jednièka}{7cm}
  94
  95 \>{\I Druhé øe¹ení:} Budeme vrcholy spojovat do~dvojic, pak výsledky z~tìchto
  96 dvojic opìt do~dvojic a tak dále. Tak dosáhneme èasové slo¾itosti $\Theta(\log n)$,
  97 prostorová slo¾itost zùstane lineární.
  98
  99 \figure{1_4_chytry_or.eps}{Chytøej¹í øe¹ení stejného problému}{8cm}
 100
 101 \h{Sèítání binárních èísel}
 102
 103 Pojïme se podívat na~zajímavìj¹í problém: Mìjme dvì èísla zapsané ve~dvojkové
 104 soustavì jako $x_{n-1}\ldots x_1x_0$ a $y_{n-1}\ldots y_1y_0$. Budeme chtít
 105 spoèítat jejich souèet $z_nz_{n-1}\ldots z_1z_0$.
 106
 107 Samozøejmì mù¾eme pou¾ít algoritmus \uv{sèítání pod sebou}, který nás
 108 uèili na~základní ¹kole. Formálnì by se dal zapsat tøeba takto:
 109 $$
 110 z_i=x_i \oplus y_i \oplus c_{i-1},
 111 $$
 112 kde $\oplus$ znaèí operaci {\sc xor} (souèet modulo~2) a $c_{i-1}$ je {\I pøenos} z~$(i-1)$-ního
 113 øádu do~$i$-tého. Pøenos pøitom nastane tehdy, kdy¾ ze~tøí xorovaných èíslic
 114 jsou alespoò dvì jednièky:
 115 $$
 116 \eqalign{
 117 c_{-1} &= 0 \cr
 118 c_i &= (x_i \land y_i)\lor((x_i \lor y_i) \land c_{i-1}).\cr
 119 }
 120 $$
 121
 122 \figure{1_6_hloupe_scitani.eps}{Sèítání ze~základní ¹koly}{8cm}
 123
 124 Bohu¾el na to, abychom spoèítali $c_i$ (a~tedy~$z_i$), musíme znát hodnotu $c_{i-1}$, tedy mít
 125 spoèítané hodnoty pro v¹echny èísla men¹í ne¾ $i$. To dává lineární èasovou
 126 slo¾itost. Zamysleme se nad tím, jak by se proces sèítání mohl zrychlit.
 127
 128 \h{Pøenosy v~blocích}
 129
 130 Jediné, co nás pøi sèítání brzdí, jsou pøenosy. Kdybychom je dokázali spoèítat rychle
 131 (øeknìme v~logaritmické hloubce), souèet u¾ zvládneme dopoèítat v~konstantním èase.
 132
 133 Podívejme se na~libovolný {\I blok} v~na¹em souètu. Tak budeme øíkat èíslùm
 134 $x_a\ldots x_b$ a $y_a\ldots y_b$ v~nìjakém intervalu indexù $\left<a,b\right>$.
 135 Pøenos $c_b$ vystupující z~tohoto bloku závisí mimo hodnot sèítancù u¾ pouze
 136 na~pøenosu $c_{a-1}$, který do bloku vstupuje. Záviset mù¾e pouze tøemi
 137 mo¾nými zpùsoby:
 138
 139 \numlist\ndotted
 140 \:generuje pøenos: $c_a=1$,
 141 \:pohlcuje pøenos: $c_a=0$,
 142 \:kopíruje pøenos: $c_a=c_{b-1}$.
 143 \endlist
 144
 145 \figure{1_7_blok_scitani.eps}{Blok souètu}{8cm}
 146
 147 \s{Cvièení:} Rozmyslete si, jak pøesnì vypadají bloky s~jednotlivými typy chování.
 148
 149 Jednobitové bloky se chovají velice jednodu¹e:
 150
 151 \figure{1_11_tabulka_kodovani.eps}{Tabulka triviálních bitù}{3cm}
 152
 153 Pokud máme nìjaký vìt¹í blok~$B$ slo¾ený z~men¹ích blokù $p$ a~$q$, jejich¾
 154 chování u¾ známe, mù¾eme z~toho odvodit, jak se chová velký blok:
 155
 156 \figure{1_10_konvence_deleni_bloku.eps}{Skládání chování blokù}{3cm}
 157
 158 V¹imòìme si, ¾e skládání chování blokù je asociativní operace (je to vlastnì
 159 úplnì obyèejné skládání funkcí), tak¾e pro libovolný blok mù¾eme jeho
 160 chování spoèítat v~èase $\O(\log n)$ postupným skládáním (\uv{stromeèkovým}
 161 zpùsobem).
 162
 163 To nám dá nìjaký kombinaèní obvod nad trojprvkovou abecedou, ale samozøejmì
 164 mù¾eme chování blokù kódovat i binárnì dvojicí bitù:
 165
 166 \itemize\ibull
 167 \:$(1,*) = <$,
 168 \:$(0,0) = 0$,
 169 \:$(0,1) = 1$
 170 \endlist
 171
 172 \>Operaci skládání $(a,x) \odot (b,y) = (c,z)$ pak definujeme takto:
 173 $$
 174 \eqalign{
 175 c &= a \land b,\cr
 176 z &= (\neg a \land x) \lor (a \land y).\cr
 177 }
 178 $$
 179
 180 \h{Paralelní sèítání}
 181
 182 \>Paralelní algoritmus na~sèítání u¾ zkonstruujeme pomìrnì snadno. Bez
 183 újmy na~obecnosti budeme pøedpokládat, ¾e poèet bitù vstupních èísel~$n$
 184 je mocnina dvojky, jinak si vstup doplníme nulami.
 185
 186 \algo
 187 \:Spoèteme chování blokù velikosti~1. ($\O(1)$ hladin)
 188 \:Postupnì poèítáme chování blokù velikosti $2^k$ na~pozicích dìlitelných $2^k$.
 189   ($\O(\log n)$ hladin, na~nich¾ se skládají bloky)
 190 \:$c_{-1} \leftarrow 0$
 191 \:Urèíme $c_n$ podle $c_{-1}$ a chování (jediného) bloku velikosti~$n$.
 192 \:Postupnì poèítáme pøenosy na~hranicích dìlitelných $2^k$ \uv{zahu¹»ováním}:
 193   jakmile víme $c_{2^k-1}$, mù¾eme dopoèítat $c_{2^k+2^{k-1}-1}$ podle
 194   chování bloku $\left< 2^k+2^{k-1}-1,2^k\right>$. ($\O(\log n)$ hladin,
 195   na~nich¾ se dosazuje)
 196 \:$\forall i: z_i = x_i \oplus y_i \oplus c_{i-1}$.
 197 \endalgo
 198
 199 \figure{1_9_deleni_bloku.eps}{Výpoèet pøenosu}{8cm}
 200
 201 Algoritmus pracuje v~èase $\O(\log n)$. Hradel je dokonce lineárnì:
 202 na~jednotlivých hladinách kroku~2 poèet hradel exponenciálnì klesá
 203 od~$n$ k~1, na~hladinách kroku~5 exponenciálnì stoupá od~1 k~$n$, tak¾e se
 204 seète na~$\O(n)$.
 205
 206 \bye