christiaan/reductioncircuit.lhs

   1 \subsection{Restrictions}
   2 %include talk.fmt
   3 \frame{
   4 \frametitle{Too Restrictive?}
   5 \begin{itemize}
   6   \item Is \clash{} too restrictive given the fact that a designer can currently not define his own vector transformations, or recursive functions for that matter?
   7 \end{itemize}
   8 }
   9 \note[itemize]{
  10 \item Je kan je natuurlijk afvragen of er nu niet teveel restricties zijn binnen \clash{}. Dit valt op zich wel mee, gezien veel gebruikte lijst-functies, zoals: map, zipwith, fold, enzo wel beschikbaar zijn
  11 \item next sheet: expressief genoeg voor reductiecircuit
  12 }
  13
  14 \frame{
  15 \frametitle{Too Restrictive?}
  16 \begin{itemize}
  17   \item There is certainly room to increase expressivity. But we can already describe non-trivial design in \clash{}.
  18   \item Example: Reduction circuit
  19 \end{itemize}
  20 }
  21 \note[itemize]{
  22 \item Recursieve functies zijn soms wel een gemis, en er is ook zeker ruimte om de expressiviteit van \clash{} uit te breiden. Maar we kunnen al wel niet-triviale ontwerpen maken, zoals het reductiecircuit wat ik nu ga laten zien.
  23 \item Next sheet: beschrijving reductie circuit
  24 }
  25
  26 \subsection{Reduction circuit}
  27
  28 \frame{
  29 \frametitle{Reduction Circuit}
  30 \begin{columns}[l]
  31 \column{0.5\textwidth}
  32 \begin{figure}
  33 \includegraphics[height=6.5cm]{reducer}
  34 \end{figure}
  35 \column{0.5\textwidth}
  36 \begin{itemize}
  37   \item Reduction circuit sums the floating-point values of each row in a matrix.
  38   \item Non-trivial due to pipe-lined floating-point adder.
  39   \item Largest restrictions are the fixed-size vectors.
  40 \end{itemize}
  41 \end{columns}
  42 }
  43 \note[itemize]{
  44 \item Reductiecircuit telt voor alle rijen, de getallen uit zo'n rij bij elkaar op.
  45 \item Het probleem is niet triviaal, omdat resultaten met een bepaalde vertraging uit de opteller komen vanwege pipelining. Triviale oplossing zoals een simpel accumulate register zijn niet mogelijk omdat dan per ongelijk meerdere rijen bij elkaar opgeteld worden. Ook kan je niet wachten op het resultaat, omdat je mogelijk een oneindig grote input buffer nodig hebt.
  46 \item Daarom heb je speciale controle logica nodig die bijhoud welke waarden er in de opteller zitten.
  47 \item De grootste beperking in het ontwerp is niet het gebrek aan recursieve functies, maar het gebrek aan dynamishe lijsten.
  48 \item next sheet: synthese output reductie circuit
  49 }
  50
  51 \begin{frame}
  52    \begin{figure}
  53       \includegraphics[height=9cm]{reducerschematic}
  54     \end{figure}
  55 \end{frame}
  56 \note[itemize]{
  57 \item Zie hier het werkelijke circuit
  58 \item Next sheet: fifo buffer wens
  59 }
  60
  61 \begin{frame}
  62 \frametitle{FIFO Buffer}
  63 \begin{itemize}
  64   \item Wish:
  65 \begin{code}
  66 fifo :: (State mem) (input, shift) =
  67   (State mem', out1, out2)
  68   where
  69     out1 | length mem == 0 = NotValid
  70          | otherwise       = head mem
  71     out2 | length mem < 2  = NotValid
  72          | otherwise       = head (tail mem)
  73     {-"{\color<2>[rgb]{1,0,0}"-}mem' = drop shift mem ++ [input]{-"}"-}
  74 \end{code}
  75 \end{itemize}
  76 \end{frame}
  77 \note[itemize]{
  78 \item Hier het gewenste ontwerp van de input (FIFO) buffer.
  79 \item Zie vooral de laatste regel. De lengte van mem' is afhankelijk van de waarde van shift. Dus dynamish.
  80 \item Next sheet: fifo buffer realiteit
  81 }
  82
  83 \begin{frame}
  84 \frametitle{FIFO Buffer}
  85 \begin{itemize}
  86   \item Reality:
  87 \begin{code}
  88 fifo :: (State (Fifo {..})) (inp, shift) =
  89   ( State (Fifo { mem = mem'
  90                 , ptr = ptr'
  91                 })
  92   , out1, out2
  93   )
  94   where
  95     {-"{\color<2>[rgb]{1,0,0}"-}ptr'  = ptr - shift + 1{-"}"-}
  96     {-"{\color<2>[rgb]{1,0,0}"-}mem'' = replace mem ptr (Valid inp){-"}"-}
  97     {-"{\color<2>[rgb]{1,0,0}"-}mem'  | shift == 0 = mem''{-"}"-}
  98     {-"{\color<2>[rgb]{1,0,0}"-}      | shift == 1 = (tail mem'') <+ NotValid{-"}"-}
  99     {-"{\color<2>[rgb]{1,0,0}"-}      | otherwise  = ((tail (tail mem''){-"}"-}
 100     {-"{\color<2>[rgb]{1,0,0}"-}                      <+ NotValid) <+ NotValid){-"}"-}
 101     out1  = head mem
 102     out2  = head (tail mem)
 103 \end{code}
 104 \end{itemize}
 105 \end{frame}
 106 \note[itemize]{
 107 \item Die dynamishe lijsten hebben we dus niet in \clash{}
 108 \item Daarom moeten we heel veel logica toevoegen om iets te maken wat het gedrag van een dynamishe lijst emuleert.
 109 \item Next sheet: dynamish vs statisch
 110 }
 111
 112 \frame{
 113 \frametitle{FIFO Buffer}
 114 \begin{itemize}
 115   \item Wish: Dynamically sized vectors
 116   \item Reality: Statically sized vectors
 117 \end{itemize}
 118 }
 119 \note[itemize]{
 120 \item Dus, de wens is dynamishe lijsten, en de realiteit is statische lijsten. Dit omdat statische lijsten veel makelijker naar hardware zijn te mappen. Ze zijn gewoon 1-op-1 te kopieren.
 121 \item Dynamische lijsten moeilijk, ik kan niet op run-time extra hardware maken. Wat bij software wel gebeurd: gewoon meer RAM alloceren
 122 \item Next sheet: problemen/mogelijkheden dynamische lijsten
 123 }
 124
 125 \frame{
 126 \frametitle{Dynamically Sized Vectors}
 127 \begin{itemize}
 128   \item Map all vectors to RAMs:
 129   \begin{itemize}
 130     \item Store length separately, extra logic
 131     \item What happens if size of the vector exceeds size of the size of the RAM?
 132   \end{itemize}
 133   \item Translate to (shift/circular) Buffers
 134   \begin{itemize}
 135   \item Requires analysis of data-access
 136   \item How do we determine maximum size?
 137   \end{itemize}
 138 \end{itemize}
 139 }
 140 \note[itemize]{
 141 \item Wat zijn dan mogelijkheden voor dynamische lijsten?
 142 \item Alle lijsten naar RAMs mappen... maar dan is er wel extra logica nodig om de lengte bij te houden. Wat gebeurd er als de RAM eenheid vol is?
 143 \item We kunnen ook proberen om de operaties te vertalen naar shift/circulaire buffers... Maar dan moeten we dus wel data-access analyse doen... en we moeten de maximale lengte kunnen bepalen...
 144 \item Allemaal niet triviaal dus
 145 \item Next sheet: belangrijkste future work, recursie
 146 }