engleski

Performance Comparison of Several Data Structures for Storing VLSI Geometry

This paper, in its first part, describes several well-known dana structures for storing VLSI geometry and presents their implementation. KD tree data structure, as one of the first used for this purpose, is described in detail. Its usage is illustrated on the problem of design rule check (DRC) verification. Corner stitching, data structure introduced by Ousterhout, is presented and its main characteristics are given. Patented bucketing dana structure is described. This data structure was independently implemented on the basis of patent description. The implementation was benchmark for other algorithms, as data structure that is used in modern CAD tools. Performance of the described algorithms was tested on several realworld layout examples in the second part of the paper. Speed of typical operations, together with memory requirements, were compared. In the conclusion main advantages and disadvantages of the implemented algorithms are discussed.

CAD geometry data structure; VLSI layout; VLSI physical design; performance comparison

nije evidentirano