UNCONSTRAINED VIA MINIMIZATION FOR TOPOLOGICAL MULTILAYER ROUTING

被引：7

作者：

STALLMANN, M ^{[1
]}

HUGHES, T ^{[1
]}

LIU, WT ^{[1
]}

机构：

[1] N CAROLINA STATE UNIV,DEPT ELECT & COMP ENGN,RALEIGH,NC 27695

来源：

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS | 1990年 / 9卷 / 09期

基金：

美国国家科学基金会;

关键词：

D O I：

10.1109/43.59073

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

A theoretical study is presented which allows determination of the minimum number of vias for realizable multilayer channel routing under a topological model. The theory is sufficiently general to solve a variety of problems under different technological constraints, e.g., VLSI multilayer switchbox and channel routing, through-hole printed circuit board (PCB) channels, and single layer routing. Topological routing is concerned with wire intersection but not area, zero width wires and zero area vias being assumed. Unconstrained via minimization (UVM) is not constrained to a prerouted topology. This paper presents restrictive cases of UVM, finding most to be NP-hard, but the case resulting from constraints of traditional switchbox or channel routing to be solvable in 0(kn2), where k is the maximum number of pins of a net on a layer and n is the number of pins. The minimum number of vias for various switchbox and channel routing benchmarks are reported. © 1990 IEEE

引用

页码：970 / 980

页数：11

共 35 条

[1]

BOWLBY R, 1985, IEEE SPECTRUM, P37

[2]

BRUELL P, 1985, P INT C COMPUTER AID, P298

[3]

Burstein M., 1983, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, VCAD-2, P223, DOI 10.1109/TCAD.1983.1270040

[4]

CHANG K, 1985, TR8533 U MINN DEP CO

[5] EFFICIENT ALGORITHMS FOR LAYER ASSIGNMENT PROBLEM [J].

CHANG, KC ;

DU, DHC .

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, 1987, 6 (01) :67-78

[6]

CHEN Y, 1981, M8179 U CAL EL RES L

[7]

CHEN YK, 1984, IEEE T COMPUT AID D, V3, P156, DOI 10.1109/TCAD.1984.1270070

[8] A NEW APPROACH TO 3-LAYER OR 4-LAYER CHANNEL ROUTING [J].

CONG, JS ;

WONG, DF ;

LIU, CL .

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, 1988, 7 (10) :1094-1104

[9]

DEUTSCH DN, 1976, 19TH P DES AUT C IEE, P425

[10]

Even S., 1971, THEORY MACHINES COMP, P71, DOI DOI 10.1016/B978-0-12-417750-5.50011-7

← 1 2 3 4 →