From de83fa8d6c6622158edc6b5aa05c7df89e481df5 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Wed, 2 Jan 2008 21:45:07 +0100 Subject: [PATCH] Opravena definice hradlovych siti, prepsan vyklad scitaciho algoritmu, ted uz snad bude srozumitelny. --- 1-hradla/1-hradla.tex | 164 ++++++++++++++++++++++++++---------------- 1 file changed, 101 insertions(+), 63 deletions(-) diff --git a/1-hradla/1-hradla.tex b/1-hradla/1-hradla.tex index 6b75cc1..9e8dd8a 100644 --- a/1-hradla/1-hradla.tex +++ b/1-hradla/1-hradla.tex @@ -2,13 +2,15 @@ \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 element, který poèítá nìjakou pevnì danou funkci +\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 @@ -17,12 +19,12 @@ $f: \{0,1\}^{k} \rightarrow \{0,1\} $. Z~nich nej \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-vstupuvé: logický souèin ({\sc and},~\&) a souèet ({\sc or},~$\lor$). +\: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} +\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¹í @@ -50,7 +52,7 @@ form \itemize\ibull \:$\forall i \in I: \deg^{+}(i)=0$ (do~vstupù nic nevede); -\:$\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); +\:$\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). @@ -64,17 +66,18 @@ ukazuj \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 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 hradla, 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. +\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¹í cesta z~nìkterého z~portù sítì do~$v$ má délku právì~$i$. To jsou +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 @@ -90,79 +93,114 @@ hradel sou \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 $\log_2 n$, +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í dvou binárních èísel} - -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$. - -\h{Algoritmus základní ¹koly} -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. - -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 -$$c_i=(x_i \land y_i)\lor((x_i \lor y_i) \land c_{i-1})$$. -\figure{1_6_hloupe_scitani.eps}{Obrázek 1.7 -- Sèítání}{8cm} -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. - -\h{Trik -- chování blokù souètu} - -\figure{1_7_blok_scitani.eps}{Obrázek 1.8 -- Blok souètu}{8cm} -\>Blok se mù¾e chovat tøemi rùznými zpùsoby: - -\numlist{\ndotted} -\:V¾dy vydá pøenos 0, -\:V¾dy vydá pøenos 1, -\:Kopíruje (pøedá dál). +\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$. +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 -\h{Rozdìlení a skládání blokù} -\>Blok B lze rozdìlit na dva bloky p, q (pokud B není trivální). -\figure{1_10_konvence_deleni_bloku.eps}{Obrázek 1.9 -- Dìlení blokù}{3cm} +\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í. -\h{Triviální bity} -\figure{1_11_tabulka_kodovani.eps}{Obrázek 1.10 -- Tabulka triviálních bitù}{3cm} +Jednobitové bloky se chovají velice jednodu¹e: -\s{Tvrzení:} Ka¾dý blok mohu postavit z~triviálních bitù. +\figure{1_11_tabulka_kodovani.eps}{Tabulka triviálních bitù}{3cm} -\proof -Dùkaz indukcí z asociativity. +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). -\h{Kódování typù chování blokù} -%\>{\I Sem tabulku prosím :)} +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ù: -\>Definujeme $(a,x)$: \itemize\ibull \:$(1,*) = <$, \:$(0,0) = 0$, \:$(0,1) = 1$ \endlist -\>a operaci skládání blokù $\sigma$ pro kterou platí: - -$(a,x) \sigma (b,y) = (c,z)$, - -\>kde - -$c = a \land b$, - -$z = (\neg a \land x) \lor (a \land y)$. - - - -\h{Lep¹í algoritmus sèítání} -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)$. - -\figure{1_9_deleni_bloku.eps}{Obrázek 1.11 -- Výpoèet pøenosu}{8cm} -Víme pro ka¾dý blok velikosti $2^k$ na pozici dìlitelné $2^k$ jeho chování. -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. - - +\>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 -- 2.39.2