|
UWEETR-2003-0011 Author(s): Keywords: Abstract This paper presents FROSTY, a computer program for automatically extracting the hierarchy of a large-scale digital CMOS circuit from its transistor-level netlist and a library of subcircuits. To handle the complexity and diversity of industrial circuits, FROSTY combines traditional structural recognition and pattern matching methods into a two-step extraction process. First, gate structures based on channel-connected-components are recognized from a circuit netlist and all library subcircuits. Then annotated graphs representing the connectivity and properties of gate structures are constructed. Comparing to transistor-level netlists, these graphs are much smaller in size, more distinguishable in structure, and are thus more suitable for labeling based pattern matching. An efficient pattern matching algorithm is applied to extract the circuit hierarchy from these condensed circuit graphs. FROSTY has been demonstrated to be orders of magnitude faster than pattern-matching based extraction program SubGemini, and can extract the entire hierarchy of industrial designs with several hundreds of thousands of transistors in a few minutes on a modern Sun workstation. Furthermore FROSY is scalable with the size of a circuit. |