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

11.3.2 Efficient Window Selection for Sequential Networks

The above presentation concerns computation of windows in combina-
tional networks. When the network is sequential, it may be considered as
combinational for the purpose of computing internal don't-cares. In this case,
combinational windowing can be applied, but the result of optimization will only
exploit combinational flexibility. To tap into sequential flexibility, we need to
consider sequential elements during optimization. Just as in the combinational case,
windowing is important in this case because it allows computations to be scalable.
We experimented with several schemes for sequential windowing, i.e., window-
ing that considers sequential elements. The main difficulty here is that some path
may be cyclic and need to be included in the window completely, instead of being
broken by introducing PI and PO pairs, which are used to represent sequential
elements in combinational synthesis.
Described below is the simplest form of sequential windowing used in several
applications. It is both easy to implement and gives good experimental results. This
windowing is based on partitioning registers of the network, and extracting the cone-
of-influence of one partition at a time, while replacing the outputs of registers of
other partitions by free variables, that is, additional PIs. We tried several register
partitioning algorithms and found that the following naive one works well in most
cases: divide registers into groups of fixed size in the order of their appearance in
the network, with possibly a fixed overlap between the groups.
For example, if we have eight registers .1;2;3;4;5;6;7;8/ , with partition size 3

and overlap 1, we have the following partitioning: .

The selection of partition size and overlap depends on the application. In particular,
when detecting and merging sequential equivalent nodes using a SAT-based induc-
tive prover, the partition size of several thousands led to acceptable runtime and
good experimental results [97].

.1; 2; 3/; .3; 4; 5/; .5; 6; 7/; .7; 8/

Problems

11.1. Consider the sequential circuit lion9.blif whose description in the blif
language is:

.model lion9.kiss2
.inputs v0 v1
.outputs v6.4
.latch

v6.0 v2 0

.latch v6.1 v3 0

.latch v6.2 v4 1

.latch v6.3 v5 0

.names [17] v6.4
01