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

Regularity Pre-extraction Algorithm for Small Scale Frequent Subcircuits

针对数字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.