4-hradla/4-hradla.tex

   1 \input ../lecnotes.tex
   2
   3 \prednaska{4}{Hradlové sítì}{(zapsal: Petr Jankovský)}
   4
   5 \def\land{\mathbin{\&}}
   6
   7 Výkon poèítaèù nelze zvy¹ovat donekoneèna a pøesto¾e ji¾ pìkných pár let platí,
   8 ¾e se jejich rychlost s~èasem exponenciálnì zvìt¹uje, jednou urèitì narazíme
   9 pøinejmen¹ím na~fyzikální limity.
  10
  11 Kdy¾ tedy nemù¾eme zvy¹ovat rychlost jednoho procesoru, jak poèítat rychleji?
  12 Øe¹ením by mohlo být poøídit si procesorù víc. U¾~dnes na~bì¾ném PéCéèku máme
  13 k~dispozici vícejádrové procesory, díky nim¾ mù¾eme vyu¾ít pararelní poèítání
  14 a úlohu øe¹it tak, ¾e práci ¹ikovnì rozdìlíme mezi procesory (èi jádra) a
  15 zamìstnáme je pøi~výpoètu v¹echny.
  16
  17 My se podíváme na~abstraktní výpoèetní model, který je je¹tì paralelnìj¹í.
  18 Techniky, které si uká¾eme na~tomto modelu, se v¹ak dají pøekvapivì vyu¾ít i~pøi~reálném
  19 paralelizování na~nìkolika málo procesorech. Konec koncù i proto, ¾e vnitøní
  20 architektura procesoru se na¹emu modelu velmi podobá. Budeme se zabývat
  21 jednoduchým modelem paralelního poèítaèe, toti¾ hradlovou sítí.
  22
  23 \h{Hradlové sítì}
  24
  25 \s{Definice:} {\I Hradlo} je prvek, který umí vyhodnocovat nìjakou funkci
  26 nad~koneènou abecedou $\Sigma$.
  27
  28 Obecnì se na~hradlo díváme jako na~funkci $f: {\Sigma}^{k} \rightarrow \Sigma$, která dostane $k$ vstupù
  29 a~vrátí jeden výstup, pøièem¾ hodnoty, nad~kterými pracuje, budou z~nìjaké koneèné
  30 abecedy -- tedy z~nìjaké koneèné mno¾iny symbolù $\Sigma$. Písmenku $k$ zde øíkáme {\I arita
  31 hradla}.
  32
  33 \s{Pøíklad:} Èasto studujeme hradla booleovská (pracující nad abecedou $\{0,1\}$), která poèítají logické funkce.
  34
  35 Z~nich nejèastìji potkáme:
  36
  37 \itemize\ibull
  38 \:nulární: to jsou konstanty (FALSE=0, TRUE=1),
  39 \:unární: napø. negace (znaèíme~$\lnot$),
  40 \:binární: logický souèin ({\sc and},~$\land$), souèet ({\sc or},~$\lor$), ...
  41 \endlist
  42
  43 \>Hradla kreslíme tøeba následovnì:
  44
  45 \figure{hradlo_and.eps}{Binární hradlo provádící logickou operaci {\sc and}.}{1in}
  46
  47 Jednotlivá hradla mù¾eme navzájem urèitým zpùsobem propojovat a vytváøet
  48 z nich {\I hradlové sítì}. Pokud pou¾íváme pouze booleovská hradla, øíkáme takto vytvoøeným
  49 sítím {\I booleovské obvody}. Pokud pracujeme s~operacemi nad nìjakou obecnìj¹í (ale koneènou)
  50 mno¾inou symbolù (abecedou), nazývají se {\I kombinaèní obvody.}
  51
  52 Ka¾dá hradlová sí» má nìjaké vstupy, nìjaké výstupy a uvnitø jsou propojovaná
  53 hradla. Ka¾dý vstup hradla je pøipojen buïto na~nìkterý ze~vstupù sítì nebo
  54 na~výstup jiného hradla. Výstupy hradel mohou být propojeny na~vstupy dal¹ích
  55 hradel (mohou se vìtvit), nebo na výstupy sítì. Pøitom máme zakázáno vytváøet
  56 cykly.
  57
  58 Ne¾ si øekneme formální definici, podívejme se na obrázek.
  59
  60 \figure{hradlova_sit.eps}{Hradlová sí» -- tøívstupová verze funkce {\I majorita}.}{3in}
  61
  62 Obrazek znázoròuje hradlovou sí», která poèítá, zda je alespoò na~dvou ze~vstupù
  63 jednièka. Pojïme si ale {\I hradlovou sí»} definovat formálnì.
  64
  65 \s{Definice:} {\I Hradlová sí»} je urèena:
  66 \itemize\ibull
  67 \:{\I abecedou} $\Sigma$ (to je nìjaká koneèná mno¾ina symbolù, obvykle $\Sigma=\{0,1\}$);
  68 \:po dvou disjunktními koneènými mno¾inami $I$~({\I vstupy}), $O$~({\I výstupy}) a~$H$~({\I hradla});
  69 \:acyklickým orientovaným multigrafem~$(V,E)$, kde~$V = I \cup O \cup H$;
  70 \:zobrazením~$F$, které ka¾dému hradlu $h\in H$ pøiøadí nìjakou funkci~$F(h):
  71   \Sigma^{a(h)} \rightarrow \Sigma$, co¾ je funkce, kterou toto hradlo vykonává.
  72   Èíslu $a(h)$ øíkáme {\I arita} hradla~$h$;
  73 \:zobrazením~$z: E \rightarrow {\bb N}$, které ka¾dé hranì vedoucí do~nìjakého
  74   hradla pøiøazuje nìkterý ze vstupù tohoto hradla.
  75 \endlist
  76
  77 \>Pøitom jsou splnìny následující podmínky:
  78
  79 \itemize\ibull
  80 \:$\forall i \in I: \deg^{in}(i)=0$ (do~vstupù nic nevede);
  81 \:$\forall o \in O: \deg^{in}(o)=1~\land~\deg^{out}(o)=0$ (z~výstupù nic nevede a do~ka¾dého vede právì jedna hrana);
  82 \:$\forall h \in H: \deg^{in}(v)=a(v)$ (do~ka¾dého hradla vede tolik hran, kolik je jeho arita);
  83 \:$\forall h \in H~\forall j: 1\le j\le a(h)$ existuje právì jedena hrana~$e$ taková, ¾e~$e$ konèí v~$h$ a~$z(e)=j$,
  84   (v¹echny vstupy hradel jsou zapojeny).
  85 \endlist
  86
  87 \s{Pozorování:} Kdybychom pøipustili hradla s~libovolnì vysokým poètem vstupù, mohli
  88 bychom libovolný problém se vstupem délky~$n$ vyøe¹it jedním hradlem o~$n$~vstupech,
  89 kterému bychom pøiøadili funkci, která by na¹i úlohu rovnou vyøe¹ila. Tento model
  90 v¹ak není ani realistický, ani pìkný. Proto pøijmìme omezení, ¾e~arity v¹ech hradel
  91 budou omezeny nìjakou pevnou konstantou $k$ (uká¾e se, ¾e nám bude staèit dvojka
  92 a~vystaèíme si tedy pouze s nulárními, unárními a binárními hradly).
  93 Následující obrázky ukazují, jak hradla o~více vstupech nahradit dvouvstupovými:
  94
  95 \twofigures{hradlo_ternor.eps}{Trojvstupové hradlo \sc or.}{0.5in}{hradlo_ternbior.eps}{Jeho nahrazení 2-vstupovými hradly.}{0.6in}
  96
  97
  98 Nyní bychom je¹tì mìli definovat, co taková hradlová sí» vlastnì poèítá a~jak
  99 její výpoèet probíhá.
 100
 101 \s{Definice:} {\I Výpoèet sítì} probíhá po~{\I taktech.} V nultém taktu jsou definovány pouze
 102 hodnoty na~vstupech sítì a na~výstupech hradel arity 0. Mù¾eme si to pøedstavit
 103 tak, ¾e na~zaèátku nemá ¾ádné hradlo definovánu výstupní hodnotu (a¾ na ji¾
 104 zmínìná hradla nulární). V~ka¾dém dal¹ím taktu pak vydají výstup hradla, která
 105 na~konci minulého taktu mìla definovány v¹echny hodnoty na vstupech. Jakmile
 106 budou po~nìjakém koneèném poètu taktù definované i hodnoty v¹ech výstupù, sí»
 107 se zastaví a~vydá výsledek.
 108
 109 \s{Pozorování:} Proto¾e je sí» acyklická, je jasné, ¾e jakmile jednou nìjaké hradlo vydá
 110 výstup, tak se tento výstup bìhem dal¹ího výpoètu sítì ji¾ nezmìní.
 111
 112 \figure{vypocet_site.eps}{Výpoèet hradlové sítì.}{6cm}
 113
 114 \>Podle toho, jak sí» poèítá, si ji mù¾eme rozdìlit na~vrstvy:
 115
 116 \s{Definice:} {\I $i$-tá vrstva $S_i$} obsahuje právì takové vrcholy~$v$, pro~které nejdel¹í cesta ze~vstupù
 117 sítì do $v$ má délku rovnou~$i$.
 118
 119 \s{Pozorování:} V¹imnìme si, ¾e v $i$-tém taktu vydají hodnoty právì hradla z $S_i$.
 120
 121 Dává tedy smysl prohlásit za~{\I èasovou slo¾itost} sítì poèet
 122 jejích vrstev. Podobnì {\I prostorovou slo¾itost} definujeme jako poèet hradel v~síti.
 123
 124 \s{Pøíklad:} Sestrojme sí», která zjistí, zda se mezi jejími~$n$ vstupy
 125 vyskytuje alespoò jedna jednièka.
 126
 127 \>{\I První øe¹ení:} zapojíme hradla za~sebe (sériovì). Èasová i prostorová
 128 slo¾itost odpovídají~$\Theta(n)$. Zde ov¹em vùbec nevyu¾íváme toho, ¾e by mohlo poèítat více
 129 hradel souèasnì.
 130
 131 \figure{hloupy_or.eps}{Hradlová sí», která zjistí, zdali je na vstupu alespoò jedna jednièka.}{0.7in}
 132
 133 \>{\I Druhé øe¹ení:} Hradla budeme spojovat do~dvojic, pak výsledky z~tìchto dvojic opìt
 134 do~dvojic a tak dále. Díky paralelnímu zapojení dosáhneme èasové slo¾itosti $\Theta(\log n)$,
 135 prostorová slo¾itost zùstane lineární.
 136
 137 \figure{chytry_or.eps}{Chytøej¹í øe¹ení stejného problému pro vstup velikosti 16.}{3in}
 138
 139 \bye