Chapters/Introduction.tex

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