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

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

作　　者：李长青[1] 汪雪林[1] 彭思龙[1] 

机构地区：[1]中国科学院自动化研究所国家专用集成电路设计工程技术研究中心,北京100080

出　　处：《计算机辅助设计与图形学学报》2006年第9期1377-1382,共6页Journal of Computer-Aided Design & Computer Graphics

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

关 键 词：辐射路 集成电路反向分析 逻辑综合 子图同构 子电路提取 

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