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.
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.
17 As a motivating example, consider the following simple functional
18 program:\footnote[notfinalsyntax]{Note that this example is not in the final
22 notword :: [Bit] -> [Bit]
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
30 \startuseMPgraphic{AndWord}
33 newCircle.inp(btex $\overrightarrow{input}$ etex) "framed(false)";
36 newCircle.a[i](btex not etex);
38 newCircle.out(btex $\overrightarrow{output}$ etex) "framed(false)";
40 % Center the input and output ports vertically, and put them left and right
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));
45 % Space the operations vertically, with some extra space between the middle
47 a2.c-a1.c=(0cm, 1.5cm);
48 a3.c-a2.c=(0cm, 2.5cm);
49 a4.c-a3.c=(0cm, 1.5cm);
52 % Draw objects and lines
60 % Draw a dotted line between the middle operations
61 ncline(a2)(a3) "linestyle(dashed withdots)", "arrows(-)";
63 \useMPgraphic{AndWord}
66 Slightly more complicated is the following incremental summation of
67 values:\note[notfinalsyntax]
73 sum' :: Int -> [Int] -> [Int]
75 sum' acc (x:xs) = acc' : (sum' acc' xs)
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.
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:
89 save inp, a, zero, out;
91 newCircle.inp(btex $\overrightarrow{input}$ etex) "framed(false)";
92 newCircle.zero(btex $0$ etex) "framed(false)";
95 newCircle.a[i](btex + etex);
97 newCircle.out(btex $\overrightarrow{output}$ etex) "framed(false)";
99 % Center the input and output ports vertically, and put them left and right
102 % Space the operations vertically, with some extra space between the middle
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);
110 % Put the zero above the input
111 zero.c-inp.c=(0cm, 1cm);
113 nccurve(zero)(a1) "angleA(0)", "angleB(-40)";
114 % Draw objects and lines
119 nccurve(a[i])(out) "posA(e)", "angleB(" & decimal((num - i)*-20) & ")", "angleA(60)";
121 nccurve(inp)(a[i]) "angleA(" & decimal(i*-15) & ")", "angleB(40)";
123 ncline(a[i-1])(a[i]);
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:
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)";
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);
151 % Draw objects and lines
159 nccurve(a)(reg) "posA(e)", "angleA(0)", "angleB(180)", "posB(d)";
161 nccurve(reg)(a) "posA(out)", "angleA(180)", "angleB(-30)";
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
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.
178 This leads us to the following research question:
179 \todo{Include Haskell in questions?}
181 % Slightly bigger font, some extra spacing.
182 \setupquotation[style=tfb,spacebefore=5mm]
184 How can we describe the structural properties of a hardware design, using
185 a functional language?
187 \setupquotation[style=normal,spacebefore=]
189 We can further split this into subquestions from a hardware perspective:
191 \item How can we describe a stateful design?
192 \item How can we describe (hierarchical) structure in a design?
195 And subquestions from a functional perspective:
197 \item How to interpret recursion in descriptions?
198 \item How to interpret polymorphism?
199 \item How to interpret higher order descriptions?
202 \todo{Introduce Cλash?}
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.
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
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?
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.
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.
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
239 % vim: set sw=2 sts=2 expandtab: