Recipe
Contents
Description
A library for writing behavioural descriptions in York Lava, inspired by Page and Luk's "Compiling Occam into Field-Programmable Gate Arrays", Oxford Workshop on Field Programmable Logic and Applications, 1991. Features explicit clocking, signals as well as registers, shared procedure calls, and an optimiser. The implementation is short and sweet! Used in the implementation of the Reduceron, a graph reduction machine for Xilinx FPGAs.
To illustrate, consider the implementation of a sequential multiplier using the shift-and-add algorithm.
import Lava import Recipe
We define a state type containing three registers: the two inputs to multiply, and the result of the multiplication.
data Mult n = Mult { a, b, result :: Reg n }
A value of type Mult n is created by newMult.
newMult :: N n => New (Mult n) newMult = return Mult `ap` newReg `ap` newReg `ap` newReg
The shift-and-add recipe operates over a value of type Mult n.
shiftAndAdd s =
While (s!b!val =/= 0) $
Seq [ s!a <== s!a!val!shr
, s!b <== s!b!val!shl
, s!b!val!vhead |>
s!result <== s!result!val + s!a!val
, Tick
]
shr x = low +> vinit x
shl x = vtail x <+ low
Three remarks are in order:
- The
!operator is flipped application with a high precedence.
infixl 9 !
(!) :: a -> (a -> b) -> b
x!f = f x
This gives descriptions an appropriate object-oriented flavour.
- The value of a variable is obtained using the function
val :: Var v => v n -> Word n
Registers (of type Reg) are an instance of the Var class.
- The functions
+>and<+perform cons and snoc operations on vectors,vheadtakes the head of a vector, and=/=is generic disequality.
To actually perform a multiplication, the input variables need to be initialised.
multiply x y s = Seq [ s!a <== x, s!b <== y, s!result <== 0, Tick, s!shiftAndAdd ]
example :: Mult N8 -> Recipe example s = s!multiply 5 25
simExample = simRecipe newMult example result
Evaluating simExample yields 25 :: Word N8.
See REDUCERON MEMO 23 - included in the package and available at
http://www.cs.york.ac.uk/fp/reduceron/ - for further details and
examples.
- data Recipe
- (|>) :: Bit -> Recipe -> Recipe
- call :: Proc -> Recipe
- class Var v where
- (!) :: a -> (a -> b) -> b
- (-->) :: a -> b -> (a, b)
- type New a = RWS Schedule (Bit, Recipe) VarId a
- data Reg n
- newReg :: N n => New (Reg n)
- newRegInit :: N n => Word n -> New (Reg n)
- data Sig n
- newSig :: N n => New (Sig n)
- newSigDef :: N n => Word n -> New (Sig n)
- data Proc
- newProc :: Recipe -> New Proc
- recipe :: New a -> (a -> Recipe) -> Bit -> (a, Bit)
- simRecipe :: Generic b => New a -> (a -> Recipe) -> (a -> b) -> b
Recipe constructs
Constructors
| Skip | The most basic recipe; does nothing. |
| Tick | Does nothing, but takes one clock-cycle to do it. |
| Seq [Recipe] | Sequential composition of recipes. |
| Par [Recipe] | Fork-Join parallel composition of recipes. |
| While Bit Recipe | Run a recipe while a condition holds. |
| Do Recipe Bit | Like |
Mutable variables; named locations that can be read from and assigned to.
The New monad
Mutable variables: registers and signals
Register variables: assignments to a register come into effect in the clock-cycle after the assignment is performed; the initial value of a register is zero unless otherwise specified.
Signal variables: assignments to a signal come into effect in the current clock-cycle, but last only for the duration of that clock-cycle; if a signal not assigned to in a clock-cycle then its value will be its default value which is zero unless otherwise specified.
Shared procedures
newProc :: Recipe -> New ProcSource
Capture a recipe as shared procedure that can be called whenever desired; needless to say, the programmer should avoid parallel calls to the same shared procedure!