talk.lhs

   1 \RequirePackage{atbegshi}
   2 \documentclass[empty]{beamer}
   3 \usetheme{default}
   4 %\setbeameroption{show only notes}
   5 %\setbeameroption{show notes}
   6 \setbeamertemplate{navigation symbols}{}
   7 \setbeamertemplate{footline}
   8 {
   9   \hbox{%
  10   \centerline{\insertframenumber{}}}%
  11   \vskip5pt%
  12 }
  13
  14 \addtobeamertemplate{note page}{
  15   \vskip5pt
  16   \centerline{\insertframenumber}
  17   \vskip5pt
  18 }{}
  19
  20 %include talk.fmt
  21 \include{preamble}
  22
  23 \title{Haskell-ish Hardware Descriptions}
  24 \author{Matthijs Kooijman, Christiaan Baaij, Jan Kuper}
  25 \date{Dutch Haskell user group day, 2010}
  26
  27 \begin{document}
  28
  29 \section{Introduction}
  30
  31 \frame{\titlepage}
  32
  33 \note[itemize]
  34 {
  35   \item Master's thesis - hardware description language \& compiler Cλash
  36   \item Short introduction, then examples
  37   \item VHDL is common, but sucks
  38   \item Cλash compiler is not embedded, but external
  39 }
  40
  41 \frame
  42 {
  43   \frametitle{Compiler}
  44   \begin{center}
  45     \includegraphics[width=10cm]{figures/pipeline}
  46   \end{center}
  47 }
  48
  49 \note[itemize]
  50 {
  51   \item Working prototype, rough edges
  52   \item Reuse GHC
  53   \item Custom normalization - Reduction system of transformations
  54   \item Simple subset of VHDL - existing tooling
  55 }
  56
  57 \section{Examples}
  58
  59 \frame
  60 {
  61     \frametitle{Multiply-accumulate}
  62     \only<1> {
  63       \begin{code}
  64 mac :: Num a => a -> a -> a -> a
  65       \end{code}
  66     }
  67     \only<2-> {
  68       \begin{code}
  69 type Word = SizedWord D16
  70 mac :: Word -> Word -> Word -> Word
  71       \end{code}
  72     }
  73     \begin{code}
  74 mac x y acc = acc + x * y
  75     \end{code}
  76     \smallskip
  77     \includegraphics[width=6cm]{figures/mac}
  78 }
  79
  80 \note[itemize]
  81 {
  82   \item functions are components (operators are functions too!)
  83   \item function application is component instantiation
  84   \item Polymorphic description
  85   \item But top level must be monomorphic (next frame)
  86 }
  87
  88 \frame
  89 {
  90     \frametitle{Stateful multiply-accumulate}
  91     \begin{code}
  92 newtype State a = State a
  93
  94 smac :: State Word -> Word -> Word -> (State Word, Word)
  95 smac (State s) x y = (State s', s')
  96   where s' = s + x * y
  97     \end{code}
  98     \smallskip
  99       \includegraphics[width=6cm]{figures/smac}
 100 }
 101
 102 \note[itemize]
 103 {
 104   \item State is explicit: Argument and result
 105   \item Produces register == memory
 106 }
 107
 108 \frame
 109 {
 110     \frametitle{Simple CPU}
 111     \includegraphics[width=11cm]{figures/cpu}
 112 }
 113
 114 \note[itemize]
 115 {
 116     \item Simple CPU: Instructions are one opcode and four address pairs
 117     \item One input line, one output line, no memories
 118     \item Small, but basis for real hardware
 119     \item Three fixed function units, one multipurpose function unit
 120 }
 121
 122 \frame
 123 {
 124   \frametitle{Fixed function function units}
 125   \begin{code}
 126   fu :: (... u ~ n :-: D1 ...) => (a -> a -> t)
 127                  -> Vector n a
 128                  -> (Index u, Index u)
 129                  -> t
 130
 131   fu op inputs (a1, a2) = op (inputs!a1) (inputs!a2)
 132   \end{code}
 133   \vspace{2cm}
 134
 135   \begin{code}
 136   fu1 = fu (+)
 137   fu2 = fu (-)
 138   fu3 = fu (*)
 139   \end{code}
 140 }
 141
 142 \note[itemize]
 143 {
 144   \item fu abstracts the input selection
 145   \item fu takes an arbitrary binary operation
 146   \item Some context left out
 147   \item Vector is a fixed size vector, Index an index
 148 }
 149
 150 \frame
 151 {
 152   \frametitle{Multi-purpose function unit}
 153   \begin{code}
 154   data Opcode = Shift | Xor | Equal
 155
 156   multiop :: Opcode -> Word -> Word -> Word
 157   multiop Shift   = shift
 158   multiop Xor     = xor
 159   multiop Equal   = \a b -> if a == b then 1 else 0
 160   \end{code}
 161   \vspace{2cm}
 162
 163   \begin{code}
 164   fu0 c = fu (multiop c)
 165   \end{code}
 166 }
 167
 168 \note[itemize]
 169 {
 170   \item multiop takes an opcode and produces a binary operation
 171   \item multiop is partially applied to the opcode
 172 }
 173
 174 \frame
 175 {
 176   \frametitle{The complete CPU}
 177   \begin{code}
 178 type CpuState = State (Vector D4 Word)
 179
 180 cpu :: CpuState
 181   -> (Word, Opcode, Vector D4 (Index D6, Index D6))
 182   -> (CpuState, Word)
 183 cpu  (State s) (x, opc, addrs) = (State s', out)
 184   where
 185     inputs = x +> (0 +> (1 +> s))
 186     s' = (fu0 opc inputs (addrs!(0 :: Index D3))) +> (
 187          (fu1     inputs (addrs!(1 :: Index D3))) +> (
 188          (fu2     inputs (addrs!(2 :: Index D3))) +> (
 189          (fu3     inputs (addrs!(3 :: Index D3))) +> (
 190          (empty)))))
 191     out = last s
 192   \end{code}
 193 }
 194
 195 \note[itemize] {
 196   \item Uses partial application for fu0
 197   \item Cpu state is one register per fu
 198 }
 199
 200 \frame
 201 {
 202     \frametitle{Floating point reduction circuit}
 203     \includegraphics[width=11cm]{figures/reducer}
 204 }
 205 \note[itemize]
 206 {
 207   \item Sums rows of corresponding FP numbers (e.g., sparse matrix
 208   multiplication)
 209   \item Complexity: Pipelined adder, multiple rows simultaneously
 210   \item Big design, implemented in Cλash
 211 }
 212
 213 \frame
 214 {
 215   \frametitle{Controller function}
 216   \begin{code}
 217 controller (inp1, inp2, pT, from_res_mem) =
 218     (arg1, arg2, shift, to_res_mem)
 219   where
 220     (arg1, arg2, shift, to_res_mem)
 221       | valid pT && valid from_res_mem
 222         = (pT , from_res_mem , 0, False)
 223       | valid pT && valid inp1 && discr pT == discr inp1
 224         = (pT , inp1 , 1, False)
 225       | valid inp1 && valid inp2 && discr inp1 == discr inp2
 226         = (inp1 , inp2 , 2, valid pT)
 227       | valid inp1
 228         = (inp1 , (True, (0, discr inp1)) , 1, valid pT)
 229       | otherwise
 230         = (notValid, notValid , 0, valid pT)
 231   \end{code}
 232 }
 233
 234 \note[itemize]
 235 {
 236   \item Elegant implementation of algorithm rules
 237 }
 238
 239
 240 \section{Future}
 241
 242 \frame
 243 {
 244   \frametitle{Future work}
 245   \begin{itemize}
 246     \item More systematic normalization
 247     \item Recursion / normal lists
 248     \item Nested state abstraction
 249     \item Multiple clock domains / asynchronicity
 250     \item Graphical output
 251   \end{itemize}
 252 }
 253
 254 \note[itemize]
 255 {
 256   \item More systematic normalization - proofs
 257   \item Recursion / normal lists - Fixed size recursion has problems
 258   \item Nested state abstraction - Larger designs can get messy
 259   \item Multiple clock domains / asynchronicity - Clock is currently implicit
 260   \item Graphical output - For analysis and testing
 261   \item Plenty of assignments!
 262 }
 263
 264
 265 \subsection{Thanks}
 266 \frame
 267 {
 268 \vspace{2cm}\centerline{\Huge{Thanks!}}
 269 \vspace{2cm}
 270 http://wwwhome.cs.utwente.nl/~baaijcpr/ClaSH/Index.html
 271 \begin{center}or just\end{center}
 272 http://google.com/search?q={\bf{}C$\lambda$aSH}\&btnI=I'm Feeling Lucky
 273 }
 274
 275 \end{document}
 276 % vim: set filetype=tex sw=2 sts=2 expandtab: