AN EXACT ALGORITHM FOR SINGLE-LAYER WIRE LENGTH MINIMIZATION

被引：4

作者：

HO, JM

SUZUKI, A

SARRAFZADEH, M

机构：

[1] NANZAN UNIV,DEPT INFORMAT SCI SYST,NAGOYA,AICHI 466,JAPAN

[2] NORTHWESTERN UNIV,DEPT ELECT ENGN & COMP SCI,EVANSTON,IL 60201

来源：

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS | 1993年 / 12卷 / 01期

关键词：

D O I：

10.1109/43.184855

中图分类号：

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

学科分类号：

0812 ;

摘要：

Consider an arbitrary single-layer detailed routine L of a set of two-terminal nets. We present the necessary and sufficient condition for a layout to have minimum length under homotopic transformations i.e., without changing the given global routing). Based on the proposed classification and the notion of line-segment visibility, we present an exact algorithm that minimizes the total wire length of L. The proposed algorithm runs in O(n2) time, where n is the number of bends in L.

引用

页码：175 / 180

页数：6

共 13 条

[1]

Aho A. V., 1974, DESIGN ANAL COMPUTER

[2]

[Anonymous], 1984, ADV COMPUTING RES

[3]

Baker B. S., 1983, 24th Annual Symposium on Foundations of Computer Science, P360, DOI 10.1109/SFCS.1983.6

[4]

COHOON J, 1984, UNPUB CONNECTING 2 P

[5]

DAI W, UNPUB MULTILAYER ROU

[6]

HSU CP, 1983, 20TH P DES AUT C, P578

[7]

Leiserson Charles E., 1985, P 17 ANN ACM S THEOR, P69, DOI [10.1145/22145.22153, DOI 10.1145/22145.22153]

[8] BOUNDARY SINGLE-LAYER ROUTING WITH MOVABLE TERMINALS [J].

LIAO, KF ;

SARRAFZADEH, M .

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, 1991, 10 (11) :1382-1391

[9]

Marek-Sadowska M., 1983, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, VCAD-2, P246, DOI 10.1109/TCAD.1983.1270042

[10]

PINTER RY, 1983, 3RD CALTECH C VLSI

← 1 2 →