Graph-based Representations and Coupled Verification of VLSI Schematics and Layouts

From bibtex.

Abstract

Structural verification of VLSI schematics and layouts is formalized. Both schematics and layouts are modeled as graphs and structural correctness is tied to a rigorous set of graph composition rules which define how blocks of schematics and layouts may be composed. Novel, non-heuristic verification techniques which allow structural verification to be performed for a continuum of schematic and layout block sizes are introduced. Using one potent structural verification mechanism, these techniques provide a unified approach to schematic design style verification, layout design rule verification and schematic vs. layout comparison. The verification techniques are fast and can be performed incrementally as the schematics and layouts are created. For schematic design style verification the composition rules are captured by graph transformations akin to context free grammatical productions. The productions describe how a small set of module symbols may be composed. Using these productions a hierarchical parse tree that can demonstrate the correctness of the schematic is constructed. For layouts the composition rules are represented by graph templates. Design rule verification is achieved by covering the layout graph with these templates. Schematic vs. layout correspondence verification is achieved by allowing individual templates to span both schematics and layouts and simultaneously covering the schematic and layout with these templates.