Computation of Sequential Flexibility in Netlists by Windowing - The Unknown Component Problem: Theory and Applications - page 175

Fig. 11.1 A window and its
abstracted environment,

o

S

Large
Netlist

Window 2

v

F

S

Window 1

u

i

the window, if possible. Then a second window is found which contains the first
window. The second window is chosen to include as much information about the
flexibility allowed by the environment without making the second window too large.
An example of choosing the second window would be to include all nodes in the
transitive fanout of up to

levels.
Even this might be too large, so some methods for trimming this second window
can be used. An efficient method for choosing the second window is proposed in
Sect. 11.2 . It is modeled after similar constructions for combinational networks.
Once the two windows have been chosen, the larger one is taken as the
specification and the smaller one as the unknown component. Note that the efficient
method of solution of Chap. 7 can be used for obtaining the largest FSM solution
for the smaller window, because both the specification and fixed part are given as
deterministic netlists. Suppose that the FSM solution has been obtained and that a
small implementation is chosen to replace the first window, then the overall behavior
of the larger window is unchanged according to the theory of language solving.
Hence, the overall behavior of the netlist is also unchanged.
We highlight that in all steps of windowing, from choosing the second window
of the unknown component to selecting a replacement from the largest solution
and then optimizing the resulting sequential logic, care must be observed not to
introduce combinational cycles. However we will not discuss the issue in this
chapter, and we leave it as a caveat in the background.
This idea is used for minimizing the original large netlist by iterating this proce-
dure and choosing another window for minimization, solving and reimplementing
the network inside the window. This is iterated over the entire network. By limiting
the sizes of the windows chosen, the computations can be made practical and
reasonably efficient.
In this chapter, we discuss the methods for choosing the two windows and the
implications that their sizes have on the solution process.
The general setting is shown in Fig. 11.1 ,where Window 1 denotes the sub-
network,

k levels and all nodes in the transitive fanin up to m

X , to be optimized and Window 2 denotes the specification, S ,tobeused

in the language solving instance. The sub-network S n X ( S without X )represents

the fixed part, F , of the language solving problem.