Efficient algorithms for two and three-layer over-the-cell channel routing

Author

Shew, Paul-Waie ; Yan, Jin-Tai ; Hsiao, Pei-Yung ; Lim, Yong-Ching

Author_Institution

Dept. of Electr. Eng., Nat. Univ. of Singapore, Singapore

Volume

4

fYear

1994

fDate

30 May-2 Jun 1994

Firstpage

183

Abstract

We present a new efficient algorithm for both two and three-layer over-the-cell channel routing in the standard cell design technology. Our approach considers both density distribution in the channel and longest path in vertical constraint graph. Besides, we use vacant terminals to eliminate cycles in the vertical constraint graph as well as to reduce the maximum cliques in the horizontal constraint graph for selecting net segments to be routed over the cells. For the PRIMARY 1 benchmark examples, our router reduced the total channel height by 39.1% and 61.0% for two-layer and three-layer routing model, respectively

Keywords

VLSI; cellular arrays; circuit layout CAD; graph theory; logic CAD; network routing; PRIMARY 1 benchmark; VLSI; density distribution; horizontal constraint graph; longest path; maximum cliques; net segments; over-the-cell channel routing; standard cell design technology; three-layer channel routing; total channel height; two-layer channel routing; vacant terminals; vertical constraint graph; Algorithm design and analysis; Benchmark testing; Contracts; Routing; Very large scale integration;

fLanguage

English

Publisher

ieee

Conference_Titel

Circuits and Systems, 1994. ISCAS '94., 1994 IEEE International Symposium on

Conference_Location

London

Print_ISBN

0-7803-1915-X

Type

conf

DOI

10.1109/ISCAS.1994.409227

Filename

409227