External memory layout vs. schematic

ABSTRACT

The circuit represented by a VLSI layout must be verified by checking it against the schematic circuit as an important part of the functional verification step. This involves two central problems of matching the circuit graphs with each other (graph isomorphism) and extracting a higher level of circuit from a given level by finding subcircuits in the circuit graph (subgraph isomorphism). Modern day VLSI layouts contain millions of devices. Hence the memory requirements of the data structures required by tools for verifying them become huge and can easily exceed the amount of internal memory available on a computer. In such a scenario, a program not aware of the memory hierarchy performs badly because of its unorganized input/output operations (I/Os) as the speed of a disk access is about a million times slower than accessing a main memory location. In this article, we present I/O-efficient algorithms for the graph isomorphism and subgraph isomorphism problems in the context of verification of VLSI layouts. Experimental results show the need and utility of I/O-efficient algorithms for handling problems with large memory requirements.

REFERENCES

• 1: Magdy S. Abadir , Jack Ferguson, An improved layout verification algorithm (LAVA), Proceedings of the conference on European design automation, March 12-15, 1990, Glasgow, Scotland
• 2: Alok Aggarwal , Jeffrey,S. Vitter, The input/output complexity of sorting and related problems, Communications of the ACM, v.31 n.9, p.1116-1127, Sept. 1988 [doi>10.1145/48529.48535]
• 3: Deepak Ajwani , Roman Dementiev , Ulrich Meyer, A computational study of external-memory BFS algorithms, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.601-610, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109623]
• 4: Aloul, F. A., Ramani, A., Markov, I., and Sakallah, K. 2003. Solving difficult instances of Boolean satisfiability in the presence of symmetry. IEEE Trans. Comput. Aid. Des. Integr. Circ. Syst. 22 9, 1117--1137.
• 5: Barke, E. 1984. A network comparison algorithm for layout verification of integrated circuits. IEEE Trans. Comput.-Aid. Des. Integr. Circuits and Syst. 3 2, 135--141.
• 6: Michael Boehner, LOGEX—an automatic logic extractor form transistor to gate level for CMOS technology, Proceedings of the 25th ACM/IEEE conference on Design automation, p.517-522, June 12-15, 1988, Atlantic City, New Jersey, United States
• 7: Thomas S Chanak, Netlist Processing for Custom VLSI via Pattern Matching, Stanford University, Stanford, CA, 1995
• 8: Yi-Jen Chiang , Michael T. Goodrich , Edward F. Grove , Roberto Tamassia , Darren Erik Vengroff , Jeffrey Scott Vitter, External-memory graph algorithms, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.139-149, January 22-24, 1995, San Francisco, California, United States
• 9: Corneil, D. and Kirkpatrick, D. 1980. A theoretical analysis of various heuristics for the graph isomorphism problem. SIAM J. Comput. 9, 281--297.
• 10: Ebeling, C. 1988. GeminiII: A second generation layout validation tool. In Proceedings of the International Conference on Computer-Aided Design (ICCAD'88). IEEE, 322--325.
• 11: Yokesh Kumar , Prosenjit Gupta, An External Memory Circuit Validation Algorithm for Large VLSI Layouts, Proceedings of the IEEE Computer Society Annual Symposium on VLSI, p.510-511, March 09-11, 2007 [doi>10.1109/ISVLSI.2007.24]
• 12: An Efficient External-Memory Implementation of Region Query with Application to Area Routing, Proceedings of the 2002 IEEE International Conference on Computer Design: VLSI in Computers and Processors (ICCD'02), p.36, September 16-18, 2002
• 13: F. Luellau , T. Hoepken , E. Barke, A technology independent block extraction algorithm, Proceedings of the 21st conference on Design automation, p.610-615, June 25-27, 1984, Albuquerque, New Mexico, United States
• 14: Bruno T. Messmer , Horst Bunke, Efficient Subgraph Isomorphism Detection: A Decomposition Approach, IEEE Transactions on Knowledge and Data Engineering, v.12 n.2, p.307-323, March 2000 [doi>10.1109/69.842269]
• 15: Kameshwar Munagala , Abhiram Ranade, I/O-complexity of graph algorithms, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.687-694, January 17-19, 1999, Baltimore, Maryland, United States
• 16: Miles Ohlrich , Carl Ebeling , Eka Ginting , Lisa Sather, SubGemini: identifying subcircuits using a fast subgraph isomorphism algorithm, Proceedings of the 30th international conference on Design automation, p.31-37, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164556]
• 17: Pelz, G. and Roettcher, U. 1994. Pattern matching and refinement hybrid approach to circuit comparison. IEEE Trans. Comput.-Aid. Des. Integr. Circ. Syst. 13 2, 264--276.
• 18: Read, R. C. and Corneil, D. G. 1977. The graph isomorphism disease. J. Graph Theor. 1 4, 339--363.
• 19: Rubanov, N. 2003. Subislands: the probabilistic match assignment algorithm for subcircuit recognition. IEEE Trans. Comput.-Aid. Des. Integr. Circ. Syst. 22 1, 26--38.
• 20: Sharathkumar, R., Maheshwari, P., and Gupta, P. 2006. A practical algorithm for connectivity extraction for very large VLSI layouts. In Proceedings of 49th IEEE International Midwest Symposium on Circuits and Systems (MWSCAS'06). IEEE, 491--495.
• 21: Sharathkumar, R., Vinaykumar, M. T. C., Maheshwari, P., and Gupta, P. 2005. Efficient external memory segment intersection for processing very large VLSI layouts. In Proceedings of 48th IEEE International Midwest Symposium on Circuits and Systems (MWSCAS'05). IEEE, 740--743.
• 22: J. D. Tygar , Ron Ellickson, Efficient netlist comparison using hierarchy and randomization, Proceedings of the 22nd ACM/IEEE conference on Design automation, p.702-708, June 1985, Las Vegas, Nevada, United States [doi>10.1145/317825.317966]
• 23: J. R. Ullmann, An Algorithm for Subgraph Isomorphism, Journal of the ACM (JACM), v.23 n.1, p.31-42, Jan. 1976 [doi>10.1145/321921.321925]
• 24: Jeffrey Scott Vitter, External memory algorithms and data structures: dealing with massive data, ACM Computing Surveys (CSUR), v.33 n.2, p.209-271, June 2001 [doi>10.1145/384192.384193]
• 25: Lei Yang , C.-J. Richard Shi, FROSTY: A Fast Hierarchy Extractor for Industrial CMOS Circuits, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.741, November 09-13, 2003 [doi>10.1109/ICCAD.2003.74]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Verification

General Terms:
Algorithms, Verification

Keywords:
Graph, design automation, external memory algorithms, subgraph isomorphism, verification of layouts