1-hradla/1-hradla.tex

   1 \input ../lecnotes.tex\r
   2 \r
   3 \prednaska{1}{Paralelní algoritmy}{(zapsal Jirka Fajfr a Ján Èerný)}\r
   4 \r
   5 \r
   6 \h{Hradlo}\r
   7 Jedná se o obvod provádìjící elementární binární operace (AND, OR, ...). Ka¾dé hradlo má k-vstupù a právì jeden výstup. Mù¾eme si ho pøedstavit jako funkci\r
   8 $$f : \{0,1\}^{k} \rightarrow \{0,1\}$$\r
   9 \>kde $k$ je poèet vstupù. Pøíklad dvouvstupového hradla provádìjícího operaci AND je na Obrázku 1.1\r
  10 \figure{1_1_hradlo.eps}{Obrázek 1.1 - Hradlo provádìjící logickou operaci AND se dvìma vstupy}{4cm}\r
  11 %\>speciálním pøípadem je hradlo s poètem vstupù $k$ rovným nule. Toto hradlo pova¾ujeme za konstantu. \r
  12 \r
  13 \h{Druhy hradlových sítí}\r
  14 \itemize\ibull\r
  15 \:boolovské obvody (maximálnì dvoustavová hradla)\r
  16 \:kombinaèní obvod (hradla s mnoha stavy)\r
  17 \endlist\r
  18 \r
  19 \h{Hradlová sí»}\r
  20 Hradlová sí» je obvod slo¾ený ze soustavy navzájem propojených hradel, vstupních a výstupních portù. Dohromady tvoøí acyklický orientovaný graf s vrcholy $V = I \cup O \cup H$ a hranami $E$. Hradlová sí» musí splòovat následující podmínky\r
  21 \numlist{\ndotted}\r
  22 \:Výsledný graf je acyklický\r
  23 \:Do ¾ádného vstupu (hradla) nevede více ne¾ jedna hrana\r
  24 \:V¹echny kromì vstupních portù jsou zapojeny\r
  25 \:Do vstpních portù nic nevede (vstupní port není výsledkem ¾ádného hradla)\r
  26 \:Výstupní porty nejsou zapojeny (nejsou zdrojem ¾ádného hradla)\r
  27 \endlist   \r
  28 \r
  29 \s{Vícevstupové hradlo s neomezeným poètem vstupù:} nepraktické (nerealizovatelné) vìt¹inou se poèet vstupù omezuje konstantou (\#)\r
  30 \figure{1_2_vice_vstupove_hradlo.eps}{Obrázek 1.2 - Trojvstupové hradlo na funkci AND}{3cm}\r
  31 \r
  32 \s{Vícevstupové hradlo:} hradlo z Obrázku 1.2, lze jednodu¹e simulovat soustavou dvou dvouvstupových hradel\r
  33 \figure{1_3_vice_vstupove_hradlo.eps}{Obrázek 1.3 - Dvouvstupové hradlo simulující funkci trojvstupového AND}{3cm}\r
  34 \r
  35 \s{Definice:} {\I Hradlová sí»} je obvod slo¾ený ze soustavy hradel tvoøící acyklický orientovaný graf s vrcholy $V = I \cup O \cup H$ \foot{I - vstupní porty, O - výstupní porty, H - hradla} a hranami $E$, takovými, ¾e \r
  36 \numlist{\ndotted}\r
  37 \:$\forall v \in I : deg^{+}(v) = 0$\r
  38 \:$\forall v \in O : deg^{-}(v) = 0, deg^{+}(v) = 1$\r
  39 \:$\forall v \in H: \exists f(v) : \left\{0,1\right\}^{a(v)} \rightarrow \left\{0,1\right\}$\ \ \ \foot{$f(v)$ je funkce vykonávaná hradlem a $a(v)$ je arita této funkce}\r
  40 \endlist\r
  41 \r
  42 \>$deg^{+}(v) = a(v)$, hrany vstupující do hradla jsou oèíslovány $1 \ldots a(v)$.\r
  43 Navíc $\forall v \in H : a(v) \leq 2$.\r
  44 \r
  45 \s{Definice:} {\I Konstanta} je hradlo $v$, pro které platí $\#vstupù=0$, tedy ¾e nemá ¾ádné vstupy. \r
  46 \r
  47 \s{Definice:} {\I Výpoèet sítì} probíhá v taktech. V 0tém taktu jsou definované právì vstupy.\r
  48 V i-tém taktu vydají výsledek hradla, která mìla definována vstupy v $(i - 1)$tém taktu. \r
  49 Kdy¾ jsou definovány hodnoty v¹ech hradel a portù. Sí» se zastaví a vydá výsledek.\r
  50 \figure{1_7_vypocet_site.eps}{Obrázek 1.4 - Výpoèet hradlové sítì}{6cm}\r
  51 \r
  52 \s{Definice:} {\I i-tá vrstva} $\equiv$ vrcholy takové, ¾e $max$ $d(w, v) = i$, kde $w \in I$ a $v \in V$\r
  53 \r
  54 \s{Slo¾itosti:} Èasová slo¾itost je rovna \#poètu vrstev. Prostorová slo¾itost \#hradel sítì \r
  55 \s{Pøíklady:}\r
  56 Je na vstupu alespoò 1 jednièka?\r
  57 \r
  58 \>{\I První øe¹ení: } zapojíme hradla sériovì za sebou. Èasová a prostorová slo¾itost n (kde n je \# hradel). Hloupé øe¹ení. Nevyu¾íváme paraleního výpoètu, v¾dy mù¾e poèítat jen jedno hradlo. \r
  59 \figure{1_5_hloupy_or.eps}{Obrázek 1.5 - Hradlová sí», která zjistí zda-li je na vstupu alespoò jedna jednièka}{7cm}\r
  60 \r
  61 \>{\I Druhé øe¹ení: } chytøej¹í øe¹ení. Èasová slo¾itost $log(n)$, prostorová slo¾itost n. Výpoèet probíhá správnì po vrstvách\r
  62 \figure{1_4_chytry_or.eps}{Obrázek 1.6 - Chytøej¹í implementace stejného problému}{8cm}\r
  63 \r
  64 \r
  65 \h{Sèítání dovou binárních èísel}\r
  66 Máme 2 èísla délky n, oznaèíme $x_i$, $y_i$ èíslice na jejich i-tých místech, $i=0,1,..n-1$, tj $x = x_{n-1}x_{n-2} \ldots x_1x_0$, $y = y_{n-1}y_{n-2} \ldots y_1y_0$. Podobnì jejich souèet znaèíme $z = z_nz_{n-1} \ldots z_1z_0$. Ka¾dý ji¾ urèitì zná jeden algoritmus jak tento souèet spoèítat, a to\r
  67 \r
  68 \h{Algoritmus základní ¹koly}\r
  69 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.6. \r
  70  \r
  71 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 je alespoò 1 èíslo jednièka, tedy\r
  72 $$c_i=(x_i \land y_i)\lor((x_i \lor y_i) \land c_{i-1})$$.\r
  73 \figure{1_6_hloupe_scitani.eps}{Obrázek 1.7 sèítání}{8cm}\r
  74 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.\r
  75 \r
  76 \h{Trik - chování blokù souètu}\r
  77 \r
  78 \figure{1_7_blok_scitani.eps}{Obrázek 1.8 - Blok souètu}{8cm}\r
  79 \>Blok se mù¾e chovat tøemi rùznými zpùsoby:\r
  80 \r
  81 \numlist{\ndotted}\r
  82 \:V¾dy vydá pøenos 0 \r
  83 \:V¾dy vydá pøenos 1\r
  84 \:Kopíruje (pøedá dál)\r
  85 \endlist\r
  86 \r
  87 \h{Rozdìlení a skládání blokù}\r
  88 Blok B lze rozdìlit na 2 bloky p,q (pokud B není trivální)\r
  89 \figure{1_10_konvence_deleni_bloku.eps}{Obrázek 1.9 - Dìlení blokù}{3cm}\r
  90 \r
  91 \r
  92 \h{Triviální bity}\r
  93 \figure{1_11_tabulka_kodovani.eps}{Obrázek 1.10 - Tabulka triviálních bitù}{3cm}\r
  94 \r
  95 \s{Tvrzení:} Ka¾dý blok mohu postavit z triviálních bitù. \r
  96 \r
  97 \proof \r
  98 Dùkaz indukcí z asociativity.\r
  99 \r
 100 \r
 101 \r
 102 \h{Kódování typù chování blokù}\r
 103 %\>{\I Sem tabulku prosím :)}\r
 104 \r
 105 \>Definujeme (a,x) : \r
 106 \itemize\ibull\r
 107 \:$(1,*) = <$\r
 108 \:$(0,0) = 0$\r
 109 \:$(0,1) = 1$\r
 110 \endlist\r
 111 \r
 112 \>a operaci skládání blokù $\sigma$ pro kterou platí\r
 113 \r
 114 $(a,x) \sigma (b,y) = (c,z)$\r
 115 \r
 116 \>kde\r
 117 \r
 118 $c = a \land b$\r
 119 \r
 120 $z = (\neg a \land x) \lor (a \land y)$\r
 121 \r
 122 \r
 123 \r
 124 \h{Lep¹í algoritmus sèítání}\r
 125 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).\r
 126 \r
 127 \figure{1_9_deleni_bloku.eps}{Obrázek 1.11 - Výpoèet pøenosu}{8cm}\r
 128 Víme pro ka¾dý blok velikosti $2^k$ na pozici dìlitelné $2^k$ jeho chování.\r
 129 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.\r
 130 \r
 131 \r
 132 \r
 133 \bye\r