TOPOLOGICAL VIA MINIMIZATION REVISITED

被引：6

作者：

SARRAFZADEH, M

LEE, DT

机构：

[1] Department of Electrical Engineering and Computer Science, Northwestern University, Evanston

来源：

IEEE TRANSACTIONS ON COMPUTERS | 1991年 / 40卷 / 11期

关键词：

ALGORITHM; CIRCLE GRAPHS; RESTRICTED PERMUTATION GRAPH; TOPOLOGICAL VIA MINIMIZATION; VLSI LAYOUT;

D O I：

10.1109/12.102839

中图分类号：

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

学科分类号：

0812 ;

摘要：

We consider the topological via minimization problem in a two-layer environment. Given is a set of n two-terminal nets in a bounded region, we want to find a homotopy to assign nets to distinct layers so that no two nets on the same layer cross each other and the number of vias is minimized. We use a recursive approach to solve this problem optimally in which an optimal solution to a two-sided channel routing problem is used as a basis. The notion of partition number K of a circle graph is introduced and the total running time of the via minimization algorithm is shown to be O((n/K)2K-2 log(n/K)), where n is the total number of nets.

引用

页码：1307 / 1312

页数：6

共 12 条

[1] AN EFFICIENT ALGORITHM FOR MAXDOMINANCE, WITH APPLICATIONS [J].

ATALLAH, MJ ;

KOSARAJU, SR .

ALGORITHMICA, 1989, 4 (02) :221-236

[2]

BUCKINGHAM MA, 1980, THESIS NEW YORK U

[3]

Hsu C.-P., 1983, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, VCAD-2, P235

[4]

LEE DT, 1990, SIAM J COMPUT, V9, P1041

[5] NEW LOWER BOUND TECHNIQUES FOR VLSI [J].

LEIGHTON, FT .

MATHEMATICAL SYSTEMS THEORY, 1984, 17 (01) :47-70

[6]

LOU RD, 1990, 1ST P ACM SIAM C DIS

[7]

LOU RD, IN PRESS SIAM J DISC

[8] AN UNCONSTRAINED TOPOLOGICAL VIA MINIMIZATION PROBLEM FOR 2-LAYER ROUTING [J].

MAREKSADOWSKA, M .

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, 1984, 3 (03) :184-190

[9]

Preparata Franco P, 2012, COMPUTATIONAL GEOMET

[10] A NEW APPROACH TO TOPOLOGICAL VIA MINIMIZATION [J].

SARRAFZADEH, M ;

LEE, DT .

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, 1989, 8 (08) :890-900

← 1 2 →