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 Na této pøedná¹ce se budeme zabývat jednoduchým modelem paralelního poèítaèe,
   6 toti¾ hradlovou sítí, a uká¾eme si alespoò jeden efektivní paralelní algoritmus,
   7 konkrétnì sèítání dvojkových èísel v~logaritmickém èase vzhledem k~jejich délce.
   8
   9 \h{Hradlové sítì}
  10
  11 \s{Definice:} {\I Hradlo} je element, který poèítá nìjakou pevnì danou funkci
  12 s~$k$ vstupy a jedním výstupem.
  13
  14 \s{Pøíklad:} Obvykle pracujeme s~booleovskými hradly, ta pak odpovídají funkcím
  15 $f: \{0,1\}^{k} \rightarrow \{0,1\} $. Z~nich nejèastìji potkáme:
  16
  17 \itemize\ibull
  18 \:0-vstupové: to jsou konstanty {\sc true} a {\sc false},
  19 \:1-vstupové: identita (ta je vcelku k~nièemu) a negace (znaèíme~$\lnot$),
  20 \:2-vstupuvé: logický souèin ({\sc and},~\&) a souèet ({\sc or},~$\lor$).
  21 \endlist
  22
  23 \>Hradla kreslíme tøeba následovnì:
  24
  25 \figure{1_1_hradlo.eps}{Hradlo provádìjící logickou operaci {\sc AND} se dvìma vstupy}{4cm}
  26
  27 Z~jednotlivých hradel pak vytváøíme hradlové sítì. Pokud pou¾íváme pouze booleovská
  28 hradla, øíkáme takovým sítím {\I booleovské obvody,} pokud operace nad nìjakou obecnìj¹í
  29 (ale koneènou) mno¾inou symbolù (abecedou), nazývají se {\I kombinaèní obvody.}
  30 Ka¾dý vstup hradla je pøipojen buïto na~nìkterý ze~vstupù sítì nebo na~výstup nìjakého
  31 jiného hradla. Výstupy hradel mohou být propojeny na výstupy sítì nebo pøivedeny
  32 na~vstupy dal¹ích hradel, pøièem¾ je zakázáno vytváøet cykly. Ne¾ si øekneme
  33 formální definici, podívejme se na obrázek.
  34
  35 \todo{OBR}
  36
  37 \s{Definice:} {\I Hradlová sí»} je urèena:
  38 \itemize\ibull
  39 \:{\I abecedou} $\Sigma$ (to je nìjaká koneèná mno¾ina symbolù, obvykle $\Sigma=\{0,1\}$);
  40 \:mno¾inou {\I hradel} $H$, {\I vstupních portù} $I$ a {\I výstupních portù} $O$;
  41 \:acyklickým orientovaným grafem~$(V,E)$, kde~$V = H \cup I \cup O$;
  42 \:zobrazením~$F$, které ka¾dému hradlu $h\in H$ pøiøadí nìjakou funkci~$F(h):
  43   \Sigma^{a(h)} \rightarrow \Sigma$. To je funkce, kterou toto hradlo vykonává,
  44   a~èíslu $a(h)$ øíkáme {\I arita} hradla~$h$;
  45 \:zobrazením~$z: E \rightarrow {\bb N}$, které ka¾dé hranì vedoucí do~nìjakého
  46   hradla pøiøazuje nìkterý ze vstupù tohoto hradla.
  47 \endlist
  48
  49 \>Pøitom jsou splnìny následující podmínky:
  50
  51 \itemize\ibull
  52 \:$\forall i \in I: \deg^{+}(i)=0$ (do~vstupù nic nevede);
  53 \:$\forall o \in O: \deg^{+}(o)=1 \mathbin{\&} \deg^{-}(o)=0$ (z~výstupù nic nevede a do~ka¾dého vede právì jedna hrana);
  54 \:$\forall h \in H: \deg^{+}(v)=a(v)$ (do~ka¾dého hradla vede tolik hran, kolik je jeho arita);
  55 \:$\forall h \in H, 1\le j\le a(h)$ existuje právì jeden vrchol~$v$ takový, ¾e $z(vh)=j$
  56   (v¹echny vstupy hradel jsou zapojeny).
  57 \endlist
  58
  59 \s{Pozorování:} Kdybychom pøipustili hradla s~libovolnì vysokým poètem vstupù, mohli bychom
  60 libovolný problém se vstupem délky~$n$ vyøe¹it jedním hradlem o~$n$~vstupech, co¾ není
  61 ani realistické, ani pìkné. Proto pøijmìme omezení, ¾e v¹echna hradla budou mít maximálnì
  62 $k$ vstupù, kde~$k$ je nìjaká pevná konstanta, obvykle dvojka. Následující obrázky
  63 ukazují, jak hradla o~více vstupech nahradit dvouvstupovými:
  64
  65 \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}
  66
  67 \s{Definice:} {\I Výpoèet sítì} probíhá v taktech. V nultém taktu jsou definovány právì hodnoty
  68 vstupních portù. V~$i$-tém taktu vydají výsledek hradla, která jsou pøipojena na~porty
  69 nebo hradla, jejich¾ hodnota byla definována v~$(i-1)$-ním taktu. A¾ po~nìjakém koneèném
  70 poètu taktù budou definované i hodnoty výstupních portù, sí» se zastaví a vydá výsledek.
  71
  72 \figure{1_7_vypocet_site.eps}{Výpoèet hradlové sítì}{6cm}
  73
  74 \>Podle toho, jak sí» poèítá, si ji mù¾eme rozdìlit na~vrstvy:
  75
  76 \s{Definice:} {\I $i$-tá vrstva} obsahuje v¹echny vrcholy~$v$ takové, ¾e
  77 nejdel¹í cesta z~nìkterého z~portù sítì do~$v$ má délku právì~$i$. To jsou
  78 pøesnì vrcholy, které vydají výsledek poprvé v~$i$-tém taktu výpoètu.
  79 Dává tedy smysl prohlásit za~{\I èasovou slo¾itost} sítì poèet jejích
  80 vrstev. Podobnì {\I prostorovou slo¾itost} definujeme jako poèet hradel
  81 v~síti.
  82
  83 \s{Pøíklad:} Sestrojte sí», která zjistí, zda se mezi jejími~$n$ vstupy
  84 vyskytuje alespoò jedna jednièka.
  85
  86 \>{\I První øe¹ení:} zapojíme hradla za~sebe (sériovì). Èasová a prostorová
  87 slo¾itost jsou~$n$. Zde vùbec nevyu¾íváme toho, ¾e by mohlo poèítat více
  88 hradel souèasnì.
  89
  90 \figure{1_5_hloupy_or.eps}{Hradlová sí», která zjistí zda-li je na vstupu alespoò jedna jednièka}{7cm}
  91
  92 \>{\I Druhé øe¹ení:} Budeme vrcholy spojovat do~dvojic, pak výsledky z~tìchto
  93 dvojic opìt do~dvojic a tak dále. Tak dosáhneme èasové slo¾itosti $\log_2 n$,
  94 prostorová slo¾itost zùstane lineární.
  95
  96 \figure{1_4_chytry_or.eps}{Chytøej¹í øe¹ení stejného problému}{8cm}
  97
  98 \h{Sèítání dvou binárních èísel}
  99
 100 Mìjme dvì èísla zapsané ve~dvojkové soustavì jako $x_{n-1}\ldots x_1x_0$ a $y_{n-1}\ldots y_1y_0$.
 101 Budeme chtít spoèítat jejich souèet $z_nz_{n-1}\ldots z_1z_0$.
 102
 103 \h{Algoritmus základní ¹koly}
 104 Pøenosy oznaèíme $c_0$ a¾ $c_{n-1}$ v krocích poèítání, dodefinujeme $c_{-1}=0$. Algoritmus probíhá zleva od místa s nejni¾¹í vahou, viz Obrázek 1.7.
 105
 106 Výsledné èíslo $z_{n}...z_1z_0$ lze tedy vyjádøit pøedpisem: $$z_i=x_i \oplus y_i \oplus c_{i-1},$$ kde $\oplus$ znaèí operaci XOR. Pøenos nastane, pokud jsou alespoò dvì èísla jednièky, tedy
 107 $$c_i=(x_i \land y_i)\lor((x_i \lor y_i) \land c_{i-1})$$.
 108 \figure{1_6_hloupe_scitani.eps}{Obrázek 1.7 -- Sèítání}{8cm}
 109 Bohu¾el na to abychom spoèítali $z_i$ musíme znát hodnotu $c_{i-1}$, tedy mít spoèítané hodnoty pro v¹echny èísla men¹í ne¾ $i$. To dává lineární èasovou slo¾itost. Zamysleme se nad tím jak by se proces sèítání mohl zrychlit.
 110
 111 \h{Trik -- chování blokù souètu}
 112
 113 \figure{1_7_blok_scitani.eps}{Obrázek 1.8 -- Blok souètu}{8cm}
 114 \>Blok se mù¾e chovat tøemi rùznými zpùsoby:
 115
 116 \numlist{\ndotted}
 117 \:V¾dy vydá pøenos 0,
 118 \:V¾dy vydá pøenos 1,
 119 \:Kopíruje (pøedá dál).
 120 \endlist
 121
 122 \h{Rozdìlení a skládání blokù}
 123 \>Blok B lze rozdìlit na dva bloky p, q (pokud B není trivální).
 124 \figure{1_10_konvence_deleni_bloku.eps}{Obrázek 1.9 -- Dìlení blokù}{3cm}
 125
 126
 127 \h{Triviální bity}
 128 \figure{1_11_tabulka_kodovani.eps}{Obrázek 1.10 -- Tabulka triviálních bitù}{3cm}
 129
 130 \s{Tvrzení:} Ka¾dý blok mohu postavit z~triviálních bitù.
 131
 132 \proof
 133 Dùkaz indukcí z asociativity.
 134
 135
 136
 137 \h{Kódování typù chování blokù}
 138 %\>{\I Sem tabulku prosím :)}
 139
 140 \>Definujeme $(a,x)$:
 141 \itemize\ibull
 142 \:$(1,*) = <$,
 143 \:$(0,0) = 0$,
 144 \:$(0,1) = 1$
 145 \endlist
 146
 147 \>a operaci skládání blokù $\sigma$ pro kterou platí:
 148
 149 $(a,x) \sigma (b,y) = (c,z)$,
 150
 151 \>kde
 152
 153 $c = a \land b$,
 154
 155 $z = (\neg a \land x) \lor (a \land y)$.
 156
 157
 158
 159 \h{Lep¹í algoritmus sèítání}
 160 V na¹em pùvodním algoritmu ze základní ¹koly jsme mìli $\O(n)$ hradel v~$\O(n)$ hladinách. Algoritmus tedy nebyl paralelní a trval èas $\O(n)$.
 161
 162 \figure{1_9_deleni_bloku.eps}{Obrázek 1.11 -- Výpoèet pøenosu}{8cm}
 163 Víme pro ka¾dý blok velikosti $2^k$ na pozici dìlitelné $2^k$ jeho chování.
 164 Teï, kdy¾ u¾ známe v¹echny zbytky $c_0$ a¾ $c_n$, mù¾eme u¾ jednodu¹e v konstantním èase spoèítat výsledek.
 165
 166
 167
 168 \bye