Add some more stuff about state.

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

diff --git a/Chapters/HardwareDescription.tex b/Chapters/HardwareDescription.tex
index 90007ee02eee550c6a73d7a354229f6fe3209122..1571ff6acc31148a5bd75d27ddbdfb490ba71a29 100644 (file)
--- a/Chapters/HardwareDescription.tex
+++ b/Chapters/HardwareDescription.tex
@@ -27,17 +27,54 @@
   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:
+  \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

 
 

-  \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
+  \startuseMPgraphic{And3}
+    save a, b, c, anda, andb, out;

 
 

-  This results in the following hardware:
-  
-  TODO: Pretty picture
+    % 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
+
+  TODO: Define top level function and subfunctions/circuits.

 
   \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 +84,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:
+  partial application. \in{Example}[ex:Quadruple] shows an example use of
+  partial application and the corresponding architecture.

 
 

-  \starthaskell
-  -- | Multiply the input word by four.
-  quadruple :: Word -> Word
-  quadruple n = mul (mul n)
-    where
-      mul = (*) 2
-  \stophaskell
+\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);

 
 

-  It should be clear that the above code describes the following hardware:
+    nccurve(two)(mula) "angleA(0)", "angleB(45)";
+    nccurve(two)(mulb) "angleA(0)", "angleB(45)";
+    ncline(in)(mula);
+    ncline(mula)(mulb);
+    ncline(mulb)(out);
+  \stopuseMPgraphic

 
 

-  TODO: Pretty picture
+  \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


@@ -217,7 +285,8 @@ acc in = out
         In Haskell, this would look like \in{example}[ex:ExplicitAcc].
 
 \startbuffer[ExplicitAcc]
         In Haskell, this would look like \in{example}[ex:ExplicitAcc].
 
 \startbuffer[ExplicitAcc]

-acc :: Word -> (State Word) -> (State Word, Word)
+-- input -> current state -> (new state, output)
+acc :: Word -> Word -> (Word, Word)

 acc in (State s) = (State s', out)
   where
     out = s + in
 acc in (State s) = (State s', out)
   where
     out = s + in


@@ -237,26 +306,90 @@ acc in (State s) = (State s', out)
         looks the same from the outside, regardless of what state variables it
         uses (or wether it's stateful at all).
 
         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}
         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.
-
-      Note about automatic ``down-pushing'' of state.
-
-      Note about explicit state specification as the best solution.
-
-      Note about substates
-
-      Note about conditions on state variables and checking them.
+      We've seen the concept of explicit state in a simple example below, but
+      what are the implications of this approach?
+
+      \subsubsection{Substates}
+        Since a function's state is reflected directly in its type signature,
+        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 also means that the type of a function (at least the "state"
+        part) is dependent on its implementation and the functions it calls.
+        This is the major downside of this approach: The separation between
+        interface and implementation is limited. However, since Cλash is not
+        very suitable for separate compilation (see
+        \in{section}[sec:prototype:separate]) this is not a big problem in
+        practice. Additionally, when using a type synonym for the state type
+        of each function, we can still provide explicit type signatures
+        while keeping the state specification for a function near its
+        definition only.
+    
+      \subsubsection{...}
+        We need some way to know which arguments should become input ports and
+        which argument(s?) should become the current state (\eg, be bound to
+        the register outputs). This does not hold holds not just for the top
+        level function, but also for any subfunctions. Or could we perhaps
+        deduce the statefulness of subfunctions by analyzing the flow of data
+        in the calling functions?
+
+        To explore this matter, we make an interesting observation: We get
+        completely correct behaviour when we put all state registers in the
+        top level entity (or even outside of it). All of the state arguments
+        and results on subfunctions are treated as normal input and output
+        ports. Effectively, a stateful function results in a stateless
+        hardware component that has one of its input ports connected to the
+        output of a register and one of its output ports connected to the
+        input of the same register.
+
+        TODO: Example?
+
+        Of course, even though the hardware described like this has the
+        correct behaviour, unless the layout tool does smart optimizations,
+        there will be a lot of extra wire in the design (since registers will
+        not be close to the component that uses them). Also, when working with
+        the generated \small{VHDL} code, there will be a lot of extra ports
+        just to pass one state values, which can get quite confusing.
+
+        To fix this, we can simply \quote{push} the registers down into the
+        subcircuits. When we see a register that is connected directly to a
+        subcircuit, we remove the corresponding input and output port and put
+        the register inside the subcircuit instead. This is slightly less
+        trivial when looking at the Haskell code instead of the resulting
+        circuit, but the idea is still the same.
+
+        TODO: Example?
+
+        However, when applying this technique, we might push registers down
+        too far. When you intend to store a result of a stateless subfunction
+        in the caller's state and pass the current value of that state
+        variable to that same function, the register might get pushed down too
+        far. It is impossible to distinguish this case from similar code where
+        the called function is in fact stateful. From this we can conclude
+        that we have to either:
+
+        \startitemize
+        \item accept that the generated hardware might not be exactly what we
+        intended, in some specific cases. In most cases, the hardware will be
+        what we intended.
+        \item explicitely annotate state arguments and results in the input
+        description.
+        \stopitemize
+
+        The first option causes (non-obvious) exceptions in the language
+        intepretation. Also, automatically determining where registers should
+        end up is easier to implement correctly with explicit annotations, so
+        for these reasons we will look at how this annotations could work.
+
+
+      TODO: Note about conditions on state variables and checking them.

 
     \subsection{Explicit state implementation}
       Recording state variables at the type level.
 
     \subsection{Explicit state implementation}
       Recording state variables at the type level.