基于子图同构的子电路提取算法

Subcircuit Extraction Algorithm Based on Subgraph Isomorphism

从门级到功能模块级的子电路提取问题在大规模集成电路计算机辅助设计领域有广泛地应用,提出了基于子图同构的方法来解决该问题。针对子电路的特征,选择辐射路匹配和赋标号算法之一作为搜索的主算法。尽管子图同构问题是NP完全问题,算法对实际的电路是快速的,满足工程需要。

Subcircuit extraction problem from gate level to function level arises in many contexts in VLSI computeraided design.From the viewpoint of subgraph isomorphism,we proposed a high performance algorithm to solve it.Based on the features of the subcircuit,radiate path matching or labeling algorithm may be chosen for searching.Although Subgraph Isomorphism problem is known to be NP-complete,our solution is very fast in practice for real circuits.