Hardware Reference
In-Depth Information
M
B
and obtain the solution
M
B
0
that does not depend on input
U
and is shown in
Fig.
12.2
f.
Therefore, the component FSM
M
B
can be replaced by
M
B
0
independent from
input
M
A
becomes superfluous, i.e., it can be deleted
from the composition, because there is no need to produce the internal output
U
, and so the component FSM
U
(and
also no need for
M
B
0
to produce the internal output
V
). By direct inspection, one
can verify that the composition of the FSM
M
B
0
and of the component FSM
M
C
is
equivalent to the composition
M
A
M
B
M
C
(the latter is shown in Fig.
12.2
d).
The proposed strategy for resynthesis is a global one, because it takes into
account the complete network in computing the flexibility of the components. Its
main disadvantage is that collapsing a system of interacting FSMs into a single FSM
(the specification and the context) may cause state explosion, since the collapsed
FSMs are huge for real applications. In order to alleviate the computational effort, at
the price of missing some flexibility, we propose local optimization procedures that
apply windowing strategies to networks of FSM (cf. windowing applied to netlists
in Chap. 11).
12.2
Windowing in a Network of FSMs
Given a component FSM to be resynthesized, it is reasonable to assume that its
behavior depends mostly on its neighbouring machines. Therefore, we will propose
strategies to compute the flexibility of a component with respect to its neighbours
instead of the entire context.
12.2.1
Windowing Via Solving a Set of Equations
Given the FSM network
M
A
1
M
An
and a component FSM
M
A
j
, consider
another component FSM
M
A
t
connected with
M
A
j
, and the equation
M
X
M
A
t
Š
M
A
j
M
B
j
M
A
t
Š
M
A
j
M
A
t
. Since the composition operator is commutative and associative, the
composition
M
A
t
. For each solution
M
B
j
of the equation, it holds that
M
A
1
M
A
j
M
A
t
M
A
n
is equivalent to
M
A
1
.M
A
j
M
A
t
/ M
A
n
,andalsoto
M
A
1
.M
B
j
M
A
t
/ M
A
n
and
finally to
M
A
1
M
B
j
M
A
t
M
A
n
, i.e., each solution of the equation
can replace the component FSM
M
A
j
without changing the external behavior of the
overall composition. So the following statement holds.
Proposition 12.2.1
Given the composition
M
A
1
M
A
j
M
A
t
:::M
A
n
,
let
M
A
j
and
M
A
t
be connected component FSMs. For each solution
M
B
j
of the
Search WWH ::
Custom Search