Efficient Algorithms for Channel Routing

Author

Yoshimura, Takesh ; Kuh, Ernest S.

Author_Institution

Department of Electrical Engineering and Computer Sciences, and the Electronics Research Laboratory, University of California, Berkeley, CA, USA

Volume

1

Issue

1

fYear

1982

fDate

1/1/1982 12:00:00 AM

Firstpage

25

Lastpage

35

Abstract

In the layout design of LSI chips, channel routing is one of the key problems. The problem is to route a specified net list between two rows of terminals across a two-layer channel. Nets are routed with horizontal segments on one layer and vertical segments on the other. Connections between two layers are made through via holes. Two new algorithms are proposed. These algorithms merge nets instead of assigning horizontal tracks to individual nets. The algorithms were coded in Fortran and implemented on a VAX 11/780 computer. Experimental results are quite encouraging. Both programs generated optimal solutions in 6 out of 8 cases, using examples in previously published papers. The computation times of the algorithms for a typical channel (300 terminals, 70 nets) are 1.0 and 2.1 s, respectively.

Keywords

Design automation; Helium; Laboratories; Large scale integration; Routing; Testing;

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/TCAD.1982.1269993

Filename

1269993