Channel routing by sorting

Author

Chaudhary, Kamal ; Robinson, Peter

Author_Institution

Comput. Lab., Cambridge Univ., UK

Volume

10

Issue

6

fYear

1991

fDate

6/1/1991 12:00:00 AM

Firstpage

754

Lastpage

760

Abstract

A novel approach for the channel routing problem based on sorting is described. A router based on the bubble-sort for routing two point nets across a channel is presented. A lower and an upper bound on the channel width and an upperbound on the number of vias are given. The router is extended for handling multiterminal nets and single-sided connections. Results for multilayer channel routing are presented. The high-speed and predictable performance of these channel routing algorithms makes them valuable in assessing the difficulty of routing a particular configuration of logic blocks. This makes then suitable for use when calculating a cost metric in an iterative placement algorithm

Keywords

circuit layout CAD; multiterminal networks; network topology; CAD; bubble-sort; channel routing; iterative placement algorithm; layout design; logic blocks; multilayer routeing; multiterminal nets; routing algorithms; single-sided connections; sorting; Fabrication; Geometry; Helium; Nonhomogeneous media; Routing; Semiconductor device modeling; Solid modeling; Sorting; Upper bound; Wire;

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.137504

Filename

137504