Oziveni hradlovych siti a bitonickeho trideni, zatim bez uprav

[ads2.git] / 5-hradla / 5-hradla.tex

\input ../lecnotes.tex

\prednaska{5}{Hradlové sítì}{}

\def\land{\mathbin{\&}}

Výkon poèítaèù nelze zvy¹ovat donekoneèna a pøesto¾e ji¾ pìkných pár let platí,
¾e se jejich rychlost s~èasem exponenciálnì zvìt¹uje, jednou urèitì narazíme
pøinejmen¹ím na~fyzikální limity.

Kdy¾ tedy nemù¾eme zvy¹ovat rychlost jednoho procesoru, jak poèítat rychleji?
Øe¹ením by mohlo být poøídit si procesorù víc. U¾~dnes na~bì¾ném PéCéèku máme
k~dispozici vícejádrové procesory, díky nim¾ mù¾eme vyu¾ít pararelní poèítání
a úlohu øe¹it tak, ¾e práci ¹ikovnì rozdìlíme mezi procesory (èi jádra) a
zamìstnáme je pøi~výpoètu v¹echny.

My se podíváme na~abstraktní výpoèetní model, který je je¹tì paralelnìj¹í.
Techniky, které si uká¾eme na~tomto modelu, se v¹ak dají pøekvapivì vyu¾ít i~pøi~reálném
paralelizování na~nìkolika málo procesorech. Konec koncù i proto, ¾e vnitøní
architektura procesoru se na¹emu modelu velmi podobá. Budeme se zabývat 
jednoduchým modelem paralelního poèítaèe, toti¾ hradlovou sítí.

\h{Hradlové sítì}

\s{Definice:} {\I Hradlo} je prvek, který umí vyhodnocovat nìjakou funkci
nad~koneènou abecedou $\Sigma$.

Obecnì se na~hradlo díváme jako na~funkci $f: {\Sigma}^{k} \rightarrow \Sigma$, která dostane $k$ vstupù
a~vrátí jeden výstup, pøièem¾ hodnoty, nad~kterými pracuje, budou z~nìjaké koneèné
abecedy -- tedy z~nìjaké koneèné mno¾iny symbolù $\Sigma$. Písmenku $k$ zde øíkáme {\I arita
hradla}.

\s{Pøíklad:} Èasto studujeme hradla booleovská (pracující nad abecedou $\{0,1\}$), která poèítají logické funkce.

Z~nich nejèastìji potkáme:

\itemize\ibull
\:nulární: to jsou konstanty (FALSE=0, TRUE=1),
\:unární: napø. negace (znaèíme~$\lnot$),
\:binární: logický souèin ({\csc and},~$\land$), souèet ({\csc or},~$\lor$), ...
\endlist

\>Hradla kreslíme tøeba následovnì:

\figure{hradlo_and.eps}{Binární hradlo provádící logickou operaci {\csc and}.}{1in}

Jednotlivá hradla mù¾eme navzájem urèitým zpùsobem propojovat a vytváøet
z nich {\I hradlové sítì}. Pokud pou¾íváme pouze booleovská hradla, øíkáme takto vytvoøeným
sítím {\I booleovské obvody}. Pokud pracujeme s~operacemi nad nìjakou obecnìj¹í (ale koneènou) 
mno¾inou symbolù (abecedou), nazývají se {\I kombinaèní obvody.}

Ka¾dá hradlová sí» má nìjaké vstupy, nìjaké výstupy a uvnitø jsou propojovaná
hradla. Ka¾dý vstup hradla je pøipojen buïto na~nìkterý ze~vstupù sítì nebo
na~výstup jiného hradla. Výstupy hradel mohou být propojeny na~vstupy dal¹ích
hradel (mohou se vìtvit), nebo na výstupy sítì. Pøitom máme zakázáno vytváøet
cykly. 

Ne¾ si øekneme formální definici, podívejme se na obrázek.

\figure{hradlova_sit.eps}{Hradlová sí» -- tøívstupová verze funkce {\I majorita}.}{3in}

Obrazek znázoròuje hradlovou sí», která poèítá, zda je alespoò na~dvou ze~vstupù
jednièka. Pojïme si ale {\I hradlovou sí»} definovat formálnì.

\s{Definice:} {\I Hradlová sí»} je urèena:
\itemize\ibull
\:{\I abecedou} $\Sigma$ (to je nìjaká koneèná mno¾ina symbolù, obvykle $\Sigma=\{0,1\}$);
\:po dvou disjunktními koneènými mno¾inami $I$~({\I vstupy}), $O$~({\I výstupy}) \hfil\break a~$H$~({\I hradla});
\:acyklickým orientovaným multigrafem~$(V,E)$, kde~$V = I \cup O \cup H$;
\:zobrazením~$F$, které ka¾dému hradlu $h\in H$ pøiøadí nìjakou funkci~$F(h):
  \Sigma^{a(h)} \rightarrow \Sigma$, co¾ je funkce, kterou toto hradlo vykonává.
  Èíslu $a(h)$ øíkáme {\I arita} hradla~$h$;
\:zobrazením~$z: E \rightarrow {\bb N}$, které ka¾dé hranì vedoucí do~nìjakého
  hradla pøiøazuje nìkterý ze vstupù tohoto hradla.
\endlist

\>Pøitom jsou splnìny následující podmínky:

\itemize\ibull
\:$\forall i \in I: \deg^{in}(i)=0$ (do~vstupù nic nevede);
\:$\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);
\:$\forall h \in H: \deg^{in}(v)=a(v)$ (do~ka¾dého hradla vede tolik hran, kolik je jeho arita);
\:$\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$, 
  (v¹echny vstupy hradel jsou zapojeny).
\endlist

\s{Pozorování:} Kdybychom pøipustili hradla s~libovolnì vysokým poètem vstupù, mohli
bychom libovolný problém se vstupem délky~$n$ vyøe¹it jedním hradlem o~$n$~vstupech,
kterému bychom pøiøadili funkci, která by na¹i úlohu rovnou vyøe¹ila. Tento model
v¹ak není ani realistický, ani pìkný. Proto pøijmìme omezení, ¾e~arity v¹ech hradel
budou omezeny nìjakou pevnou konstantou $k$ (uká¾e se, ¾e nám bude staèit dvojka
a~vystaèíme si tedy pouze s nulárními, unárními a binárními hradly). 
Následující obrázky ukazují, jak hradla o~více vstupech nahradit dvouvstupovými:

\twofigures{hradlo_ternor.eps}{Trojvstupové hradlo \csc or.}{0.5in}{hradlo_ternbior.eps}{Jeho nahrazení 2-vstupovými hradly.}{0.6in}


Nyní bychom je¹tì mìli definovat, co taková hradlová sí» vlastnì poèítá a~jak
její výpoèet probíhá.

\s{Definice:} {\I Výpoèet sítì} probíhá po~{\I taktech.} V nultém taktu jsou definovány pouze 
hodnoty na~vstupech sítì a na~výstupech hradel arity 0. Mù¾eme si to pøedstavit
tak, ¾e na~zaèátku nemá ¾ádné hradlo definovánu výstupní hodnotu (a¾ na ji¾ 
zmínìná hradla nulární). V~ka¾dém dal¹ím taktu pak vydají výstup hradla, která
na~konci minulého taktu mìla definovány v¹echny hodnoty na vstupech. Jakmile
budou po~nìjakém koneèném poètu taktù definované i hodnoty v¹ech výstupù, sí»
se zastaví a~vydá výsledek.

\s{Pozorování:} Proto¾e je sí» acyklická, je jasné, ¾e jakmile jednou nìjaké hradlo vydá
výstup, tak se tento výstup bìhem dal¹ího výpoètu sítì ji¾ nezmìní.

\figure{vypocet_site.eps}{Výpoèet hradlové sítì.}{6cm}

\>Podle toho, jak sí» poèítá, si ji mù¾eme rozdìlit na~vrstvy:

\s{Definice:} {\I $i$-tá vrstva $S_i$} obsahuje právì takové vrcholy~$v$, pro~které nejdel¹í cesta ze~vstupù
sítì do $v$ má délku rovnou~$i$.

\s{Pozorování:} V¹imnìme si, ¾e v $i$-tém taktu vydají hodnoty právì hradla z $S_i$.
 
Dává tedy smysl prohlásit za~{\I èasovou slo¾itost} sítì poèet
jejích vrstev. Podobnì {\I prostorovou slo¾itost} definujeme jako poèet hradel v~síti.

\s{Pøíklad:} Sestrojme sí», která zjistí, zda se mezi jejími~$n$ vstupy
vyskytuje alespoò jedna jednièka.

\>{\I První øe¹ení:} zapojíme hradla za~sebe (sériovì). Èasová i prostorová
slo¾itost odpovídají~$\Theta(n)$. Zde ov¹em vùbec nevyu¾íváme toho, ¾e by mohlo poèítat více
hradel souèasnì.

\figure{hloupy_or.eps}{Hradlová sí», která zjistí, zdali je na vstupu alespoò jedna jednièka.}{0.7in}

\>{\I Druhé øe¹ení:} Hradla budeme spojovat do~dvojic, pak výsledky z~tìchto dvojic opìt
do~dvojic a tak dále. Díky paralelnímu zapojení dosáhneme èasové slo¾itosti $\Theta(\log n)$,
prostorová slo¾itost zùstane lineární.

\figure{chytry_or.eps}{Chytøej¹í øe¹ení stejného problému pro vstup velikosti 16.}{3in}

Minule jsme si zavedli paralelní výpoèetní model, ve kterém si nyní nìco naprogramujeme \dots

\h{Sèítání binárních èísel}

Mìjme dvì èísla $x$ a $y$ zapsané ve~dvojkové soustavì. Jejich èíslice oznaème
$x_{n-1}\ldots x_0$ a $y_{n-1}\ldots y_0$, kde $i$-tý øád má váhu $2^i$. Nyní budeme chtít tato èísla
seèíst.

K tomuto úèelu se~ihned nabízí pou¾ít starý dobrý \uv{¹kolní algoritmus}, který
funguje ve~dvojkové soustavì stejnì dobøe jako v~desítkové. Zkrátka sèítáme èísla
zprava doleva. V¾dy seèteme pøíslu¹né èíslice pod~sebou a~pøièteme pøenos z~ni¾¹ího
øádu. Tím dostaneme jednu èíslici výsledku a~pøenos do~vy¹¹ího øádu. Formálnì
bychom to mohli zapsat tøeba takto:
$$
z_i=x_i \oplus y_i \oplus c_i,
$$
kde $z_i$ je $i$-tá èíslice souètu, $\oplus$ znaèí operaci {\csc xor} (souèet modulo~2) a~$c_i$ je {\I pøenos}
z~$(i-1)$-ního øádu do~$i$-tého. Pøenos pøitom nastane tehdy, pokud se~nám potkají
dvì jednièky pod~sebou, nebo kdy¾ se~vyskytne alespoò jedna jednièka a~k~tomu
pøenos z~ni¾¹ího øádu. Jinými slovy tehdy, kdy¾ ze~tøí xorovaných èíslic jsou alespoò
dvì jednièky (pomocí obvodu pro majoritu z minulé pøedná¹ky lehce zkonstruujeme):
$$
\eqalign{
c_{0} &= 0, \cr
c_{i+1} &= (x_i~\&~y_i)\lor(x_i~\&~c_i)\lor(y_i~\&~c_i).\cr
}
$$

Takovéto sèítání sice perfektnì funguje, nicménì je bohu¾el pomìrnì pomalé.
Pokud bychom stavìli hradlovou sí» podle tohoto pøedpisu, byla by slo¾ená z~nìjakých
podsítí (\uv{krabièek}), které budou mít na~vstupu $x_i$, $y_i$ a~$c_i$ a jejich výstupem
bude $z_i$ a~$c_{i+1}$. 

\figure{hloupe_scitani.eps}{Sèítání ¹kolním algoritmem.}{1.5in}

V¹imìme si, ¾e~ka¾dá krabièka závisí na~výstupu té pøedcházející. Jednotlivé
krabièky tedy musí urèitì le¾et na~rùzných hladinách. Celkovì bychom museli pou¾ít
$\Theta{(n)}$ hladin a~jeliko¾ je ka¾dá krabièka konstantnì velká, také $\Theta{(n)}$ hradel. To dává
lineární èasovou i~prostorovou slo¾itost, èili oproti sekvenènímu algoritmu jsme si nepomohli.

Zamysleme se nad tím, jak by se proces sèítání mohl zrychlit.

\h{Pøenosy v~blocích}
Jediné, co nás pøi sèítání brzdí, jsou pøenosy mezi jednotlivými øády. Ka¾dý øád,
aby~vydal souèet, musí poèkat na~to, a¾~dopoèítají v¹echny pøedcházející øády.
Teprve pak se~toti¾ dozví pøenos. Kdybychom ov¹em pøenosy dokázali spoèítat
nìjakým zpùsobem paralelnì, máme vyhráno. Jakmile známe v¹echny pøenosy, souèet
u¾~zvládneme dopoèítat na~konstantnì mnoho hladin -- tedy v~konstantním èase.

Podívejme se na~libovolný {\I blok} v~na¹em souètu. Tak budeme øíkat èíslùm
$x_j\ldots x_i$ a $y_j\ldots y_i$ v~nìjakém intervalu indexù $\left<i,j\right>$. Pøenos $c_{j+1}$ vystupující z~tohoto bloku závisí mimo hodnot sèítancù u¾ pouze na~pøenosu $c_{i}$, který do bloku vstupuje.

\figure{blok_scitani.eps}{Blok souètu.}{3in}

Z tohoto pohledu se mù¾eme na blok také dívat jako na nìjakou funkci, která
dostane jednobitový vstup a vydá jednobitový výstup. To je nám pøíjemné, nebo» 
takových funkcí existují jenom ètyøi typy:
\numlist\ndotted
\:$f(x) = 0$,  ~~~~(0)
\:$f(x) = 1$,  ~~~~(1)
\:$f(x) = x$,  ~~~~($<$ -- kopírování)
\:$f(x) = \neg{x}$.
\endlist
Jak se za~chvíli uká¾e, poslední pøípad, kdy by~nìjaký blok pøedával opaèný
pøenos, ne¾ do~nìj vstupuje, navíc nikdy nemù¾e nastat. Pojïme si to rozmyslet.
Jednobitové bloky se chovají velice jednodu¹e:

\figure{bloky_1bit.eps}{Tabulka triviálních blokù.}{1.1in}

Z prvního bloku evidentnì v¾dy vyleze 0, a»~do~nìj vstoupí jakýkoli pøenos.
Poslední blok naopak sám o~sobì pøenos vytváøí, a»~ji¾ do~nìj vleze jakýkoliv.
Bloky prostøední se chovají stejnì, a~to tak, ¾e~samy o~sobì ¾ádný pøenos nevytvoøí,
ale~pokud do~nich nìjaký pøijde, tak~také odejde.

Mìjme nyní nìjaký vìt¹í blok~$C$ slo¾ený ze~dvou men¹ích podblokù $A$ a~$B$, jejich¾
chování u¾ známe. Z~toho mù¾eme odvodit, jak se chová celý blok:

\figure{tabulka_skladani_bloku.eps}{Skládání chování blokù.}{1.3in}

Pokud vy¹¹í blok pøenos pohlcuje, pak a»~se u¾~ni¾¹í blok chová jakkoli, slo¾ení
tìchto blokù musí v¾dy pohlcovat. V~prvním øádku tabulky jsou tudí¾ nuly. Analogicky,
pokud vy¹¹í blok generuje pøenos, tak~ten ni¾¹í na~tom nic nezmìní. V~druhém
øádku tabulky jsou tedy samé jednièky. Zajímavìj¹í pøípad nastává, pokud vy¹¹í blok
kopíruje -- tehdy zále¾í èistì na~chování ni¾¹ího bloku.

V¹imnìme si, ¾e~skládání chování blokù je vlastnì úplnì obyèejné skládání
funkcí. Nyní bychom mohli prohlásit, ¾e~budeme poèítat nad~tøíprvkovou abecedou,
a~¾e~celou tabulku doká¾eme spoèítat jedním jediným hradlem. Pojïmì si v¹ak
rozmyslet, jak~bychom takovouto vìc popsali èistì binárnì. Jak tedy tyto tøi stavy
popisovat pouze nìkolika bity?

Evidentnì nám k tomuto binárnímu zakódování tøí stavù budou staèit bity dva.
Oznaème si je jako $p$ a $q$. Tato dvojice mù¾e nabývat hned ètyø mo¾ných hodnot,
kterým pøiøadíme tøi mo¾ná chování bloku. Toto kódování mù¾eme zvolit zcela
libovolnì, ale pokud si ho zvolíme ¹ikovnì, u¹etøíme si dále práci pøi kompozici.
Zvolme si tedy kódování takto:

\itemize\ibull
\:$(1,*) = <$,
\:$(0,0) = 0$,
\:$(0,1) = 1$
\endlist

Tomu, ¾e blok kopíruje, odpovídá dvojice $p = 1$; $q =$ \<cokoliv>. V~ostatních
pøípadech bude~$p$ nulové a~$q$ nám bude øíkat, co je na~výstupu pøíslu¹ného bloku.
Jinými slovy $p = 0$ znamená, ¾e funkce je konstanta, pøièem¾ $q$ øíká jaká; naproti
tomu $p = 1$~znamená, ¾e funkce je identita, a»~u¾~je $q$ cokoli.

Pojïme si nyní ukázat, jak bude celé skládání blokù vypadat. Rozmysleme si,
kdy je~$p$ celého dvojbloku jednièkové, tedy kdy celý dvojblok kopíruje. To nastane
tehdy, pokud kopírují obì jeho èásti, a tedy  $p = p_a~\&~p_b$. Dále $q$ bude rovno jednièce,
pokud $q = (\neg{p_a}~\&~q_a) \lor (p_a~\&~q_b)$.

Skládání chování blokù lze tedy popsat buï ternárnì -- tabulkou, ale lze to
i~binárnì vý¹e uvedeným pøedpisem.

Nyní si tedy mù¾eme dopøedu vypoèítat chování bloku velikosti jedna, poté
 z~nich skládáním blokù velikosti dva, dál velikosti ètyøi, osm, atd \dots

\h{Paralelní sèítání}

Paralelní algoritmus na~sèítání u¾~zkonstruujeme pomìrnì snadno. Bez újmy
na~obecnosti budeme pøedpokládat, ¾e~poèet bitù vstupních èísel je mocnina dvojky,
jinak si vstup doplníme nulami, co¾ výsedný èas bìhu algoritmu zhor¹í maximálnì
konstanta-krát.

\algo
\:Spoèteme chování blokù velikosti~1. ($\O(1)$ hladin)
\:Postupnì poèítáme chování blokù\foot{myslíme \uv{pøirozenì zarovnané} bloky, tedy takové, jejich¾ poloha je násobkem velikosti} velikosti 2, 4, 8, ..., $2^k$. 
  ($\O(\log n)$ hladin, na~nich¾ se skládají bloky)
\:$c_0 \leftarrow 0$ (pøenos do nejni¾¹ího øádu je v¾dy 0)
\:Urèíme $c_n$ podle $c_0$ a chování (jediného) bloku velikosti~$n$.
\:Postupnì dopoèítáme pøenosy na~hranicích dìlitelných $2^k$ \uv{zahu¹»ováním}:
  jakmile víme $c_{2^k}$, mù¾eme dopoèítat $c_{2^k+2^{k-1}}$ podle
  chování bloku $\left< 2^k, 2^k+2^{k-1}\right>$. ($\O(\log n)$ hladin,
  na~nich¾ se dosazuje)
\:Seèteme: $\forall i: z_i = x_i \oplus y_i \oplus c_i$.
\endalgo

\figure{1_9_deleni_bloku.eps}{Výpoèet pøenosu.}{2.5in}

Algoritmus pracuje v~èase $\O(\log n)$. Hradel je pou¾ito lineárnì: na~jednotlivých
hladinách kroku~2 poèet hradel exponenciálnì klesá od~$n$ k~1, na~hladinách kroku~5
exponenciálnì stoupá od~1 k~$n$, tak¾e dohromady se seète na~$\Theta(n)$.

\h{Paralelní násobení}

Podobnì jako u~sèítání si vzpomeneme na~¹kolní algoritmus -- tentokráte v¹ak pro násobení.
To fungovalo tak, ¾e~jsme si jedno ze~dvou binárních èísel na~vstupu (øíkejme mu tøeba $x$) $n$-krát posouvali. Tam kde pak byly v~èísle~$y$ jednièky, pøíslu¹né kopie $x$ jsme seèetli. Jinými slovy tedy násobení umíme pøevést na~nìjaké posuny (ty lze realizovat pouze \uv{pøedrátováním} -- nic nás nestojí), násobení jedním bitem (co¾ je 
{\csc and} ) a~nakonec potøebujeme výsledných~$n$ èísel seèíst.
\figure{skolni_scitani.eps}{©kolní sèítání.}{2in}

Jak nyní seèíst $n$ $n$-bitových èísel..? Nabízí se vyu¾ít osvìdèený \uv{stromeèek} -- sèítat dvojice èísel, výsledky pak opìt po~dvojicích seèíst, a¾ na~konci vyjde jediný výsledek.
\figure{stromecek.eps}{Stromeèek}{1.4in}

Toto øe¹ení by v¹ak vedlo na~èasovou slo¾itost $\Theta (\log^2 n)$, nebo» sèítat umíme v~èase $\Theta (\log n)$. To je sice dle na¹ich mìøítek
docela efektivní, ale pøekvapivì to jde je¹tì lépe -- toti¾ na~$\Theta (\log n)$ hladin. Této 
slo¾itosti dosáhneme malým trikem.

Vymyslíme obvod konstantní hloubky, který na~vstupu dostane tøi èísla. Odpoví pak dvìma èísly
takovými, ¾e budou mít stejný souèet jako pùvodní tøi èísla. Jinými slovy pomocí
tohoto obvodu budeme umìt seètení tøí èísel pøevést na seètení dvou èísel.

\figure{obvod.eps}{$x+y+z = p+q$}{0.3in}

V¹imnìme si, ¾e~kdy¾ sèítáme tøi bity, mù¾e být pøenos do~vy¹¹ího øádu nula èi~jednièka. Vezmeme si tedy bity $x_i$, $y_i$, $z_i$ a~ty seèteme. To nám dá dvoubitový výsledek, pøièem¾ ni¾¹í bit z~tohoto výsledku po¹leme do~èísla~$p$, vy¹¹í do~èísla~$q$.

\figure{obvod_real.eps}{Redukování sèítání}{1.2in}

Toto zredukování sèítání nám nyní umo¾ní opìt stavit strom, by» o malièko slo¾itìj¹í.

\figure{sl_stromecek.eps}{Slo¾itìj¹í stromeèek}{0.9in}

Pokud jsme mìli na~zaèátku $n$ èísel, po~první redukci nám jich zbývá jen $2/3 \cdot n$ a~obecnì v~$k$-té hladiné $(2/3)^k \cdot n$. Znamená to, ¾e èísel nám ubývá exponenciálnì, tak¾e poèet hladin bude logaritmický. Redukující obvod je pøi tom jen konstantnì hluboký, tak¾e celé redukování zvládneme v~èase $\Theta (\log n)$. Na~konci Slo¾itìj¹ího stromeèku pak máme umístìnou jednu obyèejnou sèítaèku, která zbývající dvì èísla seète v~logaritmickém èase.

Seètení v¹ech $n$ èísel tedy zabere $\Theta (\log n)$ hladin.

Kdy¾ se nyní vrátíme k~násobení, zbývá nám vyøe¹it posouvání a~{\csc and}ování. Uvìdomme si, ¾e to je plnì paralelení a~zvládneme ho za~konstantnì mnoho hladin. Celé násobení tedy zvládneme v~logaritmickém èase.

\bye