FROSTY: A program for fast extraction of high-level structural representation from circuit description for industrial CMOS circuits

This paper presents FROSTY, a computer program for automatically extracting the high-level structural representation of a large-scale digital CMOS circuit from its transistor-level netlist and a library of subcircuit descriptions. 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, logic structures based on channel-connected-components are recognized from a circuit netlist and from all library subcircuits, and are condensed into “macro devices” or called logic gates. This leads to hybrid netlists that contain the recognized logic gates and remaining transistors. Then annotated graphs representing the connectivity and properties of logic gates and remaining transistors are constructed. Compared to transistor-level netlists, these hybrid 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 then applied to extract the high-level structural representation from these condensed circuit graphs. FROSTY has demonstrated to be orders of magnitude faster than the pattern matching-based extraction program SubGemini, and can extract entire industrial designs with several hundreds of thousands of transistors in a few minutes on a modern Sun workstation. Furthermore, the FROSTY algorithm scales well with the size of a circuit.