Dominators and the Cutting Algorithm
Original Publication Date: 1985-Aug-01
Included in the Prior Art Database: 2005-Feb-19
The cutting algorithm gives a lower and upper bound for the probability of a signal equal to 1. This is useful for self-test, design verification, and delta-I analysis. Dominators are used herein to partition the logic graph so that tighter bounds are achieved. Let p be a primary input for which to find a dominator (dom) d. Let q be an output for which there are r paths from p to q. Note d is a dominator for p if all r paths from p to q pass through d. In general there may be many dominators for an input p. Let dom (p) be this set. For each primary input compute the dominator set. All dominator sets must intersect in at least one node - the output node q. Let the union of all dominator sets be the set of nodes u. For each node in u, traceback to the primary inputs and find which inputs are in the cone of logic.