二同构扩展数字集成电路规律性提取算法

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

针对目前集成电路具有高度的规律性的特点,提出了一种新的数字集成电路规律性结构提取算法,可自动对电路中一些重复出现的电路结构进行识别和提取.通过对两两相连的标准单元进行特征提取比较并产生二同构子电路,对出现频数较高的二同构子电路进行扩展产生电路结构模板,进而提取所有与该模板相似的电路结构.在算法运行过程中,通过不断地删除已经匹配的顶点,可加快程序运行的速度.该算法已应用于实际工程项目中,改变了传统的手动分析整理的局面,降低了大规模集成电路逆向分析中电路整理的难度,提高了工作效率.

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 ineluding 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.