\input ../lecnotes.tex

\prednaska{1}{Hradlové sítì}{(zapsali Jirka Fajfr a Ján Èerný)}

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

Na této pøedná¹ce se budeme zabývat jednoduchým modelem paralelního poèítaèe,
toti¾ hradlovou sítí, a uká¾eme si alespoò jeden efektivní paralelní algoritmus,
konkrétnì sèítání dvojkových èísel v~logaritmickém èase vzhledem k~jejich délce.

\h{Hradlové sítì}

\s{Definice:} {\I Hradlo} je zaøízení, které poèítá nìjakou pevnì danou funkci
s~$k$ vstupy a jedním výstupem.

\s{Pøíklad:} Obvykle pracujeme s~booleovskými hradly, ta pak odpovídají funkcím
$f: \{0,1\}^{k} \rightarrow \{0,1\} $. Z~nich nejèastìji potkáme:

\itemize\ibull
\:0-vstupové: to jsou konstanty {\sc true} a {\sc false},
\:1-vstupové: identita (ta je vcelku k~nièemu) a negace (znaèíme~$\lnot$),
\:2-vstupové: logický souèin ({\sc and},~$\land$) a souèet ({\sc or},~$\lor$).
\endlist

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

\figure{1_1_hradlo.eps}{Hradlo provádìjící logickou operaci {\sc and} se dvìma vstupy}{4cm}

Z~jednotlivých hradel pak vytváøíme hradlové sítì. Pokud pou¾íváme pouze booleovská
hradla, øíkáme takovým sítím {\I booleovské obvody,} pokud operace nad nìjakou obecnìj¹í
(ale koneènou) mno¾inou symbolù (abecedou), nazývají se {\I kombinaèní obvody.}
Ka¾dý vstup hradla je pøipojen buïto na~nìkterý ze~vstupù sítì nebo na~výstup nìjakého
jiného hradla. Výstupy hradel mohou být propojeny na výstupy sítì nebo pøivedeny
na~vstupy dal¹ích hradel, pøièem¾ je zakázáno vytváøet cykly. Ne¾ si øekneme
formální definici, podívejme se na obrázek.

\todo{OBR}

\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\}$);
\:mno¾inou {\I hradel} $H$, {\I vstupních portù} $I$ a {\I výstupních portù} $O$;
\:acyklickým orientovaným grafem~$(V,E)$, kde~$V = H \cup I \cup O$;
\:zobrazením~$F$, které ka¾dému hradlu $h\in H$ pøiøadí nìjakou funkci~$F(h):
  \Sigma^{a(h)} \rightarrow \Sigma$. To je funkce, kterou toto hradlo vykonává,
  a~èí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^{+}(i)=0$ (do~vstupù nic nevede);
\:$\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);
\:$\forall h \in H: \deg^{+}(v)=a(v)$ (do~ka¾dého hradla vede tolik hran, kolik je jeho arita);
\:$\forall h \in H, 1\le j\le a(h)$ existuje právì jeden vrchol~$v$ takový, ¾e $z(vh)=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, co¾ není
ani realistické, ani pìkné. Proto pøijmìme omezení, ¾e v¹echna hradla budou mít maximálnì
$k$ vstupù, kde~$k$ je nìjaká pevná konstanta, obvykle dvojka. Následující obrázky
ukazují, jak hradla o~více vstupech nahradit dvouvstupovými:

\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}

\s{Definice:} {\I Výpoèet sítì} probíhá v~{\I taktech.} V nultém taktu jsou definovány právì hodnoty
vstupních portù. V~$i$-tém taktu vydají výsledek hradla, která jsou pøipojena
na~porty nebo na~výstupy hradel, jejich¾ hodnota byla definována v~$(i-1)$-ním
taktu. A¾ po~nìjakém koneèném poètu taktù budou definované i hodnoty výstupních
portù, sí» se zastaví a vydá výsledek.

\figure{1_7_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} obsahuje v¹echny vrcholy~$v$ takové, ¾e
nejdel¹í z~cest z~portù sítì do~$v$ má délku právì~$i$. To jsou
pøesnì vrcholy, které vydají výsledek poprvé v~$i$-tém taktu výpoètu.
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:} Sestrojte 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á a prostorová
slo¾itost jsou~$n$. Zde vùbec nevyu¾íváme toho, ¾e by mohlo poèítat více
hradel souèasnì.

\figure{1_5_hloupy_or.eps}{Hradlová sí», která zjistí zda-li je na vstupu alespoò jedna jednièka}{7cm}

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

\figure{1_4_chytry_or.eps}{Chytøej¹í øe¹ení stejného problému}{8cm}

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

Pojïme se podívat na~zajímavìj¹í problém: Mìjme dvì èísla zapsané ve~dvojkové
soustavì jako $x_{n-1}\ldots x_1x_0$ a $y_{n-1}\ldots y_1y_0$. Budeme chtít
spoèítat jejich souèet $z_nz_{n-1}\ldots z_1z_0$.

Samozøejmì mù¾eme pou¾ít algoritmus \uv{sèítání pod sebou}, který nás
uèili na~základní ¹kole. Formálnì by se dal zapsat tøeba takto:
$$
z_i=x_i \oplus y_i \oplus c_{i-1},
$$
kde $\oplus$ znaèí operaci {\sc xor} (souèet modulo~2) a $c_{i-1}$ je {\I pøenos} z~$(i-1)$-ního
øádu do~$i$-tého. Pøenos pøitom nastane tehdy, kdy¾ ze~tøí xorovaných èíslic
jsou alespoò dvì jednièky:
$$
\eqalign{
c_{-1} &= 0 \cr
c_i &= (x_i \land y_i)\lor((x_i \lor y_i) \land c_{i-1}).\cr
}
$$

\figure{1_6_hloupe_scitani.eps}{Sèítání ze~základní ¹koly}{8cm}

Bohu¾el na to, abychom spoèítali $c_i$ (a~tedy~$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.

\h{Pøenosy v~blocích}

Jediné, co nás pøi sèítání brzdí, jsou pøenosy. Kdybychom je dokázali spoèítat rychle
(øeknìme v~logaritmické hloubce), souèet u¾ zvládneme dopoèítat v~konstantním èase.

Podívejme se na~libovolný {\I blok} v~na¹em souètu. Tak budeme øíkat èíslùm
$x_a\ldots x_b$ a $y_a\ldots y_b$ v~nìjakém intervalu indexù $\left<a,b\right>$.
Pøenos $c_b$ vystupující z~tohoto bloku závisí mimo hodnot sèítancù u¾ pouze
na~pøenosu $c_{a-1}$, který do bloku vstupuje. Záviset mù¾e pouze tøemi
mo¾nými zpùsoby:

\numlist\ndotted
\:generuje pøenos: $c_a=1$,
\:pohlcuje pøenos: $c_a=0$,
\:kopíruje pøenos: $c_a=c_{b-1}$.
\endlist

\figure{1_7_blok_scitani.eps}{Blok souètu}{8cm}

\s{Cvièení:} Rozmyslete si, jak pøesnì vypadají bloky s~jednotlivými typy chování.

Jednobitové bloky se chovají velice jednodu¹e:

\figure{1_11_tabulka_kodovani.eps}{Tabulka triviálních bitù}{3cm}

Pokud máme nìjaký vìt¹í blok~$B$ slo¾ený z~men¹ích blokù $p$ a~$q$, jejich¾
chování u¾ známe, mù¾eme z~toho odvodit, jak se chová velký blok:

\figure{1_10_konvence_deleni_bloku.eps}{Skládání chování blokù}{3cm}

V¹imòìme si, ¾e skládání chování blokù je asociativní operace (je to vlastnì
úplnì obyèejné skládání funkcí), tak¾e pro libovolný blok mù¾eme jeho
chování spoèítat v~èase $\O(\log n)$ postupným skládáním (\uv{stromeèkovým}
zpùsobem).

To nám dá nìjaký kombinaèní obvod nad trojprvkovou abecedou, ale samozøejmì
mù¾eme chování blokù kódovat i binárnì dvojicí bitù:

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

\>Operaci skládání $(a,x) \odot (b,y) = (c,z)$ pak definujeme takto:
$$
\eqalign{
c &= a \land b,\cr
z &= (\neg a \land x) \lor (a \land y).\cr
}
$$

\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~$n$
je mocnina dvojky, jinak si vstup doplníme nulami.

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

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

Algoritmus pracuje v~èase $\O(\log n)$. Hradel je dokonce 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 se
seète na~$\O(n)$.

\bye
