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