Computation and Application of Absolute Dominators in Industrial Designs

Despite the recent advances in ATPG technology computing test patterns for state-of-the-art industrial designs can demand an enormous amount of computation time. Numerous structural techniques were presented to reduce the search space and hence the runtime of state-of-the-art ATPG tools. Absolute dominators introduced by Kirkland and Mercer proved to be useful for finding mandatory observation nodes in a combinational circuit. A mandatory observation node denotes a gate which must be visited in order to propagate a fault to at least one primary output. Unfortunately their algorithm to compute absolute dominators does not scale well on large industrial designs. In this paper we propose a new algorithm to find absolute dominators in circuit graphs. The experimental results show a significant performance improvement with respect to runtime and memory consumption. The achieved speedup of three orders of magnitude on several designs enables the computation of absolute dominators in large industrial circuits in less than a second.