辐射路匹配:从门级到功能模块级的子电路提取算法

Radiate Path Matching:A Subcircuit Extraction Algorithm From Gate Level to Function Level

提出一种基于子图同构的高性能辐射路匹配算法,以满足反向分析中逻辑综合的需要.通过单个顶点的相似度特征,将子图同构问题转化为顶点之间的匹配问题.在算法运行过程中,通过不断地删除搜索空间中的非匹配顶点,大大地降低了算法的时空复杂度.理论分析和实验结果表明,该算法的时空复杂度与目标电路的逻辑门数和功能模块电路的逻辑门数均为线性关系.

A high performance radiate path matching algorithm is proposed for logic synthesis of integrated circuit reverse analysis. The algorithm transforms the subgraph isomorphism problem into a matching problem between vertexes through the introduction of similarity features for every vertex. The dismatched vertexes are deleted gradually from the searching space, therefore the complexity of the algorithm is reduced significantly. Theoretical analysis and experimental results show that both the time and space complexity of our algorithm are only linearly dependent on the number of gates of the object circuit and the function module.