Add two pictures.

[matthijs/master-project/report.git] / Chapters / HardwareDescription.tex

diff --git a/Chapters/HardwareDescription.tex b/Chapters/HardwareDescription.tex
index 0266490bf21c51bac670b20317846507883cccd0..0ec41f7403eab8c595bca563a743ff74b78a8147 100644 (file)
--- 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.
 
   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
 
   \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
   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
 
   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}
   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}
 
     \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}
       \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}
       \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.
 
     \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.
 
       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
   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