DocumentCode :
1054927
Title :
Optimal algorithms for bubble sort based non-Manhattan channel routing
Author :
Chen, C. Y Roger ; Hou, Cliff Yungchin ; Singh, Uminder
Author_Institution :
Dept. of Electr. & Comput. Eng., Syracuse Univ., NY, USA
Volume :
13
Issue :
5
fYear :
1994
fDate :
5/1/1994 12:00:00 AM
Firstpage :
603
Lastpage :
609
Abstract :
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° and -45° 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 N 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
Keywords :
circuit layout CAD; computational complexity; integrated circuit technology; network routing; IC layout; bubble sort based routing; nonManhattan channel routing; optimal algorithms; three-layer routing; time complexity; two-layer routing; Computer applications; Costs; Design automation; Fabrication; Helium; Routing; Software engineering; Wires;
fLanguage :
English
Journal_Title :
Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on
Publisher :
ieee
ISSN :
0278-0070
Type :
jour
DOI :
10.1109/43.277633
Filename :
277633
Link To Document :
بازگشت