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

from the given set. The distance- 0 nodes are the original nodes. The distance- .kC1/

nodes are found by collecting the fanins of the distance- k nodes not visited before.

The procedure CollectNodesTFO is similar.
Procedures CollectLeaves and CollectRoots take the set of the windows internal
nodes and determine the leaves and roots of this window. The leaves are the nodes
that do not belong to the given set but are fanins of at least one of the nodes in the
set. The roots are the nodes that belong to the given set and are also fanins of at least
one node not in the set. Note that some of the roots thus computed are not in the TFO
cone of the original node, for which the window is being computed, and therefore
can be dropped without violating the definition of the window and undermining the
usefulness of the window for logic synthesis operations dealing with the node.
We refer to the window constructed for a node by including

n TFI logic levels

and m TFO logic levels as an n m window.

Example 11.1. Figure 11.4 shows a 1 1 window for node N in a network. The

nodes labeled are in correspondence with the pseudo-code

in Fig. 11.3 . The windows roots (top) and leaves (bottom) are shaded. Note that
the nodes labeled by

I 1 , O 1 , S , L ,and R

P do not belong to the TFI and TFO of N , but represent

reconvergent paths in the vicinity of N . The left-most root and right-most root are

not in the TFO of N and can be dropped, as explained above.

Since implementing the first version of the windowing algorithm in [96], it was
applied in several projects. A major drawback was found to be non-robustness
when windowing is used for large designs containing nodes with more than 100
fanouts. The original algorithm involved topological traversals of the network from
the window PIs in order to find the window POs. Nodes with multiple fanouts, each
of which had to be visited, led to a substantial slow-down during this traversal. The
problem was aggravated by the fact that multiple-fanout nodes were involved in
many windows and, therefore, had to be traversed many times.
This led to the following modification. The original algorithm first detected the
window PIs, then the window POs. The current algorithm does the opposite: it
performs a shallow topological traversal to detect the window POs followed by
a deeper reverse-topological traversal from the POs to find the window PIs. The
topological traversal is performed with a fanout limit set to 10. The limit stops the
traversal at multiple-fanout nodes and declares them as window POs because they
are unlikely to yield any observability don't cares (due to many outgoing paths).
Another important improvement is that only those window POs are computed
that have reconvergence involving the pivot node and the window PIs. The POs
without reconvergence should not be included in the window because they do not
contribute don't cares.
Once the window for a node is constructed, it is considered as the network, for
the purpose of don't care computation or other logic optimizations. For this reason,
algorithms for logic optimization can be discussed in the context of a sufficiently
small network.