小规模频繁子电路的规律性预提取算法  

Regularity Pre-extraction Algorithm for Small Scale Frequent Subcircuits

作　　者：潘伟涛[1] 郝跃[1] 谢元斌[1] 史江一[1] 

机构地区：[1]西安电子科技大学微电子学院宽禁带半导体材料与器件教育部重点实验室,西安710071

出　　处：《计算机辅助设计与图形学学报》2010年第2期226-233,共8页Journal of Computer-Aided Design & Computer Graphics

基　　金：国家自然科学基金(60506020);国家重大基础研究项目(61398)

摘　　要：针对数字IC规律性提取算法复杂度过高的问题,提出一种逐级对根节点进行分类的算法.通过对频繁边的直接扩展,实现了小规模频繁子电路的快速提取;利用门级电路中小规模频繁子电路与大规模频繁子电路间的结构依赖性,解决了候选子电路生成时根节点组合爆炸的问题.实验结果表明,该算法能够降低根节点的数量,使支持度高的候选子电路得到优先提取,并显著地减少了规律性提取的时间.To cope with the problem of high complexity in extraction of functional regularity in digital ICs, an algorithm capable of categorizing the root nodes gradually is proposed. By extending the frequent edges directly, the small frequent subcircuits can be extracted fast; and utilizing structure dependencies between small frequent subcircuits and big ones at gate level, the combination explosion problem of root nodes has been solved in the process of generating candidate subcircuits. Experimental results show that the proposed algorithm can reduce the number of root nodes effectively, extract the high frequency candidate subcircuits with high priority and reduce runtime of regularity extraction observably.

关 键 词：子电路同构 候选子电路 频繁子电路 规则性指数 

分 类 号：TP391.72[自动化与计算机技术—计算机应用技术]