Article

Free access

An O(nlogm) algorithm for VLSI design rule checking

Authors:

C. R. Bonapace,

C.-Y. LoAuthors Info & Claims

DAC '89: Proceedings of the 26th ACM/IEEE Design Automation Conference

Pages 503 - 507

https://doi.org/10.1145/74382.74466

Published: 01 June 1989 Publication History

PDF eReader

Abstract

This paper describes a new variant of the segment tree approach for VLSI design rule checking. The best known algorithms to date for flat VLSI design rule checking require O(nlogn) expected time and O(√n) expected space, where n is the total number of edges on a mask layer of the chip. We present a new algorithm that can run in O(nlogm) expected time, where m is the maximum feature size on a particular mask layer. Since the maximum feature size must be bounded by the height of a chip, i.e. m ≤ O(√n), the new algorithm is adaptively more efficient than O(nlogn). For layers such as diffusion or contact windows where the maximum feature size is independent of chip size, i.e. m = O(1), the new algorithm runs in O(n) expected time, a definite improvement. The improved time efficiency is achieved without sacrificing O(√n) expected space complexity.

References

[1]

H.S. Baird, "Fast Algorithms for LSI artwoxk analysis," Design Automation and Fault Tolerant Computing 2, 179-209, 1978,

Google Scholar

[2]

S.C. Johnson, "Hierarchical Design Validation Based on Rectangles," Proceedings of the M.I.T. Conference on Advanced Research in VLSI, pp. 97-100, 1982.

Google Scholar

[3]

M.H. Arnold and J.K. Ousterhout, "Lyra: a new approach to geometric layout rule checking," Proceedings of the 19th Design Automation Conference, pp. 530-536, 1982.

Digital Library

Google Scholar

[4]

T.G. Szymanski and C.J. Van Wyk, "GOALIE: A Space-Efficient System for VL$I Artwork Analysis", Digest of Technical Papers ICCAD-84 pp. 278-280, November, 1984,

Google Scholar

[5]

C.R. Bonapace and C.-Y. Lo, "LARC2: A Space- Efficient Design Rule Checker," Digest of Technical Papers ICCAD-87, November, 1987.

Google Scholar

[6]

B.M. Chazelle, "Filtering search: A new approach to query answering," Proc. 24th IEEE Syrup. on Foundations of Computer Science, Tucson, AZ, 122-132 Nov. 1983.

Google Scholar

[7]

E. Edelsbrurmer, L.J. Guibas and J. Stolfi, "Optimal point location in a monotone subdivision," DEC/SRC research report 2, 1984, to appear in SIAM J. on Comp.

Google Scholar

[8]

I.L. Bentley and D. Wood, "An optimal worst case algorithm for reporting intersections of rectartgles," IEEE Transaction on Computers C-29(7), pp. 571- 577, 1980.

Digital Library

Google Scholar

[9]

F.P. Preparata and M.I. Shamos, "Computational geometry: an introduction," Springer-Verlag, 1985.

Digital Library

Google Scholar

Cited By

View all

Gatenby DFoo G(2013) Design for X (DFX): Key to Competitive, Profitable Products AT&T Technical Journal10.1002/j.1538-7305.1990.tb00332.x69:3(2-13)Online publication date: 29-Jul-2013
https://doi.org/10.1002/j.1538-7305.1990.tb00332.x
Bamji CAllen J(1994)GLOVE: a graph-based layout verifierProceedings of 7th International Conference on VLSI Design10.1109/ICVD.1994.282688(215-220)Online publication date: 1994
https://doi.org/10.1109/ICVD.1994.282688
Shiran Y(1991)Distributed Layout Verification Using Sequential Software and Standard Hardware1991, Proceedings. International Test Conference10.1109/TEST.1991.519768(1009)Online publication date: 1991
https://doi.org/10.1109/TEST.1991.519768
Show More Cited By

Index Terms

An O(nlogm) algorithm for VLSI design rule checking
1. Hardware
  1. Electronic design automation
    1. Physical design (EDA)
      1. Partitioning and floorplanning
  2. Very large scale integration design

Recommendations

An O ( n log m ) algorithm for VLSI design rule checking

The authors describe a new variant of the segment tree approach for VLSI design rule checking. The best known algorithms to date for flat VLSI design rule checking require O ( n log n ) expected time and O (ý n ) space, where n is the total number of ...
An optimal algorithm for checking regularity: (extended abstract)
SODA '02: Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms

We present a deterministic algorithm A that, in O(m²) time, verifies whether a given m by m bipartite graph G is regular, in the sense of Szemerédi [18]. In the case in which G is not regular enough, our algorithm outputs a witness to this irregularity. ...
High-Speed VLSI Multiplication Algorithm with a Redundant Binary Addition Tree

A high-speed VLSI multiplication algorithm internally using redundant binary representation is proposed. In n bit binary integer multiplication, n partial products are first generated and then added up pairwise by means of a binary tree of redundant ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

DAC '89: Proceedings of the 26th ACM/IEEE Design Automation Conference

June 1989

839 pages

ISBN:0897913108

DOI:10.1145/74382

Chairman:
Donald E. Thomas
Carnegie Mellon Univ., Pittsburgh, PA

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 June 1989

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

DAC89

Sponsor:

IEEE-CS\TCDA
SIGDA

DAC89: The 26th ACM/IEEE-CS Design Automation Conference

June 25 - 28, 1989

Nevada, Las Vegas, USA

Acceptance Rates

DAC '89 Paper Acceptance Rate 156 of 465 submissions, 34%;

Overall Acceptance Rate 1,770 of 5,499 submissions, 32%

Upcoming Conference

DAC '25

Sponsor:
sigda

62nd ACM/IEEE Design Automation Conference

June 22 - 26, 2025

San Francisco , CA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
388
Total Downloads

Downloads (Last 12 months)41
Downloads (Last 6 weeks)5

Reflects downloads up to 16 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Gatenby DFoo G(2013) Design for X (DFX): Key to Competitive, Profitable Products AT&T Technical Journal10.1002/j.1538-7305.1990.tb00332.x69:3(2-13)Online publication date: 29-Jul-2013
https://doi.org/10.1002/j.1538-7305.1990.tb00332.x
Bamji CAllen J(1994)GLOVE: a graph-based layout verifierProceedings of 7th International Conference on VLSI Design10.1109/ICVD.1994.282688(215-220)Online publication date: 1994
https://doi.org/10.1109/ICVD.1994.282688
Shiran Y(1991)Distributed Layout Verification Using Sequential Software and Standard Hardware1991, Proceedings. International Test Conference10.1109/TEST.1991.519768(1009)Online publication date: 1991
https://doi.org/10.1109/TEST.1991.519768
Shiran Y(1991)Parallel design verification using standard hardware and sequential software[1991] Proceedings the Fifth Israel Conference on Computer Systems and Software Engineering10.1109/ICCSSE.1991.151185(143-148)Online publication date: 1991
https://doi.org/10.1109/ICCSSE.1991.151185

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

An O ( n log m ) algorithm for VLSI design rule checking

An optimal algorithm for checking regularity: (extended abstract)

High-Speed VLSI Multiplication Algorithm with a Redundant Binary Addition Tree