Semantics and Verification of a Language for Modelling Hardware Architectures - Formal Methods and Hybrid Real-Time Systems - page 304

between transitions. They are the only way for the controller to test conditions
and make branching transitions.

2.2 Constructing Hardware from an FSMD

The translation of an FSMD model into hardware is done by translating the con-
troller part into its hardware representation, and creating the hardware datapath
as a parallel composition of all basic blocks, where in each basic block all operators
are implemented by a hardware component. Finally, the components of the hard-
ware datapath and the hardware controller are connected by appropriate signals.
Although this translation may seem straightforward, several optimizations
may be applied in order to arrive at a more ecient hardware implementation:
- As only one transition is taken in any given cycle, hardware resources may
be shared between different transitions.
- The number of operators may be reduced further by splitting a transition
into a sequence of transitions as explained below.
The actual execution time of a program depends on the number of cycles to
be executed and the time taken to execute a single cycle. The minimum cycle
time is determined by the longest path through the hardware of any of the basic
blocks. There is, therefore, a tradeoff between few transitions and long cycle
time and many transitions with faster cycle time. By splitting a basic block with
a long path through the hardware over two or more transitions, more resource
sharing may be obtained, resulting in less area requirements, while the overall
system performance may be the same if, for instance, the number of cycles have
been doubled while the cycle time has been halved.

Program text Basic blocks Mealy graph

A: n:=N;
f0 := 0;
f1 := 1;
n>0
B: f1 := f0+f1;
f0 := f1-f0;
n := n-1;
n>0
C: output f1;

int n, f0, f1;
n:=N;
f0 := 0; f1 := 1;
while (n>0) do
f1 := f0+f1;
f0 := f1-f0;
n := n-1;

A

B

C

od
output f1;

Fig. 4. From a program text to a state transition graph

Fig. 4 shows an example of a program where the basic blocks form a set of
parallel assignments. Fig. 5 shows two possible schedules of the computation in
basic block B from Fig. 4. The left schedule computes in one cycle but then
requires two arithmetic units (ALU's), while the right schedule requires two
cycles but only one ALU as the two operations (Add and Sub) are executed in
different cycles and hence may share the same resource.