A Caltech Library Service

An Integer Based Hierarchical Representation for VLSI

Whitney, Telle and Mead, Carver (1986) An Integer Based Hierarchical Representation for VLSI. In: Advanced research in VLSI : proceedings of the fourth MIT conference, April 7-9, 1986. MIT Press , Cambridge, MA, pp. 241-257. ISBN 9780262121132.

[img] PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


Geometries with 45° line segments are often used in integrated circuit layouts, since they can save considerable area. In the limit, the introduction of 45° lines is only 5% less dense than optimal geometry, i.e. circular geometry, whereas manhattan geometry is 27% less dense [7]. Obviously any actual design cannot make use of this density factor everywhere - but figure 1 illustrates a simple but common routing problem where the introduction of 45° wires substantially reduces the area. There has been a trend towards strict manhattan geometries in recent years, however, since it is commonly believed that design rule checking is complicated by the inclusion of intermediate angles [11, 1, 3, 6]. This paper describes a hierarchical representation that supports a complete circuit description, but restricts the set of allowable lines to be horizontal, vertical and 45°. Points are constrained to lie on an integer grid. Rather than use arbitrary polygons, transistors and connection wires are constructed from paths whose sides and ends are created from an octagonal circle approximation. The geometry for contacts is octagonal and is generated from the same circle approximation. The integer grid and restricted line styles allow the simplification of all the Geometrical Design Rule (GDR) checking algorithms - for example a square root is not required in the point-point distance calculations, and division is never required. In fact this approach requires less computation than typical manhattan systems. All of the calculations that normally require real number representation are expressed in integers, eliminating any possibility of round-off errors.

Item Type:Book Section
Additional Information:© 1986 MIT Press. We would like to acknowledge Dr. Ivan Sutherland whose polygon package ideas inspired the work. Special appreciation to members of "the group" in the Caltech Computer Science Lab for their support, ideas and critiques. Thanks to Dick Lyon for his careful comments, and to John Wawrzynek for his help. This work was supported by the System Development Foundation.
Funding AgencyGrant Number
System Development FoundationUNSPECIFIED
Record Number:CaltechAUTHORS:20150112-140550704
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:53582
Deposited On:13 Jan 2015 17:40
Last Modified:03 Oct 2019 07:50

Repository Staff Only: item control page