Time-efficient VLSI artwork analysis algorithms in GOALIE2

Author

Chiang, Kuang-wei ; Nahar, Surendra ; Lo, Chi-Yuan

Author_Institution

AT&T Bell Lab., Murray Hill, NJ, USA

Volume

8

Issue

6

fYear

1989

fDate

6/1/1989 12:00:00 AM

Firstpage

640

Lastpage

648

Abstract

New algorithms used in the GOALIE2 circuit extraction system are presented that are based on representing VLSI layout geometries as trapezoids. These include polygon-to-trapezoid decomposition, scanline management, and output sorting. The scanline algorithm virtually eliminates the redundant computation present in similar systems. It solves the VLSI layout analysis problem in O(n+k) expected time and O(√n) expected space, where n is the total number of input segments and k is the total number of intersection points. The new scanline algorithm is robust in what it will maintain its performance over a wide range of layout styles. Experimental results show that the running time is O(n^1.0547), i.e. that these algorithms enable one to perform VLSI layout analysis in nearly linear time

Keywords

VLSI; circuit layout CAD; integrated circuit technology; GOALIE2; VLSI artwork analysis algorithms; VLSI layout geometries; circuit extraction system; output sorting; polygon/trapezoid decomposition; scanline management; time efficient analysis; trapezoids; Algorithm design and analysis; Central Processing Unit; Circuit analysis computing; Compaction; Computational geometry; Design automation; Robustness; Routing; Sorting; Very large scale integration;

fLanguage

English

Journal_Title

Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on

Publisher

ieee

ISSN

0278-0070

Type

jour

DOI

10.1109/43.31520

Filename

31520