FROSTY: A Fast Hierarchy Extractor for Industrial CMOS Circuits
Lei Yang, Changyou Shi · 2003
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 from 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 FROSTY is scalable with the size of a circuit.