Hardware Reference
In-Depth Information
Chapter 12
Computation of Sequential Flexibility
in Networks of FSMs by Windowing
12.1
Flexibility in Networks of FSMs
This chapter addresses the problem of resynthesizing the component FSMs of a
network of FSMs; we will discuss both a global approach and a local (windowing)
approach.
It will turn out that sometimes it is more effective to solve a system of equations
instead of a single equation; therefore we will introduce systems of equations over
FSMs. The motivation is that, when optimizing a component FSM by solving a
single monolithic equation, the context and the specification may be so huge for
real sequential circuits, that they will be difficult to build. Using the fact that the
synchronous composition operator is associative, we will see that the task may
be simplified by applying a window approach, where we replace the solution
of a single large equation by the solution of a system of simpler equations. In
the windowing approach, the specification is restricted to be the composition of
only two component FSMs, and the context to a single component FSM, so that
the computational effort is reduced with respect to the general case, where the
specification is the composition of all component FSMs and the context is the
composition of all but one (the one to be resynthesized) component FSMs. For
the sake of simplicity, all component FSMs are assumed to be complete and
deterministic.
Example 12.1.
Consider the FSM network topology shown in Fig.
12.1
. Instances
of FSMs
M
C
are provided in Fig.
12.2
a-c respectively. There is a loop
containing component FSMs
M
A
,
M
B
and
M
A
and
M
B
, but there are no combinational cycles
because
M
A
is a Moore FSM. One can check that the reduced FSM
M
A
M
B
M
C
has two states as shown in Fig.
12.2
d.
Given the synchronous composition
M
A
1
M
A
j
M
A
n
of a collection of
complete and deterministic FSMs
M
A
1
;:::;M
A
j
;:::;M
A
n
, the largest solution of
the FSM equation
M
A
1
::: M
A
j 1
M
X
M
A
j C1
M
A
n
Š M
A
1
:::M
A
j 1
M
A
j
M
A
j C1
M
A
n
captures all the admissible behaviors that may replace a
Search WWH ::
Custom Search