From: Matthijs Kooijman Date: Mon, 26 Oct 2009 14:07:10 +0000 (+0100) Subject: Add some more stuff about state. X-Git-Tag: final-thesis~190 X-Git-Url: https://git.stderr.nl/gitweb?p=matthijs%2Fmaster-project%2Freport.git;a=commitdiff_plain;h=38af31872d0108220e14104f75f816fcd4e326dd;hp=46e3a9e0c8d1bc5601080c1f8d176a51f9c1db2a Add some more stuff about state. --- diff --git a/Chapters/HardwareDescription.tex b/Chapters/HardwareDescription.tex index 0ec41f7..1571ff6 100644 --- a/Chapters/HardwareDescription.tex +++ b/Chapters/HardwareDescription.tex @@ -74,6 +74,8 @@ and3 a b c = and (and a b) c {\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 expressions we can express in Haskell. The most obvious criterium for this @@ -283,7 +285,8 @@ acc in = out 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 @@ -303,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). - 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. - - 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.