X-Git-Url: https://git.stderr.nl/gitweb?p=matthijs%2Fmaster-project%2Freport.git;a=blobdiff_plain;f=progress-2009.01.28.txt;fp=progress-2009.01.28.txt;h=e690697a2b1ad8f00aef7e4778b7fe74ccaa29ae;hp=0000000000000000000000000000000000000000;hb=84d984a32326eefa22249bd377e452aed14671df;hpb=612e72177321ead79248a8dcf49b783f8153d967 diff --git a/progress-2009.01.28.txt b/progress-2009.01.28.txt new file mode 100644 index 0000000..e690697 --- /dev/null +++ b/progress-2009.01.28.txt @@ -0,0 +1,245 @@ +How to model hardware? +====================== +So far, we've had some ideas about how to model hardware using a functional +language. The general idea is that every function that models hardware has +some input signals, some "input" state and a few output signals and "output" +state. But how do we represent this exactly in our haskell code? + +The output part is probably easiest, since a function always returns a single +value. Since it needs to return both output signals and a state, it seems +obvious to make it always return a 2-tuple containing the state and output +signals. So: + + circuit :: ? -> (State, Signals) (1) + +It's interesting to note that the State and Signal types here are not really +important when simulating, so let's look at the inputs first. + +Again, we have both input signals and a state to pass to the function. It +seems consistent to again do this a single tuple, so a circuit becomes: + + circuit :: (State, Signals) -> (State, Signals) (2) + +I've not given this variant a lot of thought yet, but i have the feeling this +is not all to useful. The variant I've been using so far separates the state +and signals into separate arguments: + + circuit :: Signals -> State -> (State, Signals) (4) + +Note that this uses a seemingly inconsistent order for the arguments, but +that's mostly because the current implementation uses this order (and wasn't +well thought out). The exact order is mostly relevant for partial application, +but I'm not quite sure if that's possible or useful at all. + +This variant makes it easy to define a dependent type for all circuits, which +you pass the input, state and output types as an argument: + + type Circuit a s b = a -> s -> (s, b) (5) + +A last variant would be to separate each (or perhaps only some) input signals +into different arguments, such that each input has its own argument. For +example, for a two input port circuit: + + circuit :: Signal -> Signal -> State -> (State, Signals) (6) + +This has the obvious advantage that it could support partial application of +the input ports (ie, connect a few input pins to a circuit and pass the +resulting function elsewhere). I'm not sure how that would or should work out, +but it seems useful. + +However, this partial application seems only possible with input ports, which +might limit its usefuleness. Also, this type signature makes it harder to +define a single Circuit type that catches all circuits as with (4) and (5). +This might make simulation more tricky, though it's probably not critical. + +Signals (or Ports?) +------------------- +Now, regardless of which of the above approaches we choose, there should be +some way to model these signals and ports. So far, a basic Bit signal type +has been used: + + data Bit = High | Low | DontCare (7) + +For now, this is the only primitive type supported by the (Haskell-to-VHDL) +translator, but as pointed out above the simulator doesn't really care about +these types (as long as the input provided is of the right type). Supporting +native Haskell types (or perhaps our own variants, *e.g.*, an Int with a fixed +bit width) is probably needed later on as well. + +To allow for multiple input and output ports in a single value, tuples can be +used. This allows for grouping multiple signals while still allowing each +signal to have a different type. + +An alternative that has not been explored yet is the use of an algebraic type +to group signals. This seems to have the direct advantage of allowing names +for each element to be specified, but does add some overhead in type +declarations. It's likely that a combination of tuples and algebraic types are +best. + +It appears that lists might become useful to model VHDL (bit)vectors, since +both lists and vectors have elements of the same type. This does require that +the length of a list can be deduced at compile time. + +DontCare +-------- +In the above definition of the Bit datatype a DontCare element was present. +The idea behind this element was to assign it anywhere the value of the bit +shouldn't matter (in the alu example, this is but on the input signals that +should be ignored). Since it is not used in any other place (*e.g.*, patterns +usually only match Low and High, including the display functions), Haskell +should error out as soon as a DontCare value is actually used. Due to the lazy +nature of Haskell's evaluation, this should never happen as long as the value +is not really used. But as soon as the value is (indirectly) needed, *i.e.*, +contributes to the output of a circuit, Haskell errors out. + +Some functions ignore some inputs. For example, hwor is defined as: + + High `hwor` _ = High (8) + _ `hwor` High = High + Low `hwor` Low = Low + +This means that High `hwxor` DontCare will still be High (with no error), but +that DontCare `hwand` DontCare will immediately throw an error. This seems to +be desired behaviour, but this needs more investigation. + +State +----- +For state, we can mostly do the same reasoning as for signals (from the +circuit description point of view, input state and output state is hardly any +differen from input signals and output signals). For combining multiple +elements of state (either because a circuit has multiple Bits of state or +because it combines the states of each of its subcircuits), tuples can be +used. Algebraic types might have a use here as well. + +Stateless circuits +------------------ +Above we've concentrated on stateful circuits, but probably a lot of circuits +will be stateless. This can simply be modeled by having an empty state +(*i.e.*, () ), but that's not very elegant. However, not all of the above +approaches are usable for supporting stateless circuits. For example, if we +adapt (2) to be stateless: + + stateless_circuit :: Signals -> Signals (9) + +Now, considering that we allowed Signals to be a tuple of multiple signals, +the following two circuit types are indistinguishable, since the State and +Signal types are the same. + + stateless_circuit :: (Signal, Signal) -> (Signal, Signal) (10) + stateful_circuit :: (State, Signal) -> (State, Signal) + +Something similar goes for (6), where leaving out the state for stateless +circuits would make a stateless circuit with two inputs and two output +indistinguishable from a stateful circuit with a single input and a single +output. + +(4) above seems best suited for adapting for stateless circuits, since it +always has two arguments (inputs and state). A stateless variant would always +have a single argument. + +Examples +-------- +To get a feeling for things, here are some example using approach (6). + +Some stateless adders: + + -- Combinatoric stateless no-carry adder + -- A -> B -> S + no_carry_adder :: (Bit, Bit) -> Bit + no_carry_adder (a, b) = a `hwxor` b + + -- Combinatoric stateless half adder + -- A -> B -> (S, C) + half_adder :: (Bit, Bit) -> (Bit, Bit) + half_adder (a, b) = + ( a `hwxor` b, a `hwand` b ) + + -- Combinatoric stateless full adder + -- (A, B, C) -> (S, C) + full_adder :: (Bit, Bit, Bit) -> (Bit, Bit) + full_adder (a, b, cin) = (s, c) + where + s = a `hwxor` b `hwxor` cin + c = a `hwand` b `hwor` (cin `hwand` (a `hwxor` b)) + +A simple four bit cyclic shift register, which has an input that can be used +to toggle (xor) the first position. + + type ShifterState = [Bit] + shifter :: Bit -> ShifterState -> (ShifterState, Bit) + shifter i s = + (s', o) + where + s' = (o `hwxor` i) : (init s) + o = last s + +An implementation of a simple ALU (supporting only two operations: or & and on +two one-bit inputs) combined with a register bank containing two one-bit +registers. It also contains a list of inputs (the program), an initial state +and some wrappers around the simulation functions (main and mainIO). + + main = Sim.simulate exec program initial_state + mainIO = Sim.simulateIO exec initial_state + + program = [ + -- (addr, we, op) + (High, Low, High), -- z = r1 and t (0) ; t = r1 (1) + (Low, Low, Low), -- z = r0 or t (1); t = r0 (0) + (Low, High, DontCare), -- r0 = z (1) + (High, Low, High), -- z = r1 and t (0); t = r1 (1) + (High, High, DontCare) -- r1 = z (0) + ] + + initial_state = ((Low, High), (), Low, Low) + + -- Register bank + + type RegAddr = Bit + type RegisterBankState = (Bit, Bit) + register_bank :: + (RegAddr, Bit, Bit) -> -- (addr, we, d) + RegisterBankState -> -- s + (RegisterBankState, Bit) -- (s', o) + + register_bank (Low, Low, _) s = -- Read r0 + (s, fst s) + + register_bank (High, Low, _) s = -- Read r1 + (s, snd s) + + register_bank (addr, High, d) s = -- Write + (s', DontCare) + where + (r0, r1) = s + r0' = if addr == Low then d else r0 + r1' = if addr == High then d else r1 + s' = (r0', r1') + + -- ALU + + type AluState = () + type AluOp = Bit + + alu :: (AluOp, Bit, Bit) -> AluState -> (AluState, Bit) + alu (High, a, b) s = ((), a `hwand` b) + alu (Low, a, b) s = ((), a `hwor` b) + + type ExecState = (RegisterBankState, AluState, Bit, Bit) + exec :: (RegAddr, Bit, AluOp) -> ExecState -> (ExecState, ()) + + -- Read & Exec + exec (addr, Low, op) s = + (s', ()) + where + (reg_s, alu_s, t, z) = s + (reg_s', t') = register_bank (addr, Low, DontCare) reg_s + (alu_s', z') = alu (op, t', t) alu_s + s' = (reg_s', alu_s', t', z') + + -- Write + exec (addr, High, op) s = + (s', ()) + where + (reg_s, alu_s, t, z) = s + (reg_s', _) = register_bank (addr, High, z) reg_s + s' = (reg_s', alu_s, t, z)