Add some more content to the State section.
authorMatthijs Kooijman <matthijs@stdin.nl>
Fri, 23 Oct 2009 19:03:28 +0000 (21:03 +0200)
committerMatthijs Kooijman <matthijs@stdin.nl>
Fri, 23 Oct 2009 19:03:28 +0000 (21:03 +0200)
Chapters/HardwareDescription.tex

index 246cb30a05977ce8ceb0c55a0fae635f7fc8523c..90007ee02eee550c6a73d7a354229f6fe3209122 100644 (file)
   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.