A pattern matching algorithm for verification and analysis of very large IC layouts

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A pattern matching algorithm for verification and analysis of very large IC layouts

Full text

Pdf (922 KB)

Source

International Symposium on Physical Design archive
Proceedings of the 1998 international symposium on Physical design table of contents

Monterey, California, United States

Pages: 129 - 134

Year of Publication: 1998

ISBN:1-58113-021-X

Authors

Mariusz Niewczas	Dept. of Electrical and Computer Engineering, Carnegie Mellon University, 5000 Forbes Ave., Pittsburgh, PA and Dept. of Electronics, Warsaw University of Technology, Warsaw, Poland
Wojciech Maly	Dept. of Electrical and Computer Engineering, Carnegie Mellon University, 5000 Forbes Ave., Pittsburgh, PA
Andrzej Strojwas	Dept. of Electrical and Computer Engineering, Carnegie Mellon University, 5000 Forbes Ave., Pittsburgh, PA

Sponsors

IEEE-CS : Computer Society
IEEE-CAS : Circuits & Systems
SIGDA: ACM Special Interest Group on Design Automation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 32, Citation Count: 2

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/274535.274554 What is a DOI?

ABSTRACT

We propose a simple, isometry invariant pattern matching algorithm for an effective data reduction useful in layout-related data processing of very complex IC designs. The repeatable geometrical features and attributes are stored in a pattern database. Original pattern instance, or its geometrical attributes, may be quickly regenerated based both on the information stored within the pattern and position of the pattern instance. We also show preliminary results of analysis of the state-of-the-art ICs which suggest that the diversity of patterns does not significantly increase with the increase of chip size.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	T. Whitney, "A Hierarchical Design Analysis Front End", in Proc. of F'trst Int. Conf VLSI, Aug. 1981, pp. 217-225
	2	George S. Taylor , John K. Ousterhout, Magic's incremental design-rule checker, Proceedings of the 21st conference on Design automation, p.160-165, June 25-27, 1984, Albuquerque, New Mexico, United States
	3	D.M.H. Walker, C. Kellen, D. M. Svoboda and A. Strojwas, "The CDB/HCDB Semiconductor Wafer representation Server", IEEE Trans. on CAD, Vol CAD-12, No.2, pp.283- 295, Feb. 1993.
	4	P. K. Nag , W. Maly, Hierarchical extraction of critical area for shorts in very large ICs, Proceedings of the IEEE International Workshop on Defect and Fault Tolerance in VLSI Systems, p.19, November 13-15, 1995
	5	N. Hedenstiema and K. O. Jeppson, "The Halo Algorithm - An Algorithm for Hierarchical Design of Rule Checking of VLSI Circuits", IEEE Trans. on CAD, Vol. CAD-12, No. 2. pp 265- 272, Feb. 1993
	6	Mariusz Niewezas, Xiaolei Li, Andrzej Strojwas and Wojeieeh Maly, "Chip scale 3-D Topography Synthesis", SPIE Optical Microlithography Conference, Feb 1998.
	7	Neg-Chung Hu, Kuo-Kan Yu, Yung-Li Hsu, "Two-dimensional shape recognition using oriented-polar representation", Optical Engineering, Vol. 36, No. 10, Oct. 1997
	8	L. Davis, "Shape Matching Using Relaxation Techniques", IEEE Trans. on Pattern Analysis and Machine Intelligence, Vol. PAMI-1, No. 1, Jan. 1979
	9	T. Pavlidis, "Algorithms for Shape Analysis of Contours and Waveforms", IEEE Trans. on Pattern Analysis and Machine Intelligence, Vol. PAMI-2, No. 4, July 1980
	10	B. Bhanu and O. Faugeras, "Shape Matching of Two-Dimensional Objects", IEEE Trans. on Pattern Analysis and Machine Intelligence, Vol. PAMI-6, No. 2, March 1984
	11	S. Z. Li, "Matching: Invariant to Translations, Rotations and Scale Changes", Pattem Recognition, Vo}. 25, No. 6, pp. 583- 594 (1992)
	12	information about SiCat can be found at http://www.aiss.com
	13	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974

CITED BY 2

	Michael W. Beattie , Lawrence T. Pileggi, Modeling magnetic coupling for on-chip interconnect, Proceedings of the 38th conference on Design automation, p.335-340, June 2001, Las Vegas, Nevada, United States
	Andrew B. Kahng , Darko Kirovski , Stefanus Mantik , Miodrag Potkonjak , Jennifer L. Wong, Copy detection for intellectual property protection of VLSI designs, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.600-605, November 07-11, 1999, San Jose, California, United States