progress-2009.01.28.txt

   1 How to model hardware?
   2 ======================
   3 So far, we've had some ideas about how to model hardware using a functional
   4 language. The general idea is that every function that models hardware has
   5 some input signals, some "input" state and a few output signals and "output"
   6 state. But how do we represent this exactly in our haskell code?
   7
   8 The output part is probably easiest, since a function always returns a single
   9 value. Since it needs to return both output signals and a state, it seems
  10 obvious to make it always return a 2-tuple containing the state and output
  11 signals. So:
  12
  13     circuit :: ? -> (State, Signals)                                    (1)
  14
  15 It's interesting to note that the State and Signal types here are not really
  16 important when simulating, so let's look at the inputs first.
  17
  18 Again, we have both input signals and a state to pass to the function. It
  19 seems consistent to again do this a single tuple, so a circuit becomes:
  20
  21     circuit :: (State, Signals) -> (State, Signals)                     (2)
  22
  23 I've not given this variant a lot of thought yet, but i have the feeling this
  24 is not all to useful. The variant I've been using so far separates the state
  25 and signals into separate arguments:
  26
  27     circuit :: Signals -> State -> (State, Signals)                     (4)
  28
  29 Note that this uses a seemingly inconsistent order for the arguments, but
  30 that's mostly because the current implementation uses this order (and wasn't
  31 well thought out). The exact order is mostly relevant for partial application,
  32 but I'm not quite sure if that's possible or useful at all.
  33
  34 This variant makes it easy to define a dependent type for all circuits, which
  35 you pass the input, state and output types as an argument:
  36
  37     type Circuit a s b = a -> s -> (s, b)                               (5)
  38
  39 A last variant would be to separate each (or perhaps only some) input signals
  40 into different arguments, such that each input has its own argument. For
  41 example, for a two input port circuit:
  42
  43     circuit :: Signal -> Signal -> State -> (State, Signals)            (6)
  44
  45 This has the obvious advantage that it could support partial application of
  46 the input ports (ie, connect a few input pins to a circuit and pass the
  47 resulting function elsewhere). I'm not sure how that would or should work out,
  48 but it seems useful.
  49
  50 However, this partial application seems only possible with input ports, which
  51 might limit its usefuleness. Also, this type signature makes it harder to
  52 define a single Circuit type that catches all circuits as with (4) and (5).
  53 This might make simulation more tricky, though it's probably not critical.
  54
  55 Signals (or Ports?)
  56 -------------------
  57 Now, regardless of which of the above approaches we choose, there should be
  58 some way to model these signals and ports. So far, a basic Bit signal type
  59 has been used:
  60
  61     data Bit = High | Low | DontCare                                    (7)
  62
  63 For now, this is the only primitive type supported by the (Haskell-to-VHDL)
  64 translator, but as pointed out above the simulator doesn't really care about
  65 these types (as long as the input provided is of the right type). Supporting
  66 native Haskell types (or perhaps our own variants, *e.g.*, an Int with a fixed
  67 bit width) is probably needed later on as well.
  68
  69 To allow for multiple input and output ports in a single value, tuples can be
  70 used. This allows for grouping multiple signals while still allowing each
  71 signal to have a different type.
  72
  73 An alternative that has not been explored yet is the use of an algebraic type
  74 to group signals. This seems to have the direct advantage of allowing names
  75 for each element to be specified, but does add some overhead in type
  76 declarations. It's likely that a combination of tuples and algebraic types are
  77 best.
  78
  79 It appears that lists might become useful to model VHDL (bit)vectors, since
  80 both lists and vectors have elements of the same type. This does require that
  81 the length of a list can be deduced at compile time.
  82
  83 DontCare
  84 --------
  85 In the above definition of the Bit datatype a DontCare element was present.
  86 The idea behind this element was to assign it anywhere the value of the bit
  87 shouldn't matter (in the alu example, this is but on the input signals that
  88 should be ignored). Since it is not used in any other place (*e.g.*, patterns
  89 usually only match Low and High, including the display functions), Haskell
  90 should error out as soon as a DontCare value is actually used. Due to the lazy
  91 nature of Haskell's evaluation, this should never happen as long as the value
  92 is not really used. But as soon as the value is (indirectly) needed, *i.e.*,
  93 contributes to the output of a circuit, Haskell errors out.
  94
  95 Some functions ignore some inputs. For example, hwor is defined as:
  96
  97     High `hwor` _  = High                                               (8)
  98     _ `hwor` High  = High
  99     Low `hwor` Low = Low
 100
 101 This means that High `hwxor` DontCare will still be High (with no error), but
 102 that DontCare `hwand` DontCare will immediately throw an error. This seems to
 103 be desired behaviour, but this needs more investigation.
 104
 105 State
 106 -----
 107 For state, we can mostly do the same reasoning as for signals (from the
 108 circuit description point of view, input state and output state is hardly any
 109 differen from input signals and output signals). For combining multiple
 110 elements of state (either because a circuit has multiple Bits of state or
 111 because it combines the states of each of its subcircuits), tuples can be
 112 used. Algebraic types might have a use here as well.
 113
 114 Stateless circuits
 115 ------------------
 116 Above we've concentrated on stateful circuits, but probably a lot of circuits
 117 will be stateless. This can simply be modeled by having an empty state
 118 (*i.e.*, () ), but that's not very elegant. However, not all of the above
 119 approaches are usable for supporting stateless circuits. For example, if we
 120 adapt (2) to be stateless:
 121
 122     stateless_circuit :: Signals -> Signals                             (9)
 123
 124 Now, considering that we allowed Signals to be a tuple of multiple signals,
 125 the following two circuit types are indistinguishable, since the State and
 126 Signal types are the same.
 127
 128     stateless_circuit :: (Signal, Signal) -> (Signal, Signal)           (10)
 129     stateful_circuit :: (State, Signal) -> (State, Signal)
 130
 131 Something similar goes for (6), where leaving out the state for stateless
 132 circuits would make a stateless circuit with two inputs and two output
 133 indistinguishable from a stateful circuit with a single input and a single
 134 output.
 135
 136 (4) above seems best suited for adapting for stateless circuits, since it
 137 always has two arguments (inputs and state). A stateless variant would always
 138 have a single argument.
 139
 140 Examples
 141 --------
 142 To get a feeling for things, here are some example using approach (6).
 143
 144 Some stateless adders:
 145
 146     -- Combinatoric stateless no-carry adder
 147     -- A -> B -> S
 148     no_carry_adder :: (Bit, Bit) -> Bit
 149     no_carry_adder (a, b) = a `hwxor` b
 150
 151     -- Combinatoric stateless half adder
 152     -- A -> B -> (S, C)
 153     half_adder :: (Bit, Bit) -> (Bit, Bit)
 154     half_adder (a, b) =
 155       ( a `hwxor` b, a `hwand` b )
 156
 157     -- Combinatoric stateless full adder
 158     -- (A, B, C) -> (S, C)
 159     full_adder :: (Bit, Bit, Bit) -> (Bit, Bit)
 160     full_adder (a, b, cin) = (s, c)
 161       where
 162         s = a `hwxor` b `hwxor` cin
 163         c = a `hwand` b `hwor` (cin `hwand` (a `hwxor` b))
 164
 165 A simple four bit cyclic shift register, which has an input that can be used
 166 to toggle (xor) the first position.
 167
 168     type ShifterState = [Bit]
 169     shifter :: Bit -> ShifterState -> (ShifterState, Bit)
 170     shifter i s =
 171       (s', o)
 172       where
 173         s' = (o `hwxor` i) : (init s)
 174         o  = last s
 175
 176 An implementation of a simple ALU (supporting only two operations: or & and on
 177 two one-bit inputs) combined with a register bank containing two one-bit
 178 registers. It also contains a list of inputs (the program), an initial state
 179 and some wrappers around the simulation functions (main and mainIO).
 180
 181     main = Sim.simulate exec program initial_state
 182     mainIO = Sim.simulateIO exec initial_state
 183
 184     program = [
 185                 -- (addr, we, op)
 186                 (High, Low, High), -- z = r1 and t (0) ; t = r1 (1)
 187                 (Low, Low, Low), -- z = r0 or t (1); t = r0 (0)
 188                 (Low, High, DontCare), -- r0 = z (1)
 189                 (High, Low, High), -- z = r1 and t (0); t = r1 (1)
 190                 (High, High, DontCare) -- r1 = z (0)
 191               ]
 192
 193     initial_state = ((Low, High), (), Low, Low)
 194
 195     -- Register bank
 196
 197     type RegAddr = Bit
 198     type RegisterBankState = (Bit, Bit)
 199     register_bank ::
 200       (RegAddr, Bit, Bit) -> -- (addr, we, d)
 201       RegisterBankState -> -- s
 202       (RegisterBankState, Bit) -- (s', o)
 203
 204     register_bank (Low, Low, _) s = -- Read r0
 205       (s, fst s)
 206
 207     register_bank (High, Low, _) s = -- Read r1
 208       (s, snd s)
 209
 210     register_bank (addr, High, d) s = -- Write
 211       (s', DontCare)
 212       where
 213         (r0, r1) = s
 214         r0' = if addr == Low then d else r0
 215         r1' = if addr == High then d else r1
 216         s' = (r0', r1')
 217
 218     -- ALU
 219
 220     type AluState = ()
 221     type AluOp = Bit
 222
 223     alu :: (AluOp, Bit, Bit) -> AluState -> (AluState, Bit)
 224     alu (High, a, b) s = ((), a `hwand` b)
 225     alu (Low, a, b) s = ((), a `hwor` b)
 226
 227     type ExecState = (RegisterBankState, AluState, Bit, Bit)
 228     exec :: (RegAddr, Bit, AluOp) -> ExecState -> (ExecState, ())
 229
 230     -- Read & Exec
 231     exec (addr, Low, op) s =
 232       (s', ())
 233       where
 234         (reg_s, alu_s, t, z) = s
 235         (reg_s', t') = register_bank (addr, Low, DontCare) reg_s
 236         (alu_s', z') = alu (op, t', t) alu_s
 237         s' = (reg_s', alu_s', t', z')
 238
 239     -- Write
 240     exec (addr, High, op) s =
 241       (s', ())
 242       where
 243         (reg_s, alu_s, t, z) = s
 244         (reg_s', _) = register_bank (addr, High, z) reg_s
 245         s' = (reg_s', alu_s, t, z)