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

( nodeset, nodeset ) Window ( node N ,int nFanins ,int nFanouts ) f

nodeset I 1 = CollectNodesTFI ( fN g , nFanins );

nodeset O 1 = CollectNodesTFO ( fN g , nFanouts );

nodeset I 2 = CollectNodesTFI ( O 1 , nFanins + nFanouts );

nodeset O 2 = CollectNodesTFO ( I 1 , nFanins + nFanouts );

nodeset S = I 2 \ O 2 ;

nodeset L = CollectLeaves ( S );

nodeset R = CollectRoots ( S );

return ( L , R );

g

Fig. 11.3 Computation of a window for a node

Fig. 11.4 Example of the 1 1 window of node N

Definition 11.3.2. Given two subsets in a leaf/root relation, its window is the subset
of nodes of the network containing the root set together with all nodes on paths
between the leaf set and the root set. The nodes in the leaf set are not included in
the window.

Definition 11.3.3. A path connecting a pair of nodes is distance- k if it spans

exactly k edges between the pair. Two nodes are distance- k from each other if

the shortest path between them is distance- k .

The pseudo-code in Fig. 11.3 and the example in Fig. 11.4 describe the flow of a
window construction algorithm. Procedure Window takes a node and two integers
defining the number of logic levels on the fanin/fanout sides of the node to be
included in the window. It returns the leaf set and the root set of the window.
The procedure CollectNodesTFI takes a set

S m 0

of nodes and an integer ,

m

and returns a set of nodes on the fanin side that are distance- or less from the

S m

nodes in . An efficient implementation of this procedure for small (for most

m 10 k 0 k m

applications, ) iterates through the nodes that are distance- ( )