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

Chapter 11
Computation of Sequential Flexibility in Netlists
by Windowing

11.1 Complete Sequential Flexibility in a Window

A challenging problem is to take a larger FSM given as a netlist, e.g., in BLIF-MV
or BLIF format, and then focus on a window, partitioning the netlist into two parts -
all nodes inside the window and all nodes outside the window. The nodes inside the
window can be viewed as a separate FSM and the nodes outside the window as its
fixed environment. The nodes on the boundary of the window are sometimes called
a cut - they separate the inside from the outside. The nodes which fanout from the
inside to the outside are the POs of the window and the nodes which fanout from
the outside to the inside are the PIs of the window FSM. A similar situation occurs
when the initial netlist is given as a hierarchy of FSMs. In this case the boundaries
between the FSMs are given by the hierarchy structure.
The netlist inside the window will be considered as the unknown FSM compo-
nent; the remaining nodes will constitute the fixed part. The specification will be
the entire netlist. The largest FSM solution of the unknown component problem is
sometimes referred to as the complete sequential flexibility (CSF) of the window. It
contains all deterministic FSMs, which can be placed in the window and connected
to the fixed part such that the overall composed behavior is the same as the original
netlist. Note that unlike some problems, this application comes with a particular
known solution, which is the original netlist in the window. The challenge of this
application is to come up with a replacement netlist which is better, in some sense.
Even though the particular known solution must be contained in the largest FSM
solution, it is surprisingly difficult in many cases to find a sub-machine that is
equal or better than the original known solution. One reason is that the largest FSM
solution is usually a relatively very large machine and has so much behavior that is
it hard to find a small sub-solution.
In practical applications, the original netlist is too large, with too many latches for
the techniques in this topic to be applied. To overcome this, a typical fix is to use a
two-window approach, where the first step is to find a sub-netlist which is the target
of resynthesis, in order to obtain some improvement over the original netlist inside