一种数字集成电路链状频繁子电路提取算法

计算物理 ›› 2011, Vol. 28 ›› Issue (1): 138-144.

一种数字集成电路链状频繁子电路提取算法

潘伟涛¹, 谢元斌², 郝跃²

1. 西安电子科技大学ISN国家重点实验室, 陕西西安 7l007l;
2. 西安电子科技大学微电子学院宽禁带半导体材料与器件教育部重点实验室, 陕西西安 710071

收稿日期:2009-07-10 修回日期:2010-01-20 出版日期:2011-01-25 发布日期:2011-01-25
作者简介:潘伟涛(198l-),male,Luohe,Henan,Ph.D.,Major in IC design.
基金资助:
Supported by major project of Chinese national programs for fundamental research(973)(Grant No.61398)

An Algorithm for Chain-like Frequent Subcircuits Extraction in Digital Integrated Circuits

PAN Weitao¹, XIE Yuanbin², HAO Yue²

1. Stake Key Laboratory of Integrated Services Networks, Xidian University, Xi'an 710071, China;
2. Key Laboratory of Wide Band-gap Semiconductor Materials and Devices of Ministry of Education, School of Microelectronics, Xidian University, Xi'an 710071, China

Received:2009-07-10 Revised:2010-01-20 Online:2011-01-25 Published:2011-01-25
Supported by:
Supported by major project of Chinese national programs for fundamental research(973)(Grant No.61398)

摘要/Abstract

摘要： 基于数据挖掘思想,提出一种链状结构模板的规律性提取算法,解决集成电路规律性提取算法复杂度过高的问题.通过对边权值进行编码,将复杂子电路的同构搜索转化为边权值序列的匹配问题.模板扩展过程利用剪枝策略删除非频繁子电路,提高了规律性提取效率.将模板的产生与子电路的同构搜索过程合并,简化规律性提取流程.解决大规模集成电路中规则性提取复杂度过高的问题.结果表明,算法比SPOG与TREE算法更能充分提取电路的规律性,得到较好的电路覆盖.

关键词: 规律性提取, 频繁子电路, 数据挖掘, 规则性系数

Abstract: To reduce high complexity in extraction of functional regularity in digital ICs,a template called CHAIN generation algorithm is proposed based on data mining.Weights of edges are encoded,and a complex subcircuit isomorphism problem is solved by comparing edge weight sequences of the subcircuit.To reduce complexity and accelerate the algorithm,a pruning strategy is introduced into expending of templates to delete non-frequent subcircuits gradually.By merging template generation process and subcircuit isomorphism searching process,the regularity extraction flow is simplified.Experiments show that this CHAIN template algorithm is more effective.It obtains better circuit covering result than SPOG and TREE methods.

Key words: regularity extraction, frequent subcircuits, data mining, regularity index

中图分类号:

TP391.72

潘伟涛, 谢元斌, 郝跃. 一种数字集成电路链状频繁子电路提取算法[J]. 计算物理, 2011, 28(1): 138-144.

PAN Weitao, XIE Yuanbin, HAO Yue. An Algorithm for Chain-like Frequent Subcircuits Extraction in Digital Integrated Circuits[J]. CHINESE JOURNAL OF COMPUTATIONAL PHYSICS, 2011, 28(1): 138-144.