Naslov
Performance Comparison of Several Data Structures for Storing VLSI Geometry

Autori
Grgek, Marijana ; Branica, Ivan ; Divković-Pukšec, Julijana

Vrsta, podvrsta i kategorija rada
Radovi u zbornicima skupova, cjeloviti rad (in extenso), znanstveni

Izvornik
Proceedings of Eurocon 2003 / Zajc, Baldomir ; Tkalčič, Marko - Ljubljana, 2003, 156-159

Skup
Eurocon 2003 Computer as a Tool

Mjesto i datum
Ljubljana, Slovenija, 2003

Vrsta sudjelovanja
Predavanje

Vrsta recenzije
Međunarodna recenzija

Ključne riječi
CAD geometry data structure; VLSI layout; VLSI physical design; performance comparison

Sažetak
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.

Izvorni jezik
Engleski

Znanstvena područja
Elektrotehnika

POVEZANOST RADA