Add backmatter commands.
[matthijs/master-project/report.git] / 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 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.
8
9 % Use \subject to hide this section from the toc
10 \subject{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.
16
17   As a motivating example, consider the simple functional program shown in
18   \in{example}[ex:AndWord]\footnote[notfinalsyntax]{Note that this example is not in the final
19   Cλash syntax}. This is a very natural way to describe a lot of parallel not
20   ports, that perform a bitwise not on a bitvector. The example also shows an
21   image of the architecture described.
22
23   \startbuffer[AndWord]
24     notword :: [Bit] -> [Bit]
25     notword = map not
26   \stopbuffer
27
28   \startuseMPgraphic{AndWord}
29     % Create objects
30     save a, inp, out;
31     newCircle.inp(btex $\overrightarrow{input}$ etex) "framed(false)";
32     num := 4;
33     for i=1 upto num:
34       newCircle.a[i](btex not etex);
35     endfor 
36     newCircle.out(btex $\overrightarrow{output}$ etex) "framed(false)";
37
38     % Center the input and output ports vertically, and put them left and right
39     % resp.
40     inp.c = (xpart(a1.c) - 2cm, ypart((a[1].c + a[num].c)/2));
41     out.c = (xpart(a1.c) + 2cm, ypart((a[1].c + a[num].c)/2));
42     
43     % Space the operations vertically, with some extra space between the middle
44     % two
45     a2.c-a1.c=(0cm, 1.5cm);
46     a3.c-a2.c=(0cm, 2.5cm);
47     a4.c-a3.c=(0cm, 1.5cm);
48     a1.c=origin;
49
50     % Draw objects and lines
51     drawObj(inp);
52     for i=1 upto num:
53       ncline(inp)(a[i]);
54       drawObj(a[i]);
55       ncline(a[i])(out);
56     endfor
57     drawObj(out);
58     % Draw a dotted line between the middle operations
59     ncline(a2)(a3) "linestyle(dashed withdots)", "arrows(-)";
60   \stopuseMPgraphic
61   \placeexample[here][ex:AndWord]{Simple architecture that inverts a vector of bits.}
62     \startcombination[2*1]
63       {\typebufferlam{AndWord}}{Haskell description of the architecture.}
64       {\boxedgraphic{AndWord}}{The architecture described by the Haskell description.}
65     \stopcombination
66
67   Slightly more complicated is the incremental summation of
68   values show in \in{example}[ex:RecursiveSum]\note[notfinalsyntax].
69
70   In this example we see a recursive function \hs{sum'} that recurses over a
71   list and takes an accumulator argument that stores the sum so far. On each
72   step of the recusion, another number from the input vector is added to the
73   accumulator and each intermediate step returns its result.
74
75   This is a nice description of a series of sequential adders that produce
76   the incremental sums of a vector of numbers. For an input list of length 4,
77   the corresponding architecture is show in the example.
78
79   \startbuffer[RecursiveSum]
80     sum :: [Int] -> [Int]
81     sum = sum' 0
82
83     sum' :: Int -> [Int] -> [Int]
84     sum' acc [] = []
85     sum' acc (x:xs) = acc' : (sum' acc' xs)
86       where acc' = x + acc
87   \stopbuffer
88
89   \startuseMPgraphic{RecursiveSum}
90     save inp, a, zero, out;
91     % Create objects
92     newCircle.inp(btex $\overrightarrow{input}$ etex) "framed(false)";
93     newCircle.zero(btex $0$ etex) "framed(false)";
94     num := 4;
95     for i=1 upto num:
96       newCircle.a[i](btex + etex);
97     endfor 
98     newCircle.out(btex $\overrightarrow{output}$ etex) "framed(false)";
99
100     % Center the input and output ports vertically, and put them left and right
101     % resp.
102     
103     % Space the operations vertically, with some extra space between the middle
104     % two
105     a1.c-inp.c=(2cm, 0cm);
106     a2.c-a1.c=(1.5cm, 0cm);
107     a3.c-a2.c=(1.5cm, 0cm);
108     a4.c-a3.c=(1.5cm, 0cm);
109     out.c-a4.c=(2cm, 0cm);
110     a1.c = origin;
111     % Put the zero above the input
112     zero.c-inp.c=(0cm, 1cm);
113
114     nccurve(zero)(a1) "angleA(0)", "angleB(-40)";
115     % Draw objects and lines
116     drawObj(inp, zero);
117     %ncarc(inp)(a0);
118     for i=1 upto num:
119       if (i <> num):
120         nccurve(a[i])(out) "posA(e)", "angleB(" & decimal((num - i)*-20) & ")", "angleA(60)";
121       fi
122       nccurve(inp)(a[i]) "angleA(" & decimal(i*-15) & ")", "angleB(40)";
123       if (i <> 1):
124         ncline(a[i-1])(a[i]);
125       fi
126         
127       drawObj(a[i]);
128     endfor
129     ncline(a1)(a2);
130     ncline(a3)(a4);
131     ncline(a4)(out);
132     drawObj(out);
133   \stopuseMPgraphic
134
135   \placeexample[here][ex:RecursiveSum]{A recursive description that sums values.}
136     \startcombination[2*1]
137       {\typebufferlam{RecursiveSum}}{Haskell description of the architecture.}
138       {\boxedgraphic{RecursiveSum}}{The architecture described by the Haskell description.}
139     \stopcombination
140
141
142   Or... is this the description of a single accumulating adder, that will add
143   one element of each input each clock cycle and has a reset value of 0? In
144   that case, we would have described the architecture show in \in{example}[ex:RecursiveSumAlt]
145
146   \startuseMPgraphic{RecursiveSumAlt}
147     save reg, inp, a, out;
148     newReg.reg("") "dx(4mm)", "dy(6mm)", "reflect(true)";
149     newCircle.inp(btex $input$ etex) "framed(false)";
150     newCircle.a(btex + etex);
151     newCircle.out(btex $output$ etex) "framed(false)";
152    
153     % Put inp, a and out in one horizontal line, with reg above a
154     reg.c-a.c=(0cm, 2cm);
155     a.c-inp.c=(3cm, 0cm);
156     out.c-a.c=(3cm, 0cm);
157     a.c = origin;
158
159     % Draw objects and lines
160     drawObj(reg);
161     drawObj(inp);
162     drawObj(a);
163     drawObj(out);
164
165     ncline(inp)(a);
166     % a.e to reg.d
167     nccurve(a)(reg) "posA(e)", "angleA(0)", "angleB(180)", "posB(d)";
168     % reg.out to a
169     nccurve(reg)(a) "posA(out)", "angleA(180)", "angleB(-30)";
170     ncline(a)(out);
171   \stopuseMPgraphic
172
173   \placeexample[here][ex:RecursiveSumAlt]{An alternative interpretation of the description in \in{example}[ex:RecursiveSum]}
174     {\boxedgraphic{RecursiveSumAlt}}
175
176   The distinction in possible interpretations we see here, is an important
177   distinction in this research. In the first figure, the recursion in the code
178   is taken as recursion in space and each recursion step results in a
179   different piece of hardware, all of which are active simultaneously. In the
180   second figure, the recursion in the code is taken as recursion in time and
181   each recursion step is executed sequentially, \emph{on the same piece of
182   hardware}.
183
184   In this research we explore how to apply these two interpretations to
185   hardware descriptions. Additionally, we explore how other functional
186   programming concepts can be applied to hardware descriptions to give use an
187   efficient way to describe hardware.
188
189   This leads us to the following research question:
190
191   % Slightly bigger font, some extra spacing.
192   \setupquotation[style=tfb,spacebefore=5mm]
193   \startquotation
194     How can we describe the structural properties of a hardware design, using
195     a functional language?
196   \stopquotation
197   \setupquotation[style=normal,spacebefore=]
198
199   We can further split this into subquestions from a hardware perspective:
200   \startitemize
201     \item How can we describe a stateful design?
202     \item How can we describe (hierarchical) structure in a design?
203   \stopitemize
204   
205   And subquestions from a functional perspective:
206   \startitemize
207     \item How to interpret recursion in descriptions?
208     \item How to interpret polymorphism?
209     \item How to interpret higher order descriptions?
210   \stopitemize
211
212   In addition to looking at designing a hardware description language, we
213   will also implement a prototype to test drive our ideas. This prototype will
214   translate hardware descriptions written in the Haskell functional language
215   to simple (netlist-like) hardware descriptions in the \VHDL language. The
216   reasons for choosing these languages are detailed in section
217   \in{}[sec:prototype:input] and \in{}[sec:prototype:output] respectively.
218
219   \placeintermezzo{}{
220     \startframedtext[width=8cm,background=box,frame=no]
221     \startalignment[center]
222       {\tfa The name Cλash}
223     \stopalignment
224     \blank[medium]
225     The name Cλash more-or-less expands to CAES language for hardware
226     descriptions, where CAES refers to the research chair where this
227     project was undertaken (Computer Architectures for Embedded
228     Systems). The lambda in the name is of course a reference to the
229     lambda abstraction, which is an essential element of most functional
230     languages (and is also prominent in the Haskell logo).
231     \stopframedtext
232   }
233
234   The result of this research will thus be a prototype compiler and a language
235   that it can compile, to which we will refer to as the Cλash system and Cλash
236   language for short, or simply Cλash.
237
238 % Use \subject to hide this section from the toc
239 \subject{Outline}
240 In the first chapter, we will sketch the context for this research.
241 The current state and history of hardware description languages will be
242 briefly discussed, as well as the state and history of functional
243 programming. Since we're not the first to have merged these approaches,
244 a number of other functional hardware description languages are briefly
245 described.
246
247 Chapter two describes the exploratory part of this research: How can we
248 describe hardware using a functional language and how can we use functional
249 concepts for hardware descriptions?
250
251 Chapter three talks about the prototype that was created and which has guided
252 most of the research. There is some attention for the language chosen for our
253 hardware descriptions, Haskell. The possibilities and limits of this prototype
254 are further explored.
255
256 During the creation of the prototype, it became apparent that some structured
257 way of doing program transformations was required. Doing ad-hoc interpretation
258 of the hardware description proved non-scalable. These transformations and
259 their application are the subject of the fourth chapter.
260
261 The next chapter sketches ideas for further research, which are many. Some of
262 them have seen some initial exploration and could provide a basis for future
263 work in this area.
264
265 Finally, we present our conclusions.
266
267 % vim: set sw=2 sts=2 expandtab: