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