Space-Efficient Algorithms for Computational Geometry.
Abstract
For the VLSI design to be reliably produced as a working chip, various features on the chip must be separated by minimum distances to ensure the proper operation of transistors and interconnections. The design rule checker program verifies that these and other geometric constraints are satisified and signals an error if it finds two features that violate the design rules. For a chip composed of millions of rectangles, design rule checking is a time-consuming process which cannot be done entirely within the primary memory of many computers. This thesis presents an efficient algorithm for finding the connected components of rectangles in the plane using a machine model which incorporates the secondary disk memory where the VLSI design is stored. By running this algorithm simultaneously on each layer of a VLSI chip design, a design rule checker can determine which features of a chip design are electrically equivalent, i.e., are effectively part of the same wire. The determination of electrical equivalence allows the design rule checker to avoid reporting the many aliasing errors which occur when two electrically equivalent features are mistaken for electrically distinct features. For example, two wires might be too close together, but if they are actually the same wire, it does not matter.
Document Details
- Document Type
- Technical Report
- Publication Date
- Oct 01, 1985
- Accession Number
- ADA163426
Entities
People
- Cynthia A. Phillips
Organizations
- Massachusetts Institute of Technology