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.
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.
16 As a motivating example, consider the following simple functional program:
19 andword :: [Bit] -> [Bit]
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
30 newCircle.inp(btex $\overrightarrow{input}$ etex) "framed(false)";
33 newCircle.a[i](btex not etex);
35 newCircle.out(btex $\overrightarrow{output}$ etex) "framed(false)";
37 % Center the input and output ports vertically, and put them left and right
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));
42 % Space the operations vertically, with some extra space between the middle
44 a2.c-a1.c=(0cm, 1.5cm);
45 a3.c-a2.c=(0cm, 2.5cm);
46 a4.c-a3.c=(0cm, 1.5cm);
49 % Draw objects and lines
57 % Draw a dotted line between the middle operations
58 ncline(a2)(a3) "linestyle(dashed withdots)", "arrows(-)";
61 Slightly more complicated is the following incremental summation of values:
67 sum' :: [Int] -> Int -> [Int]
69 sum' (x:xs) acc = acc' : (sum' xs acc')
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.
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:
83 save inp, a, zero, out;
85 newCircle.inp(btex $\overrightarrow{input}$ etex) "framed(false)";
86 newCircle.zero(btex $0$ etex) "framed(false)";
89 newCircle.a[i](btex + etex);
91 newCircle.out(btex $\overrightarrow{output}$ etex) "framed(false)";
93 % Center the input and output ports vertically, and put them left and right
96 % Space the operations vertically, with some extra space between the middle
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);
104 % Put the zero above the input
105 zero.c-inp.c=(0cm, 1cm);
107 nccurve(zero)(a1) "angleA(0)", "angleB(-40)";
108 % Draw objects and lines
113 nccurve(a[i])(out) "posA(e)", "angleB(" & decimal((num - i)*-20) & ")", "angleA(60)";
115 nccurve(inp)(a[i]) "angleA(" & decimal(i*-15) & ")", "angleB(40)";
117 ncline(a[i-1])(a[i]);
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:
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)";
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);
145 % Draw objects and lines
153 nccurve(a)(reg) "posA(e)", "angleA(0)", "angleB(180)", "posB(d)";
155 nccurve(reg)(a) "posA(out)", "angleA(180)", "angleB(-30)";
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
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.
172 This leads us to the following research question:
174 % Slightly bigger font, some extra spacing.
175 \setupquotation[style=tfb,spacebefore=5mm]
177 How can we describe the structural properties of a hardware design, using
178 a functional language?
180 \setupquotation[style=normal,spacebefore=]
182 We can further split this into subquestions from a hardware perspective:
184 \item How can we describe a stateful design?
185 \item How can we describe (hierarchical) structure in a design?
188 And subquestions from a functional perspective:
190 \item How to interpret recursion in descriptions?
191 \item How to interpret polymorphism?
192 \item How to interpret higher order in descriptions?
195 In addition to looking at designing a hardware description language, we
196 will also implement a prototype to test drive our ideas. This prototype will
197 translate hardware descriptions written in the Haskell functional language
198 to simple (netlist-like) hardware descriptions in the \VHDL language. The
199 reasons for choosing these languages are detailed in section
200 \in{}[sec:prototype:input] and \in{}[sec:prototype:output] respectively.
204 In the first chapter, we will sketch the context for this research.
205 The current state and history of hardware description languages will be
206 briefly discussed, as well as the state and history of functional
207 programming. Since we're not the first to have merged these approaches,
208 a number of other functional hardware description languages are briefly
211 Chapter two describes the exploratory part of this research: How can we
212 describe hardware using a functional language and how can we use functional
213 concepts for hardware descriptions?
215 Chapter three talks about the prototype that was created and which has guided
216 most of the research. There is some attention for the language chosen for our
217 hardware descriptions, Haskell. The possibilities and limits of this prototype
218 are further explored.
220 During the creation of the prototype, it became apparent that some structured
221 way of doing program transformations was required. Doing ad-hoc interpretation
222 of the hardware description proved non-scalable. These transformations and
223 their application are the subject of the fourth chapter.
225 The final chapter sketches ideas for further research, which are many. Some of
226 have seen some initial exploration and could provide a basis for future work