A Caltech Library Service

A Hierarchical Design Rule Checker


Whitney, Telle (1981) A Hierarchical Design Rule Checker. Master's thesis, California Institute of Technology. doi:10.7907/dqz1-c122.


This thesis describes a new approach to the problem of Geometrical Design Rule Checking (DRC). Previous DRC implementations have dealt with fully instantiated geometrical artwork. As the complexity of VLSI increases, it becomes infeasible to analyze the vast amounts of information present in a fully instantiated design. The DRC algorithm presented here introduces an approach that exploits the structural hierarchy of a design in order to reduce the computational complexity of the geometrical tests that need to be made. The technique described is also applicable to other types of design checking such as circuit extraction, functional verification and electrical rule verification.

A new DRC algorithm has been developed that, by making use of the structure inherent in a hierarchical design, eliminates many redundant design rule checks. In this approach there are two places where possible design rule violations may occur. The first is within a symbol definition. The second is the area where two symbols interact. The algorithm checks a given definition only once, and then examines how interactions within each new environment where the definition is placed modify the original definition. A note is made after each interaction has been scrutinized, so that a duplicate situation will not be rechecked.

An implementation of the hierarchical DRC algorithm has been written at Caltech. This implementation extracts a minimal number of pairwise geometrical comparisons needed to check the entire design. The program accepts as in put a design description in the Caltech Intermediate Form (CIF). The output of the program is currently a fully instantiated version of those portions of the geometry that need to be checked in order to check the entire design.

A means of expressing the designer's intent through the design description is required. Current DRC's deal with geometrical artwork exclusively. Most of the difficult design rules are involved in the checking of devices. Rather than restricting the designer to the use of geometry, the idea of a primitive element is introduced. A primitive element is defined to be anything that cannot be broken down into sub-elements. A design defined using primitive elements conveys more of the functional structure than a purely geometric definition.

Item Type:Thesis (Master's thesis)
Subject Keywords:Computer Science
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Computer Science
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • Unknown, Unknown
Thesis Committee:
  • Unknown, Unknown
Defense Date:19 May 1981
Other Numbering System:
Other Numbering System NameOther Numbering System ID
Record Number:CaltechTHESIS:04122012-100224959
Persistent URL:
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:6913
Deposited By: Benjamin Perez
Deposited On:12 Apr 2012 17:53
Last Modified:09 Nov 2022 19:20

Thesis Files

PDF - Final Version
See Usage Policy.


Repository Staff Only: item control page