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.
9 This assignment has been performed in close cooperation with Christiaan
10 Baaij, whose Master's thesis \cite[baaij09]\ has been completed at the
11 same time as this thesis. Where this thesis focuses on the
12 interpretation of the Haskell language and the compilation process,
13 \cite[baaij09]\ has a more thorough study of the field, explores more
14 advanced types and provides a case study.
16 % Use \subject to hide this section from the toc
17 \subject{Research goals}
18 This research started out with the notion that a functional program is very
19 easy to interpret as a hardware description. A functional program typically
20 makes no assumptions about evaluation order and does not have any side
21 effects. This fits hardware nicely, since the evaluation order for hardware
22 is simply everything in parallel.
24 As a motivating example, consider the simple functional program shown in
25 \in{example}[ex:AndWord]\footnote[notfinalsyntax]{This example is not in the final
26 Cλash syntax}. This is a very natural way to describe a lot of parallel not
27 ports, that perform a bit-wise not on a bit-vector. The example also shows an
28 image of the architecture described.
31 notword :: [Bit] -> [Bit]
35 \startuseMPgraphic{AndWord}
38 newCircle.inp(btex $\overrightarrow{input}$ etex) "framed(false)";
41 newCircle.a[i](btex not etex);
43 newCircle.out(btex $\overrightarrow{output}$ etex) "framed(false)";
45 % Center the input and output ports vertically, and put them left and right
47 inp.c = (xpart(a1.c) - 2cm, ypart((a[1].c + a[num].c)/2));
48 out.c = (xpart(a1.c) + 2cm, ypart((a[1].c + a[num].c)/2));
50 % Space the operations vertically, with some extra space between the middle
52 a2.c-a1.c=(0cm, 1.5cm);
53 a3.c-a2.c=(0cm, 2.5cm);
54 a4.c-a3.c=(0cm, 1.5cm);
57 % Draw objects and lines
65 % Draw a dotted line between the middle operations
66 ncline(a2)(a3) "linestyle(dashed withdots)", "arrows(-)";
68 \placeexample[][ex:AndWord]{Simple architecture that inverts a vector of bits.}
69 \startcombination[2*1]
70 {\typebufferlam{AndWord}}{Haskell description of the architecture.}
71 {\boxedgraphic{AndWord}}{The architecture described by the Haskell description.}
74 Slightly more complicated is the incremental summation of
75 values shown in \in{example}[ex:RecursiveSum]\note[notfinalsyntax].
77 In this example we see a recursive function \hs{sum'} that recurses over a
78 list and takes an accumulator argument that stores the sum so far. On each
79 step of the recursion, another number from the input vector is added to the
80 accumulator and each intermediate step returns its result.
82 This is a nice description of a series of sequential adders that produce
83 the incremental sums of a vector of numbers. For an input list of length 4,
84 the corresponding architecture is show in the example.
86 \startbuffer[RecursiveSum]
90 sum' :: Int -> [Int] -> [Int]
92 sum' acc (x:xs) = acc' : (sum' acc' xs)
96 \startuseMPgraphic{RecursiveSum}
97 save inp, a, zero, out;
99 newCircle.inp(btex $\overrightarrow{input}$ etex) "framed(false)";
100 newCircle.zero(btex $0$ etex) "framed(false)";
103 newCircle.a[i](btex + etex);
105 newCircle.out(btex $\overrightarrow{output}$ etex) "framed(false)";
107 % Center the input and output ports vertically, and put them left and right
110 % Space the operations vertically, with some extra space between the middle
112 a1.c-inp.c=(2cm, 0cm);
113 a2.c-a1.c=(1.5cm, 0cm);
114 a3.c-a2.c=(1.5cm, 0cm);
115 a4.c-a3.c=(1.5cm, 0cm);
116 out.c-a4.c=(2cm, 0cm);
118 % Put the zero above the input
119 zero.c-inp.c=(0cm, 1cm);
121 nccurve(zero)(a1) "angleA(0)", "angleB(-40)";
122 % Draw objects and lines
127 nccurve(a[i])(out) "posA(e)", "angleB(" & decimal((num - i)*-20) & ")", "angleA(60)";
129 nccurve(inp)(a[i]) "angleA(" & decimal(i*-15) & ")", "angleB(40)";
131 ncline(a[i-1])(a[i]);
142 \placeexample[here][ex:RecursiveSum]{A recursive description that sums values.}
143 \startcombination[2*1]
144 {\typebufferlam{RecursiveSum}}{Haskell description of the architecture.}
145 {\boxedgraphic{RecursiveSum}}{The architecture described by the Haskell description.}
149 Or... is this the description of a single accumulating adder, that will add
150 one element of each input each clock cycle and has a reset value of
151 {\definedfont[Serif*normalnum]0}? In
152 that case, we would have described the architecture show in \in{example}[ex:RecursiveSumAlt]
154 \startuseMPgraphic{RecursiveSumAlt}
155 save reg, inp, a, out;
156 newReg.reg("") "dx(4mm)", "dy(6mm)", "reflect(true)";
157 newCircle.inp(btex $input$ etex) "framed(false)";
158 newCircle.a(btex + etex);
159 newCircle.out(btex $output$ etex) "framed(false)";
161 % Put inp, a and out in one horizontal line, with reg above a
162 reg.c-a.c=(0cm, 2cm);
163 a.c-inp.c=(3cm, 0cm);
164 out.c-a.c=(3cm, 0cm);
167 % Draw objects and lines
175 nccurve(a)(reg) "posA(e)", "angleA(0)", "angleB(180)", "posB(d)";
177 nccurve(reg)(a) "posA(out)", "angleA(180)", "angleB(-30)";
181 \placeexample[here][ex:RecursiveSumAlt]{An alternative interpretation of the description in \in{example}[ex:RecursiveSum]}
182 {\boxedgraphic{RecursiveSumAlt}}
184 The distinction in possible interpretations we see here, is an important
185 distinction in this research. In the first figure, the recursion in the code
186 is taken as recursion in space and each recursion step results in a
187 different piece of hardware, all of which are active simultaneously. In the
188 second figure, the recursion in the code is taken as recursion in time and
189 each recursion step is executed sequentially, \emph{on the same piece of
192 In this research we explore how to apply these two interpretations to
193 hardware descriptions. Additionally, we explore how other functional
194 programming concepts can be applied to hardware descriptions to give use an
195 efficient way to describe hardware.
197 This leads us to the following research question:
199 % Slightly bigger font, some extra spacing.
200 \setupquotation[style=tfb,spacebefore=5mm]
202 How can we describe the structural properties of a hardware design, using
203 a functional language?
205 \setupquotation[style=normal,spacebefore=]
207 We can further split this into sub-questions from a hardware perspective:
209 \item How can we describe a stateful design?
210 \item How can we describe (hierarchical) structure in a design?
213 And sub-questions from a functional perspective:
215 \item How to interpret recursion in descriptions?
216 \item How to interpret polymorphism?
217 \item How to interpret higher-order descriptions?
220 In addition to looking at designing a hardware description language, we
221 will also implement a prototype to test ideas. This prototype will
222 translate hardware descriptions written in the Haskell functional language
223 to simple (netlist-like) hardware descriptions in the \VHDL\ language. The
224 reasons for choosing these languages are detailed in section
225 \in{}[sec:prototype:input] and \in{}[sec:prototype:output] respectively.
228 \startframedtext[width=8cm,background=box,frame=no]
229 \startalignment[center]
230 {\tfa The name Cλash}
233 The name Cλash more-or-less expands to CAES language for hardware
234 descriptions, where CAES refers to the research chair where this
235 project was undertaken (Computer Architectures for Embedded
236 Systems). The lambda in the name is of course a reference to the
237 lambda abstraction, which is an essential element of most functional
238 languages (and is also prominent in the Haskell logo).
240 Cλash is pronounced like \quote{Clash}.
244 The result of this research will thus be a prototype compiler and a language
245 that it can compile, to which we will refer to as the Cλash system and Cλash
246 language for short, or simply Cλash.
248 % Use \subject to hide this section from the toc
250 In the first chapter, we will sketch the context for this research.
251 The current state and history of hardware description languages will be
252 briefly discussed, as well as the state and history of functional
253 programming. Since we are not the first to have merged these approaches,
254 a number of other functional hardware description languages are briefly
257 Chapter two describes the exploratory part of this research: how can we
258 describe hardware using a functional language and how can we use functional
259 concepts for hardware descriptions?
261 Chapter three talks about the prototype that was created and which has guided
262 most of the research. There is some attention for the language chosen for our
263 hardware descriptions, Haskell. The possibilities and limits of this prototype
264 are further explored.
266 During the creation of the prototype, it became apparent that some structured
267 way of doing program transformations was required. Doing ad hoc interpretation
268 of the hardware description proved non-scalable. These transformations and
269 their application are the subject of the fourth chapter.
271 The next chapter sketches ideas for further research, which are many. Some of
272 them have seen some initial exploration and could provide a basis for future
275 Finally, we present our conclusions.
277 % vim: set sw=2 sts=2 expandtab: