OPTIMAL-ALGORITHMS FOR BUBBLE SORT BASED NON-MANHATTAN CHANNEL ROUTING

被引：9

作者：

CHEN, CYR

HOU, CY

SINGH, U

机构：

[1] Department of Electrical and Computer Engineering, Syracuse University, Syracuse

[2] Department of Electrical Engineering, Kaosiung Institute of Technology, Kaosiung, Taiwan

来源：

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS | 1994年 / 13卷 / 05期

关键词：

Algorithms - Computer aided design - Printed circuit manufacture - Surface mount technology;

D O I：

10.1109/43.277633

中图分类号：

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

学科分类号：

0812 ;

摘要：

It has been pointed out that, in many cases, results generated by non-Manhattan channel routers will be better than those generated by Manhattan routers. Non-optimal bubble sort based algorithms for non-Manhattan channel routing have been proposed in the literature by also allowing connections in the +45-degrees and -45-degrees directions. In this paper, optimal algorithms are proposed for the two-layer and three-layer non-Manhattan channel routing problems based on an identical problem formulation. The time complexities of our algorithms and the existing algorithm (which produces the best results so far) are O(K2 * N) and O(K * N2), respectively, where N is the number of terminals (i.e., the length) of the channel and K is the number of routing tracks (i.e., the height) in the channel. K is always less than N, and in most cases is much smaller than N. Clearly, a significant improvement in time complexity over the existing algorithm (which produces the best results so far) is achieved, while ensuring optimality.

引用

页码：603 / 609

页数：7

共 9 条

[1]

BURSTEIN M, 1983, 20TH P DES AUT C, P591

[2] CHANNEL ROUTING BY SORTING [J].

CHAUDHARY, K ;

ROBINSON, P .

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, 1991, 10 (06) :754-760

[3]

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

[4]

HASHIMOTO A, 1971, 8TH P DES AUT WORKSH, P214

[5]

Knuth D.E., 1997, ART COMPUTER PROGRAM, V3

[6] A PRELIMINARY-STUDY OF A DIAGONAL CHANNEL-ROUTING MODEL [J].

LODI, E ;

LUCCIO, F ;

PAGLI, L .

ALGORITHMICA, 1989, 4 (04) :585-597

[7]

RIVEST RL, 1982, 19TH P DES AUT C, P418

[8]

Wang D.C, 1991, P 28 ACM IEEE DES AU, P49, DOI [10.1145/127601.127626, DOI 10.1145/127601.127626]

[9]

Yoshimura T., 1982, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, VCAD-1, P25, DOI 10.1109/TCAD.1982.1269993

← 1 →