An External Memory Circuit Validation Algorithm for Large VLSI Layouts

The circuit represented by a layout must be validated by comparing it to a schematic circuit to show that the functionality is same as intended. This done by testing for graph isomorphism between the layout and schematic circuit graphs. Circuits designed currently are so large that their corresponding data structures often exceed available main memory and thus, memory hierarchy issues like disk I/Os cannot be ignored. We present an I/O efficient procedure for testing graph isomorphism between circuit graphs. Our approach is based on the global partitioning and local matching phases along with deletion of matched vertices and we give an I/O efficient procedure for each of these phases