A Novel Subcircuit Extraction Algorithm using Heuristic Dynamic Programming (HDP)

摘要

Subcircuit extraction is very important for VLSI testing, layout versus schematic (LVS) check, and circuit partition etc. In this paper, a novel subcircuit extraction algorithm -- SubHDP, based on the Heuristic Dynamic Programming is presented to extract subcircuits from the main circuit. Its correctness rate to find out all the subcircuits is up to 100%. When compared with the DECIDE algorithm, this algorithm can identify all the instances of subcircuits from the main circuit much faster if the main circuit has no more than 20,000 transistors. However, when the main circuit is larger than 20,000 transistors, the DECIDE algorithm becomes faster.