Description
Design of very large scale integrated circuits requires structured design approaches to deal with the ever increasing complexity of these circuits. As designs become more complex, the need for layout analysis tools, such as design rule checkers and circuit verifiers, becomes greater. However, current layout analysis tools make no use of this structure, and as a result, are taking increasingly large amounts of computer time. This thesis examines ways in which these analysis tools can exploit the structure present in the layouts of large integrated circuits in order to improve run-times.
A major obstacle in building hierarchical analysis tools is in handling overlaps of cells. This thesis describes an algorithm that transforms a hierarchical layout description into a hierarchical layout description without overlaps. This newly created hierarchy is called the disjoint hierarchy. Analysis tools that rely on this disjoint hierarchy can effectively exploit the structure of the layout. The design of hierarchical algorithms to do circuit extraction, geometric design rule checking, and simple mask operations are also described. A program that implements the disjoint transformation and performs circuit extraction is discussed. A comparison of the runtimes of this program with conventional circuit extractors shows a considerable speedup for even relatively small circuits.