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

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

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

潘伟涛;谢元斌;郝跃;史江一

(西安电子科技大学宽禁带半导体材料与器件教育部重点实验室，陕西西安 710071)

收稿日期:2008-06-11 修回日期:2008-10-29 出版日期:2009-06-20 发布日期:2009-07-04
基金资助:
国家自然科学基金资助(60506020);国家部委科技预研项目资助(51308010301)

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

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

(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

摘要/Abstract

摘要：

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

关键词: 子电路同构, 规律性, 子电路模板, 逻辑综合, 标准单元

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

中图分类号:

TP391.72

潘伟涛;谢元斌;郝跃;史江一. 二同构扩展数字集成电路规律性提取算法[J]. J4, 2009, 36(3): 452-462.

PAN Wei-tao;XIE Yuan-bin;HAO Yue;SHI Jiang-yi. Two-isomorphic extending algorithm for regularity extraction in digital integrated circuits[J]. J4, 2009, 36(3): 452-462.

参考文献

［1］Dobberpuhl D. Circuits and Technology for Digital's StrongARM and ALPHA Microprocessors ［C］//Proc Conf Adv Res in VLSI. Ann Arbor: IEEE, 1997: 2-11.
［2］Nardi A, Sangiovanni-Vincentelli A L. Logic Synthesis for Manufacturability ［J］. IEEE D＆T of Computers, 2004, 5(3):192-199.
［3］Kheterpal V, Rovner V. Design Methodology for IC Manufacturability Based on Regular Logic Bricks ［C］//Proc Design Automation Conf. Anaheim: IEEE, 2005: 353-358.
［4］Rosiello A P E, Ferrandi F, Pandini D, et al. A Hash-based Approach for Functional Regularity Extraction During Logic Synthesis ［C］//IEEE Computer Society Annual Symposium on VLSI. New York: IEEE, 2007: 92-97.
［5］Kutzschebauch T. Efficient Logic Optimization Using Regularity Extraction ［C］//Proc Intl Conf on Computer Design. Austin: IEEE, 2000: 487-493.
［6］Rao D S, Kurdahi F J. On Clustering for Maximal Regularity Extraction ［J］. IEEE Trans on Computer-Aided Design, 1993, 12(8): 1198-1208.
［7］Arikati S R, Varadarajan R. A Signature Based Approach to Regularity Extraction ［C］//Proceedings of IEEE International Conference on Computer-Aided Design. Washington: IEEE, 1997: 542-545.
［8］Nijssen R X T, Van Eijk C A J. Regular Layout Generation of Logically Optimized Datapaths ［C］//Proc Intl Symp on Physical Design. Berlin: Springer-Verlag, 1997: 42-47.
［9］Chowdhary A, Kale S. Extraction of Functional Regularity in Datapath Circuits ［J］. IEEE Trans on Computer-Aided Design, 1999, 18(9): 1279-1296.
［10］李长青, 汪雪林，彭思龙. 辐射路匹配: 从门级到功能模块级的子电路提取算法［J］. 计算机辅助设计与图形学学报, 2006, 18(9): 1377-1382.
Li Changqing, Wang Xuelin, Peng Silong. Radiate Path Matching: A Subcircuit Extraction Algorithm From Gate Level to Function Level ［J］. Journal of Computer-aided Design & Computer Graphics, 2006, 18(9): 1377-1382.
［11］Hansen M, Yalcin H, Hayes J P. Unveiling the ISCAS-85 Benchmarks: a Case Study in Reverse Engineering ［J］. IEEE Design ＆ Test of Computers,1999, 16(3): 72-80.
［12］Brglez F, Fujiwara H. A Neutral Netlist of 10 Combinational Benchmark Circuits ［C］//Proc IEEE Int'l Symp Circuits and Systems. New York: IEEE, 1985: 695-698.
［13］苏浩航, 张义门, 张玉明, 等. 一种大规模电源/地线网络快速压缩BiCGStab算法［J］. 西安电子科技大学学报, 2008, 35(3): 508-512.
Su Haohang, Zhang Yimen, Zhang Yuming, et al. Fast Method for the Large-scale Power and Ground Network Analysis Based on the Compressed BiCGStab Algorithm ［J］. Journal of Xidian University, 2008, 35(3): 508-512.
［14］Jenihhin M. ISCAS'89［OL］. ［2007-12-12］. http://www.pld.ttu.ee/~maksim/benchmarks/iscas89/.

[1]	邸志雄;史江义;马佩军;张译;袁莉;郝跃;许钊. 一种组合逻辑环转化方法[J]. J4, 2014, 41(1): 75-80.
[2]	陈平;杨刚;刘鑫. VLSI标准单元通道布线的研究[J]. J4, 1998, 25(6): 0-0.