A Hierarchical Design Rule Checker

Citation

Whitney, Telle (1981) A Hierarchical Design Rule Checker. Master's thesis, California Institute of Technology. doi:10.7907/dqz1-c122. https://resolver.caltech.edu/CaltechTHESIS:04122012-100224959

Abstract

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.

Thesis Files