计算机工程与应用 ›› 2012, Vol. 48 ›› Issue (20): 70-74.

• 研发、设计、测试 • 上一篇    下一篇

基于压缩式改进迷宫算法的同构子电路提取

潘伟涛,邱智亮   

  1. 西安电子科技大学 综合业务网理论及关键技术国家重点实验室,西安 710071
  • 出版日期:2012-07-11 发布日期:2012-07-10

Algorithm based on compressed improved maze-algorithm for isomorphic subcircuit recognition

PAN Weitao, QIU Zhiliang   

  1. State Key Lab of Integrated Services Networks, Xidian University, Xi’an 710071, China
  • Online:2012-07-11 Published:2012-07-10

摘要: 提出了一种用于集成电路逆向工程的高性能子电路识别算法。在搜索匹配过程中,采用改进的迷宫算法对电路中有效节点进行遍历,解决了实际电路中出现的缓冲器问题;采用压缩式存储方法,大大降低了算法的空间复杂度,可支持超大规模的集成电路。该算法将最终的结果以通用的EDIF文件格式输出,实现与Cadence等主流EDA工具无缝衔接。该算法已应用于实际工程项目中,可显著提高分析整理集成电路的工作效率。

关键词: 同构, 子电路, 迷宫算法, 压缩, 标准单元

Abstract: A high performance subcircuit recognition algorithm which is used in integrated circuit reverse engineering is proposed. During the process of matching, an improved maze-algorithm is used to search all the valid nodes in circuits, which can neglect the buffers automatically. A more efficient compressed storage strategy is used to save the memory, therefore, very large scale integration can be done. The format of the finally result output file is EDIF, which supports to exchange the design data with famous EDA tools such as Cadence and so on seamlessly. The algorithm is used in engineering projects, which can improve the efficiency of integrated circuit reverse analysis largely.

Key words: isomorphic, subcircuit, maze-algorithm, compression, standard cell