J4 ›› 2009, Vol. 36 ›› Issue (3): 452-462.

• Original Articles • Previous Articles     Next Articles

Two-isomorphic extending algorithm for regularity extraction in digital integrated circuits

PAN Wei-tao;XIE Yuan-bin;HAO Yue;SHI Jiang-yi   

  1. (Ministry of Education Key Lab. of Wide Band-Gap Semiconductor Materials and Devices, Xidian Univ., Xi'an  710071, China)
  • Received:2008-06-11 Revised:2008-10-29 Online:2009-06-20 Published:2009-07-04
  • Contact: PAN Wei-tao E-mail:wtpan@mail.xidian.edu.cn

Abstract:

To extract the regularity in digital integrated circuits, a novel algorithm is proposed. It can automatically identify and extract the subcircuit which appears frequently. By extracting and analyzing the properties of all two connected standard cells in the circuits, a series of templates including two standard cells will be obtained. The template with a high frequency will be extended so that it becomes longer than two, and then the instances of all longer templates will be explored using the proposed algorithm.To reduce the complexity and accelerate the algorithm, the matched vertexes will be deleted gradually from the search space. This algorithm has been implemented successfully in industrial projects, and has replaced the traditional manual analysis at the gate level. Furthermore, the complexity of the reverse analysis for VLSI is reduced, and the work efficiency can also be raised distinctly.

Key words: subcircuit isomorphic, regularity, subcircuit template, logic synthesis, standard cell

CLC Number: 

  • TP391.72