Article

Free access

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

Authors:

Mariusz Niewczas,

Wojciech Maly,

Andrzej StrojwasAuthors Info & Claims

ISPD '98: Proceedings of the 1998 international symposium on Physical design

Pages 129 - 134

https://doi.org/10.1145/274535.274554

Published: 01 April 1998 Publication History

PDF eReader

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

[1]

T. Whitney, "A Hierarchical Design Analysis Front End", in Proc. of F'trst Int. Conf VLSI, Aug. 1981, pp. 217-225

Google Scholar

[2]

G. S. Taylor and J. K. Ousterhout, "Magies's Incremental Design Rule Checker", Proe. of 21stACM/IEEE Design Automation Conf., pp. 160-165, 1984.

Digital Library

Google Scholar

[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.

Digital Library

Google Scholar

[4]

P. IC Nag and W. Maly, "Hierarchical Extraction of Critical Area for Shorts in Very Large ICs", IF_, Intl. Workshop on Defect and Fault Tolerance in VLSI Systems, pp. 19-27, Nov 1995

Digital Library

Google Scholar

[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

Google Scholar

[6]

Mariusz Niewezas, Xiaolei Li, Andrzej Strojwas and Wojeieeh Maly, "Chip scale 3-D Topography Synthesis", SPIE Optical Microlithography Conference, Feb 1998.

Google Scholar

[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

Google Scholar

[8]

L. Davis, "Shape Matching Using Relaxation Techniques", IEEE Trans. on Pattern Analysis and Machine Intelligence, Vol. PAMI-1, No. 1, Jan. 1979

Digital Library

Google Scholar

[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

Digital Library

Google Scholar

[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

Digital Library

Google Scholar

[11]

S. Z. Li, "Matching: Invariant to Translations, Rotations and Scale Changes", Pattem Recognition, Vo}. 25, No. 6, pp. 583- 594 (1992)

Crossref

Google Scholar

[12]

information about SiCat can be found at http://www.aiss.com

Google Scholar

[13]

A. Aho, J. Hopcroft and J. Ulman, "The design and Analysis of Computer Algorithms", Addison-Weseley, 1974

Digital Library

Google Scholar

Cited By

View all

(2016)A fast search and classification method of isomorphic polygons in LSI design data using geometric invariant feature valueInternational Journal of Space-Based and Situated Computing10.1504/IJSSC.2016.0827606:4(199-208)Online publication date: 1-Jan-2016
https://dl.acm.org/doi/10.1504/IJSSC.2016.082760
Shoji SKoyama A(2016)A Fast Classification Method of Isomorphic Polygons in Design Data of Large Scale Integrated Circuit2016 10th International Conference on Complex, Intelligent, and Software Intensive Systems (CISIS)10.1109/CISIS.2016.65(204-209)Online publication date: Jul-2016
https://doi.org/10.1109/CISIS.2016.65
Gabrys AGreig WWest ALindorfer PFrench WMondal SPatra DGoswami KSural SCrandle T(2009)Integrated Procedure Automating Test Chip Layout, Place and Route, and Test Plan Development for Efficient Parametric Device and Process DesignIEEE Transactions on Semiconductor Manufacturing10.1109/TSM.2008.201074122:1(110-118)Online publication date: Feb-2009
https://doi.org/10.1109/TSM.2008.2010741
Show More Cited By

Index Terms

A pattern matching algorithm for verification and analysis of very large IC layouts
1. Hardware
2. Theory of computation
  1. Design and analysis of algorithms
    1. Data structures design and analysis
      1. Pattern matching
  2. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

Inexact pattern matching using genetic algorithm
GECCO '05: Proceedings of the 7th annual conference on Genetic and evolutionary computation

A Genetic Algorithm for graphical pattern matching based on angle matching had been proposed. It has proven quite effective in matching simple patterns. However, the algorithm needs some modifications to enhance its accuracy on pattern matching when ...
Approximate pattern matching with gap constraints

Pattern matching is a key issue in sequential pattern mining. Many researchers now focus on pattern matching with gap constraints. However, most of these studies involve exact pattern matching problems, a special case of approximate pattern matching and ...
Pattern Matching in Hypertext

The importance of hypertext has been steadily growing over the past decade. The Internet and other information systems use hypertext format, with data organized associatively rather than sequentially or relationally. A myriad of textual problems have ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ISPD '98: Proceedings of the 1998 international symposium on Physical design

April 1998

220 pages

ISBN:158113021X

DOI:10.1145/274535

Chairman:
M. Sarrafzadeh
Northwestern Univ., Evanston, IL

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 April 1998

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

ISPD98

Sponsor:

SIGDA
IEEE-CAS
IEEE-CS

ISPD98: International Symposium on Physical Design

April 6 - 8, 1998

California, Monterey, USA

Acceptance Rates

Overall Acceptance Rate 62 of 172 submissions, 36%

Upcoming Conference

ISPD '25

Sponsor:
sigda

International Symposium on Physical Design

March 16 - 19, 2025

Austin , TX , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
633
Total Downloads

Downloads (Last 12 months)60
Downloads (Last 6 weeks)12

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

(2016)A fast search and classification method of isomorphic polygons in LSI design data using geometric invariant feature valueInternational Journal of Space-Based and Situated Computing10.1504/IJSSC.2016.0827606:4(199-208)Online publication date: 1-Jan-2016
https://dl.acm.org/doi/10.1504/IJSSC.2016.082760
Shoji SKoyama A(2016)A Fast Classification Method of Isomorphic Polygons in Design Data of Large Scale Integrated Circuit2016 10th International Conference on Complex, Intelligent, and Software Intensive Systems (CISIS)10.1109/CISIS.2016.65(204-209)Online publication date: Jul-2016
https://doi.org/10.1109/CISIS.2016.65
Gabrys AGreig WWest ALindorfer PFrench WMondal SPatra DGoswami KSural SCrandle T(2009)Integrated Procedure Automating Test Chip Layout, Place and Route, and Test Plan Development for Efficient Parametric Device and Process DesignIEEE Transactions on Semiconductor Manufacturing10.1109/TSM.2008.201074122:1(110-118)Online publication date: Feb-2009
https://doi.org/10.1109/TSM.2008.2010741
West AMondal SPatra DGoswami KSural S(2008)A novel high speed automatic layout system to place and route test structures for parametric test capability2008 IEEE International Conference on Microelectronic Test Structures10.1109/ICMTS.2008.4509316(71-75)Online publication date: Mar-2008
https://doi.org/10.1109/ICMTS.2008.4509316
Niewczas MMaly WStrojwas A(2006)An algorithm for determining repetitive patterns in very large IC layoutsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/43.75293218:4(494-501)Online publication date: 1-Nov-2006
https://dl.acm.org/doi/10.1109/43.752932
Beattie MPileggi L(2002)On-chip induction modelingIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/TVLSI.2003.80868210:6(712-729)Online publication date: 1-Dec-2002
https://dl.acm.org/doi/10.1109/TVLSI.2003.808682
Beattie MPileggi LRabaey J(2001)Modeling magnetic coupling for on-chip interconnectProceedings of the 38th annual Design Automation Conference10.1145/378239.378504(335-340)Online publication date: 22-Jun-2001
https://dl.acm.org/doi/10.1145/378239.378504
Kahng AKirovski DMantik SPotkonjak MWong JWhite JSentovich E(1999)Copy detection for intellectual property protection of VLSI designsProceedings of the 1999 IEEE/ACM international conference on Computer-aided design10.5555/339492.340087(600-605)Online publication date: 7-Nov-1999
https://dl.acm.org/doi/10.5555/339492.340087
Kahng AKirovski DMantik SPotkonjak MWong J(1999)Copy detection for intellectual property protection of VLSI designs1999 IEEE/ACM International Conference on Computer-Aided Design. Digest of Technical Papers (Cat. No.99CH37051)10.1109/ICCAD.1999.810718(600-604)Online publication date: 1999
https://doi.org/10.1109/ICCAD.1999.810718

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Inexact pattern matching using genetic algorithm

Approximate pattern matching with gap constraints

Pattern Matching in Hypertext