Title :
A Fast and Practical Algorithm for Absolute Dominators Searching
Author :
Hu, Xiaojing ; Song, Zhengxiang ; Wang, Jianhua ; Geng, Yingsan ; Shen, Wang
Author_Institution :
State Key Lab. of Electr. Insulation & Power Equip., Xi´´an Jiaotong Univ., Xi´´an
Abstract :
Absolute dominator search is an effective topological analysis method to improve performance of computer-aided design (CAD) and automatic test pattern generation (ATPG). In this paper, we present a new algorithm for searching absolute dominators of multiple- output circuits to solve inefficient and complex computing in tradition algorithm. Compare with the tradition algorithm, the new algorithm analyzes the relations between different fanout nodes, and identifies absolute dominator for every fanout node in circuit, thus, the overall dominator graph is constructed without any changes for original circuit directly. The experimental results based on ISCAS85 and ITC99 benchmarks show a signification improvement in runtime, and it can meet the requirement of modern design and test for VLSI.
Keywords :
VLSI; automatic test pattern generation; circuit CAD; logic testing; ISCAS85 benchmark; ITC99 benchmark; VLSI; absolute dominators searching; automatic test pattern generation; computer-aided design; fanout nodes; Algorithm design and analysis; Automatic test pattern generation; Circuit faults; Circuit testing; Design automation; Logic circuits; Partitioning algorithms; Performance analysis; Very large scale integration; Wire;
Conference_Titel :
Testing and Diagnosis, 2009. ICTD 2009. IEEE Circuits and Systems International Conference on
Conference_Location :
Chengdu
Print_ISBN :
978-1-4244-2587-7
DOI :
10.1109/CAS-ICTD.2009.4960741
