Manipulations of FSMs Represented as Sequential Circuits - The Unknown Component Problem: Theory and Applications - page 125

Tabl e 7. 1 Comparison of partitioned and monolithic representations

Name i=o=cs F cs =X cs States( X ) Part,s Mono,s Ratio

s510 19/7/6 3/3 54 0.3 0.2 0.7

s208 10/1/8 4/4 497 0.4 0.8 2.0

s298 3/6/14 7/7 553 0.9 2.7 3.0

s349 9/11/15 5/10 2,626 37.7 810.3 21.5

s444 3/6/21 5/16 17,730 25.9 CNC -

s526 3/6/21 5/16 141,829 276.7 CNC -

Tab le 7.1 lists the results for several examples. The columns show the example name
(column “Name”), the number of inputs, outputs and latches (column “ i=o=cs ”), the
number of latches in the fixed part and in the current implementation of the unknown
(column “ F cs =X cs ”), the number of states in the CSF (column “States( X )”), the
runtime in seconds of the partitioned algorithm (column “Part”) and runtime in
seconds using monolithic representations (column “Mono”), and finally the ratio
of these runtimes (column “Ratio”).
The algorithms were implemented in the BALM. The measurements were made
on a Windows XP computer with a 1.6 GHz CPU.
The results show that the partitioned method is more efficient (except for very
small examples) with efficiency increasing as the problem size increases. At some
point, the monolithic method can not complete (CNC) when the intermediate
automata become relatively large. Of course, even the partition method will run
out of steam at a certain point, but note that on one example it could handle over
140,000 states in the CSF.

7.5 Conclusions

In this chapter, a strategy was presented for solving language equations when the
fixed component and the specification are represented using multi-level determinis-
tic sequential networks. In such cases, a partitioned representation derived from the
original network can be used to perform all the operations needed to compute the
maximum solution. The operations required can be re-formulated in terms of image
computations, which can take advantage of the advances made in the efficiency
of these computations over the last decade. The new methods allow for faster
solution of larger problem instances. We emphasize that the techniques described,
rely heavily on the fact that both automata, F and S , are represented initially by
multi-level sequential networks and hence are prefix-closed, and that the desired
answer is also prefix-closed.
It was proved also, that not completing F in the algorithm leads to the same
answer. This has two important consequences. First, it is not necessary to form the
completion conditions before computing the product or its determinization. This
saves a lot of computing. Second, completion of F

can lead to a non-deterministic