Computation of Sequential Flexibility in Networks of FSMs byWindowing - The Unknown Component Problem: Theory and Applications - page 190

Example 12.3. A replacement of the component FSM M B in Fig. 12.1 can be found

by solving the two equations M X C M C Š M B

M C . By direct inspection, one can check that the largest solution of the equation
M X M A Š M B M A coincides with the largest solution of the global equation
M X M A M C Š M B M A M C , shown in Fig. 12.2 e; therefore the FSM

M X A M A Š M B M A and

M B 0 in
Fig. 12.2 f can be obtained by solving a simpler equation. Indeed one can check that
the specification FSM M B M A has a single state and two transitions; moreover,

the context FSM M A has two states and eight transitions, as shown in Fig. 12.2 a.

Therefore the second equation cannot improve the FSM

M B 0 .
Resynthesis and optimization based on the window approach are computationally
cheaper than global optimization, because we do not need to consider the whole
network. The process can terminate once a solution of reasonable size is obtained.
However, when using local optimization an optimal solution may be missed, since
not all the component FSMs are taken into account.

Example 12.4. In Table 12.1 we report some experiments obtained by the compo-
sition and resynthesis of triples of FSMs from the LGSynth93 suite [87]. The letters
s denote the number of states and inputs of a corresponding benchmark. The

fourth, fifth and sixth columns report the number of states of a component FSM after
local and global optimization with respect to the minimum number of states.
When optimizing the head and the tail machines, a single FSM equation w.r.t. a
neighbor FSM was solved, while when optimizing the middle component machine
a collection of two equations was solved. Then in either case an optimal solution
was selected, to be a reduction of the largest solution that is a submachine with
a minimum number of states (with the usual requirement that such reduction be a
solution),
As an example, consider the last network in the table defined by the composition
of shiftreg , modulo12 and dk512 . In the first step the tail component FSM dk512
with two inputs and 15 states can be replaced with FSM

and i

M C 0 with 13 states. When

the tail machine dk512 is replaced with M C 0 , the middle component FSM becomes

reducible and is replaced with FSM M B 0 with 11 states. We repeat the optimization

process for the composition of shiftreg , M C 0 , and reduce the middle

and tail component FSMs to FSMs with 10 and 11 states, respectively. The head
component FSM cannot be reduced. As a result, we get a final composition whose
head component FSM has eight states, the middle component FSM has 10 states
and the tail component FSM has 11 states, matching the global optimum solution.

M B 0 and

However, in Sect. 12.2.2 we will discuss cases when the component FSM of
interest cannot be reduced by solving a set of equations, but requires instead a
system of equations.