Chapters/Introduction.tex

   1 \chapter[chap:introduction]{Introduction}
   2 This thesis describes the result and process of my work during my
   3 Master's assignment. In these pages, I will introduce the world
   4 of hardware descriptions, the world of functional languages and
   5 compilers and introduce the hardware description language Cλash that will
   6 connect these worlds and puts a step towards making hardware programming
   7 on the whole easier, more maintainable and generally more pleasant.
   8
   9 This assignment has been performed in close cooperation with Christiaan
  10 Baaij, whose Master's thesis \cite[baaij09] has been completed at the
  11 same time as this thesis. Where this thesis focuses on the
  12 interpretation of the Haskell language and the compilation process,
  13 \cite[baaij09] has a more thorough study of the field, explores more
  14 advanced types and provides a case study.
  15
  16 % Use \subject to hide this section from the toc
  17 \subject{Research goals}
  18   This research started out with the notion that a functional program is very
  19   easy to interpret as a hardware description. A functional program typically
  20   makes no assumptions about evaluation order and does not have any side
  21   effects. This fits hardware nicely, since the evaluation order for hardware
  22   is simply everything in parallel.
  23
  24   As a motivating example, consider the simple functional program shown in
  25   \in{example}[ex:AndWord]\footnote[notfinalsyntax]{This example is not in the final
  26   Cλash syntax}. This is a very natural way to describe a lot of parallel not
  27   ports, that perform a bitwise not on a bitvector. The example also shows an
  28   image of the architecture described.
  29
  30   \startbuffer[AndWord]
  31     notword :: [Bit] -> [Bit]
  32     notword = map not
  33   \stopbuffer
  34
  35   \startuseMPgraphic{AndWord}
  36     % Create objects
  37     save a, inp, out;
  38     newCircle.inp(btex $\overrightarrow{input}$ etex) "framed(false)";
  39     num := 4;
  40     for i=1 upto num:
  41       newCircle.a[i](btex not etex);
  42     endfor
  43     newCircle.out(btex $\overrightarrow{output}$ etex) "framed(false)";
  44
  45     % Center the input and output ports vertically, and put them left and right
  46     % resp.
  47     inp.c = (xpart(a1.c) - 2cm, ypart((a[1].c + a[num].c)/2));
  48     out.c = (xpart(a1.c) + 2cm, ypart((a[1].c + a[num].c)/2));
  49
  50     % Space the operations vertically, with some extra space between the middle
  51     % two
  52     a2.c-a1.c=(0cm, 1.5cm);
  53     a3.c-a2.c=(0cm, 2.5cm);
  54     a4.c-a3.c=(0cm, 1.5cm);
  55     a1.c=origin;
  56
  57     % Draw objects and lines
  58     drawObj(inp);
  59     for i=1 upto num:
  60       ncline(inp)(a[i]);
  61       drawObj(a[i]);
  62       ncline(a[i])(out);
  63     endfor
  64     drawObj(out);
  65     % Draw a dotted line between the middle operations
  66     ncline(a2)(a3) "linestyle(dashed withdots)", "arrows(-)";
  67   \stopuseMPgraphic
  68   \placeexample[][ex:AndWord]{Simple architecture that inverts a vector of bits.}
  69     \startcombination[2*1]
  70       {\typebufferlam{AndWord}}{Haskell description of the architecture.}
  71       {\boxedgraphic{AndWord}}{The architecture described by the Haskell description.}
  72     \stopcombination
  73
  74   Slightly more complicated is the incremental summation of
  75   values show in \in{example}[ex:RecursiveSum]\note[notfinalsyntax].
  76
  77   In this example we see a recursive function \hs{sum'} that recurses over a
  78   list and takes an accumulator argument that stores the sum so far. On each
  79   step of the recusion, another number from the input vector is added to the
  80   accumulator and each intermediate step returns its result.
  81
  82   This is a nice description of a series of sequential adders that produce
  83   the incremental sums of a vector of numbers. For an input list of length 4,
  84   the corresponding architecture is show in the example.
  85
  86   \startbuffer[RecursiveSum]
  87     sum :: [Int] -> [Int]
  88     sum = sum' 0
  89
  90     sum' :: Int -> [Int] -> [Int]
  91     sum' acc [] = []
  92     sum' acc (x:xs) = acc' : (sum' acc' xs)
  93       where acc' = x + acc
  94   \stopbuffer
  95
  96   \startuseMPgraphic{RecursiveSum}
  97     save inp, a, zero, out;
  98     % Create objects
  99     newCircle.inp(btex $\overrightarrow{input}$ etex) "framed(false)";
 100     newCircle.zero(btex $0$ etex) "framed(false)";
 101     num := 4;
 102     for i=1 upto num:
 103       newCircle.a[i](btex + etex);
 104     endfor
 105     newCircle.out(btex $\overrightarrow{output}$ etex) "framed(false)";
 106
 107     % Center the input and output ports vertically, and put them left and right
 108     % resp.
 109
 110     % Space the operations vertically, with some extra space between the middle
 111     % two
 112     a1.c-inp.c=(2cm, 0cm);
 113     a2.c-a1.c=(1.5cm, 0cm);
 114     a3.c-a2.c=(1.5cm, 0cm);
 115     a4.c-a3.c=(1.5cm, 0cm);
 116     out.c-a4.c=(2cm, 0cm);
 117     a1.c = origin;
 118     % Put the zero above the input
 119     zero.c-inp.c=(0cm, 1cm);
 120
 121     nccurve(zero)(a1) "angleA(0)", "angleB(-40)";
 122     % Draw objects and lines
 123     drawObj(inp, zero);
 124     %ncarc(inp)(a0);
 125     for i=1 upto num:
 126       if (i <> num):
 127         nccurve(a[i])(out) "posA(e)", "angleB(" & decimal((num - i)*-20) & ")", "angleA(60)";
 128       fi
 129       nccurve(inp)(a[i]) "angleA(" & decimal(i*-15) & ")", "angleB(40)";
 130       if (i <> 1):
 131         ncline(a[i-1])(a[i]);
 132       fi
 133
 134       drawObj(a[i]);
 135     endfor
 136     ncline(a1)(a2);
 137     ncline(a3)(a4);
 138     ncline(a4)(out);
 139     drawObj(out);
 140   \stopuseMPgraphic
 141
 142   \placeexample[here][ex:RecursiveSum]{A recursive description that sums values.}
 143     \startcombination[2*1]
 144       {\typebufferlam{RecursiveSum}}{Haskell description of the architecture.}
 145       {\boxedgraphic{RecursiveSum}}{The architecture described by the Haskell description.}
 146     \stopcombination
 147
 148
 149   Or... is this the description of a single accumulating adder, that will add
 150   one element of each input each clock cycle and has a reset value of
 151   {\definedfont[Serif*normalnum]0}? In
 152   that case, we would have described the architecture show in \in{example}[ex:RecursiveSumAlt]
 153
 154   \startuseMPgraphic{RecursiveSumAlt}
 155     save reg, inp, a, out;
 156     newReg.reg("") "dx(4mm)", "dy(6mm)", "reflect(true)";
 157     newCircle.inp(btex $input$ etex) "framed(false)";
 158     newCircle.a(btex + etex);
 159     newCircle.out(btex $output$ etex) "framed(false)";
 160
 161     % Put inp, a and out in one horizontal line, with reg above a
 162     reg.c-a.c=(0cm, 2cm);
 163     a.c-inp.c=(3cm, 0cm);
 164     out.c-a.c=(3cm, 0cm);
 165     a.c = origin;
 166
 167     % Draw objects and lines
 168     drawObj(reg);
 169     drawObj(inp);
 170     drawObj(a);
 171     drawObj(out);
 172
 173     ncline(inp)(a);
 174     % a.e to reg.d
 175     nccurve(a)(reg) "posA(e)", "angleA(0)", "angleB(180)", "posB(d)";
 176     % reg.out to a
 177     nccurve(reg)(a) "posA(out)", "angleA(180)", "angleB(-30)";
 178     ncline(a)(out);
 179   \stopuseMPgraphic
 180
 181   \placeexample[here][ex:RecursiveSumAlt]{An alternative interpretation of the description in \in{example}[ex:RecursiveSum]}
 182     {\boxedgraphic{RecursiveSumAlt}}
 183
 184   The distinction in possible interpretations we see here, is an important
 185   distinction in this research. In the first figure, the recursion in the code
 186   is taken as recursion in space and each recursion step results in a
 187   different piece of hardware, all of which are active simultaneously. In the
 188   second figure, the recursion in the code is taken as recursion in time and
 189   each recursion step is executed sequentially, \emph{on the same piece of
 190   hardware}.
 191
 192   In this research we explore how to apply these two interpretations to
 193   hardware descriptions. Additionally, we explore how other functional
 194   programming concepts can be applied to hardware descriptions to give use an
 195   efficient way to describe hardware.
 196
 197   This leads us to the following research question:
 198
 199   % Slightly bigger font, some extra spacing.
 200   \setupquotation[style=tfb,spacebefore=5mm]
 201   \startquotation
 202     How can we describe the structural properties of a hardware design, using
 203     a functional language?
 204   \stopquotation
 205   \setupquotation[style=normal,spacebefore=]
 206
 207   We can further split this into subquestions from a hardware perspective:
 208   \startitemize
 209     \item How can we describe a stateful design?
 210     \item How can we describe (hierarchical) structure in a design?
 211   \stopitemize
 212
 213   And subquestions from a functional perspective:
 214   \startitemize
 215     \item How to interpret recursion in descriptions?
 216     \item How to interpret polymorphism?
 217     \item How to interpret higher-order descriptions?
 218   \stopitemize
 219
 220   In addition to looking at designing a hardware description language, we
 221   will also implement a prototype to test ideas. This prototype will
 222   translate hardware descriptions written in the Haskell functional language
 223   to simple (netlist-like) hardware descriptions in the \VHDL\ language. The
 224   reasons for choosing these languages are detailed in section
 225   \in{}[sec:prototype:input] and \in{}[sec:prototype:output] respectively.
 226
 227   \placeintermezzo{}{
 228     \startframedtext[width=8cm,background=box,frame=no]
 229     \startalignment[center]
 230       {\tfa The name Cλash}
 231     \stopalignment
 232     \blank[medium]
 233     The name Cλash more-or-less expands to CAES language for hardware
 234     descriptions, where CAES refers to the research chair where this
 235     project was undertaken (Computer Architectures for Embedded
 236     Systems). The lambda in the name is of course a reference to the
 237     lambda abstraction, which is an essential element of most functional
 238     languages (and is also prominent in the Haskell logo).
 239     \stopframedtext
 240   }
 241
 242   The result of this research will thus be a prototype compiler and a language
 243   that it can compile, to which we will refer to as the Cλash system and Cλash
 244   language for short, or simply Cλash.
 245
 246 % Use \subject to hide this section from the toc
 247 \subject{Outline}
 248 In the first chapter, we will sketch the context for this research.
 249 The current state and history of hardware description languages will be
 250 briefly discussed, as well as the state and history of functional
 251 programming. Since we are not the first to have merged these approaches,
 252 a number of other functional hardware description languages are briefly
 253 described.
 254
 255 Chapter two describes the exploratory part of this research: How can we
 256 describe hardware using a functional language and how can we use functional
 257 concepts for hardware descriptions?
 258
 259 Chapter three talks about the prototype that was created and which has guided
 260 most of the research. There is some attention for the language chosen for our
 261 hardware descriptions, Haskell. The possibilities and limits of this prototype
 262 are further explored.
 263
 264 During the creation of the prototype, it became apparent that some structured
 265 way of doing program transformations was required. Doing ad-hoc interpretation
 266 of the hardware description proved non-scalable. These transformations and
 267 their application are the subject of the fourth chapter.
 268
 269 The next chapter sketches ideas for further research, which are many. Some of
 270 them have seen some initial exploration and could provide a basis for future
 271 work in this area.
 272
 273 Finally, we present our conclusions.
 274
 275 % vim: set sw=2 sts=2 expandtab: