基于启发式链搜索的频繁子电路提取算法

Frequent subcircuits extraction algorithm based on heuristic chain search

针对数字集成电路规律性提取时由根节点选择产生的组合爆炸问题,提出了一种通过提取链状频繁子电路来降低根节点的算法。建立了顺序相关边权值模型,实现了小规模链状频繁子电路的快速提取。利用门级电路中链状模板与其他形状模板的结构依赖性,逐级删除非频繁根节点,避免了对小规模频繁子电路的重复提取,提高了规则性提取的效率。实验结果表明,该算法能够有效解决根节点组合爆炸问题,使支持度高的候选子电路得到优先提取,并显著减少了规律性提取的时间。

Aiming at the combination explosion problem induced by choosing root nodes in the extraction of functional regularity in digital ICs,an algorithm capable of reducing the number of root nodes by extracting the chain-like frequent subcircuits is proposed.By establishing sequence-dependent edge-weight model,the small chain-like frequent subcircuits can be extracted fast.Furthermore,to improve the efficiency of regularity extraction,the non-frequent root nodes can be deleted gradually by utilizing structure dependencies between small chain-like frequent subcircuits and other structure templates at gate level,which avoids the repetitive extraction of small frequent subcircuits.Experimental results show that the proposed algorithm can solve the combination explosion problem effectively,extract the high frequency candidate subcircuits with high priority and reduce runtime of regularity extraction observably.