CAJ | 학술논문

基于数据挖掘思想,提出一种链状结构模板的规律性提取算法,解决集成电路规律性提取算法复杂度过高的问题.通过对边权值进行编码,将复杂子电路的同构搜索转化为边权值序列的匹配问题.模板扩展过程利用剪枝策略删除非频繁子电路,提高了规律性提取效率.将模板的产生与子电路的同构搜索过程合并,简化规律性提取流程.解决大规模集成电路中规则性提取复杂度过高的问题.结果表明,算法比SPOG与TREE算法更能充分提取电路的规律性,得到较好的电路覆盖.
기우수거알굴사상,제출일충련상결구모판적규률성제취산법,해결집성전로규률성제취산법복잡도과고적문제.통과대변권치진행편마,장복잡자전로적동구수색전화위변권치서렬적필배문제.모판확전과정이용전지책략산제비빈번자전로,제고료규률성제취효솔.장모판적산생여자전로적동구수색과정합병,간화규률성제취류정.해결대규모집성전로중규칙성제취복잡도과고적문제.결과표명,산법비SPOG여TREE산법경능충분제취전로적규률성,득도교호적전로복개.
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.