FROSTY: A Fast Hierarchy Extractor for Industrial CMOS Circuits

This paper presents FROSTY, a computer programfor automatically extracting the hierarchy of a large-scale digitalCMOS circuit from its transistor-level netlist description and alibrary of subcircuits. To handle the complexity of industrialcircuits, FROSTY combines traditional structural recognition andpattern matching methods into a two-step extraction process.First, gate structures based on channel-connected-components arerecognized from a circuit netlist and library subcircuits. Thenannotated graphs representing the connectivity and properties ofgate structures are constructed. Comparing to transistor-levelnetlists, these graphs are much smaller in size, moredistinguishable in structure, and are thus more suitable forlabeling based pattern matching. An efficient pattern matchingalgorithm is applied to extract the circuit hierarchy from thesecondensed circuit graphs. FROSTY has been demonstrated to beorders of magnitude faster than the best known extractionprogram SubGemini, capable of extracting the entire hierarchy ofindustrial designs with several hundred thousand transistors in afew minutes on a Sun workstation. Further FROSTY is scale withthe size of a circuit.