X-Git-Url: https://git.stderr.nl/gitweb?p=matthijs%2Fmaster-project%2Freport.git;a=blobdiff_plain;f=Chapters%2FHardwareDescription.tex;h=0ec41f7403eab8c595bca563a743ff74b78a8147;hp=0266490bf21c51bac670b20317846507883cccd0;hb=46e3a9e0c8d1bc5601080c1f8d176a51f9c1db2a;hpb=ca520674308c1949f94efa4b45e3b90076fcf05b diff --git a/Chapters/HardwareDescription.tex b/Chapters/HardwareDescription.tex index 0266490..0ec41f7 100644 --- a/Chapters/HardwareDescription.tex +++ b/Chapters/HardwareDescription.tex @@ -27,17 +27,52 @@ to the corresponding input port. The output port of the function is also mapped to a signal, which is used as the result of the application. - An example of a simple program using only function application would be: - - \starthaskell - -- | A simple function that returns the and of three bits - and3 :: Bit -> Bit -> Bit -> Bit - and3 a b c = and (and a b) c - \stophaskell - - This results in the following hardware: - - TODO: Pretty picture + \in{Example}[ex:And3] shows a simple program using only function + application and the corresponding architecture. + +\startbuffer[And3] +-- | A simple function that returns +-- the and of three bits +and3 :: Bit -> Bit -> Bit -> Bit +and3 a b c = and (and a b) c +\stopbuffer + + \startuseMPgraphic{And3} + save a, b, c, anda, andb, out; + + % I/O ports + newCircle.a(btex $a$ etex) "framed(false)"; + newCircle.b(btex $b$ etex) "framed(false)"; + newCircle.c(btex $c$ etex) "framed(false)"; + newCircle.out(btex $out$ etex) "framed(false)"; + + % Components + newCircle.anda(btex $and$ etex); + newCircle.andb(btex $and$ etex); + + a.c = origin; + b.c = a.c + (0cm, 1cm); + c.c = b.c + (0cm, 1cm); + anda.c = midpoint(a.c, b.c) + (2cm, 0cm); + andb.c = midpoint(b.c, c.c) + (4cm, 0cm); + + out.c = andb.c + (2cm, 0cm); + + % Draw objects and lines + drawObj(a, b, c, anda, andb, out); + + ncarc(a)(anda) "arcangle(-10)"; + ncarc(b)(anda); + ncarc(anda)(andb); + ncarc(c)(andb); + ncline(andb)(out); + \stopuseMPgraphic + + \placeexample[here][ex:And3]{Simple three port and.} + \startcombination[2*1] + {\typebufferhs{And3}}{Haskell description using function applications.} + {\boxedgraphic{And3}}{The architecture described by the Haskell description.} + \stopcombination \subsection{Partial application} It should be obvious that we cannot generate hardware signals for all @@ -47,19 +82,50 @@ represented as a signal or i/o port to a component. From this, we can see that the above translation rules do not apply to a - partial application. Let's look at an example: - - \starthaskell - -- | Multiply the input word by four. - quadruple :: Word -> Word - quadruple n = mul (mul n) - where - mul = (*) 2 - \stophaskell - - It should be clear that the above code describes the following hardware: - - TODO: Pretty picture + partial application. \in{Example}[ex:Quadruple] shows an example use of + partial application and the corresponding architecture. + +\startbuffer[Quadruple] +-- | Multiply the input word by four. +quadruple :: Word -> Word +quadruple n = mul (mul n) + where + mul = (*) 2 +\stopbuffer + + \startuseMPgraphic{Quadruple} + save in, two, mula, mulb, out; + + % I/O ports + newCircle.in(btex $n$ etex) "framed(false)"; + newCircle.two(btex $2$ etex) "framed(false)"; + newCircle.out(btex $out$ etex) "framed(false)"; + + % Components + newCircle.mula(btex $\times$ etex); + newCircle.mulb(btex $\times$ etex); + + two.c = origin; + in.c = two.c + (0cm, 1cm); + mula.c = in.c + (2cm, 0cm); + mulb.c = mula.c + (2cm, 0cm); + out.c = mulb.c + (2cm, 0cm); + + % Draw objects and lines + drawObj(in, two, mula, mulb, out); + + nccurve(two)(mula) "angleA(0)", "angleB(45)"; + nccurve(two)(mulb) "angleA(0)", "angleB(45)"; + ncline(in)(mula); + ncline(mula)(mulb); + ncline(mulb)(out); + \stopuseMPgraphic + + \placeexample[here][ex:Quadruple]{Simple three port and.} + \startcombination[2*1] + {\typebufferhs{Quadruple}}{Haskell description using function applications.} + {\boxedgraphic{Quadruple}}{The architecture described by the Haskell description.} + \stopcombination Here, the definition of mul is a partial function application: It applies \hs{2 :: Word} to the function \hs{(*) :: Word -> Word -> Word} resulting in @@ -77,15 +143,175 @@ completely applied. \section{State} - \subsection{Introduction} - Provide some examples - + A very important concept in hardware designs is \emph{state}. In a + stateless (or, \emph{combinatoric}) design, every output is a directly and solely dependent on the + inputs. In a stateful design, the outputs can depend on the history of + inputs, or the \emph{state}. State is usually stored in \emph{registers}, + which retain their value during a clockcycle, and are typically updated at + the start of every clockcycle. Since the updating of the state is tightly + coupled (synchronized) to the clock signal, these state updates are often + called \emph{synchronous}. + + To make our hardware description language useful to describe more that + simple combinatoric designs, we'll need to be able to describe state in + some way. \subsection{Approaches to state} - Explain impact of state (or rather, temporal behaviour) on function signature. + In Haskell, functions are always pure (except when using unsafe + functions like \hs{unsafePerformIO}, which should be prevented whenever + possible). This means that the output of a function solely depends on + its inputs. If you evaluate a given function with given inputs, it will + always provide the same output. + + TODO: Define pure + + This is a perfect match for a combinatoric circuit, where the output + also soley depend on the inputs. However, when state is involved, this + no longer holds. Since we're in charge of our own language, we could + remove this purity constraint and allow a function to return different + values depending on the cycle in which it is evaluated (or rather, the + current state). However, this means that all kinds of interesting + properties of our functional language get lost, and all kinds of + transformations and optimizations might no longer be meaning preserving. + + Provided that we want to keep the function pure, the current state has + to be present in the function's arguments in some way. There seem to be + two obvious ways to do this: Adding the current state as an argument, or + including the full history of each argument. + \subsubsection{Stream arguments and results} + Including the entire history of each input (\eg, the value of that + input for each previous clockcycle) is an obvious way to make outputs + depend on all previous input. This is easily done by making every + input a list instead of a single value, containing all previous values + as well as the current value. + + An obvious downside of this solution is that on each cycle, all the + previous cycles must be resimulated to obtain the current state. To do + this, it might be needed to have a recursive helper function as well, + wich might be hard to properly analyze by the compiler. + + A slight variation on this approach is one taken by some of the other + functional \small{HDL}s in the field (TODO: References to Lava, + ForSyDe, ...): Make functions operate on complete streams. This means + that a function is no longer called on every cycle, but just once. It + takes stream as inputs instead of values, where each stream contains + all the values for every clockcycle since system start. This is easily + modeled using an (infinite) list, with one element for each clock + cycle. Since the funciton is only evaluated once, its output is also a + stream. Note that, since we are working with infinite lists and still + want to be able to simulate the system cycle-by-cycle, this relies + heavily on the lazy semantics of Haskell. + + Since our inputs and outputs are streams, all other (intermediate) + values must be streams. All of our primitive operators (\eg, addition, + substraction, bitwise operations, etc.) must operate on streams as + well (note that changing a single-element operation to a stream + operation can done with \hs{map}, \hs{zipwith}, etc.). + + Note that the concept of \emph{state} is no more than having some way + to communicate a value from one cycle to the next. By introducing a + \hs{delay} function, we can do exactly that: Delay (each value in) a + stream so that we can "look into" the past. This \hs{delay} function + simply outputs a stream where each value is the same as the input + value, but shifted one cycle. This causes a \quote{gap} at the + beginning of the stream: What is the value of the delay output in the + first cycle? For this, the \hs{delay} function has a second input + (which is a value, not a stream!). + + \in{Example}[ex:DelayAcc] shows a simple accumulator expressed in this + style. + +\startbuffer[DelayAcc] +acc :: Stream Word -> Stream Word +acc in = out + where + out = (delay out 0) + in +\stopbuffer + +\startuseMPgraphic{DelayAcc} + save in, out, add, reg; + + % I/O ports + newCircle.in(btex $in$ etex) "framed(false)"; + newCircle.out(btex $out$ etex) "framed(false)"; + + % Components + newReg.reg("") "dx(4mm)", "dy(6mm)", "reflect(true)"; + newCircle.add(btex + etex); + + in.c = origin; + add.c = in.c + (2cm, 0cm); + out.c = add.c + (2cm, 0cm); + reg.c = add.c + (0cm, 2cm); + + % Draw objects and lines + drawObj(in, out, add, reg); + + nccurve(add)(reg) "angleA(0)", "angleB(180)", "posB(d)"; + nccurve(reg)(add) "angleA(180)", "angleB(-45)", "posA(out)"; + ncline(in)(add); + ncline(add)(out); +\stopuseMPgraphic + + + \placeexample[here][ex:DelayAcc]{Simple accumulator architecture.} + \startcombination[2*1] + {\typebufferhs{DelayAcc}}{Haskell description using streams.} + {\boxedgraphic{DelayAcc}}{The architecture described by the Haskell description.} + \stopcombination + + + This notation can be confusing (especially due to the loop in the + definition of out), but is essentially easy to interpret. There is a + single call to delay, resulting in a circuit with a single register, + whose input is connected to \hs{outl (which is the output of the + adder)}, and it's output is the \hs{delay out 0} (which is connected + to one of the adder inputs). + + This notation has a number of downsides, amongst which are limited + readability and ambiguity in the interpretation. TODO: Reference + Christiaan. + \subsubsection{Explicit state arguments and results} - Nested state for called functions. + A more explicit way to model state, is to simply add an extra argument + containing the current state value. This allows an output to depend on + both the inputs as well as the current state while keeping the + function pure (letting the result depend only on the arguments), since + the current state is now an argument. + + In Haskell, this would look like \in{example}[ex:ExplicitAcc]. + +\startbuffer[ExplicitAcc] +acc :: Word -> (State Word) -> (State Word, Word) +acc in (State s) = (State s', out) + where + out = s + in + s' = out +\stopbuffer + + \placeexample[here][ex:ExplicitAcc]{Simple accumulator architecture.} + \startcombination[2*1] + {\typebufferhs{ExplicitAcc}}{Haskell description using explicit state arguments.} + % Picture is identical to the one we had just now. + {\boxedgraphic{DelayAcc}}{The architecture described by the Haskell description.} + \stopcombination + + This approach makes a function's state very explicit, which state + variables are used by a function can be completely determined from its + type signature (as opposed to the stream approach, where a function + looks the same from the outside, regardless of what state variables it + uses (or wether it's stateful at all). + + A direct consequence of this, is that if a function calls other + stateful functions (\eg, has subcircuits), it has to somehow know the + current state for these called functions. The only way to do this, is + to put these \emph{substates} inside the caller's state. This means + that a function's state is the sum of the states of all functions it + calls, and its own state. + + This approach is the one chosen for Cλash and will be examined more + closely below. \subsection{Explicit state specification} Note about semantic correctness of top level state. @@ -353,7 +579,8 @@ Implementation issues: state splitting, linking input to output state, checking usage constraints on state variables. - \section{Recursion} + + \section[sec:recursion]{Recursion} An import concept in functional languages is recursion. In it's most basic form, recursion is a function that is defined in terms of itself. This usually requires multiple evaluations of this function, with changing