Chapters/Introduction.tex

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