In this paper, based on the hybrid methodology of top routing and bottom ro
uting, we propose an O(N-col) approach for the channel routing problem, whe
re N-col is the number of columns in a channel. Basically, top (bottom) rou
ting is a track-assignment-based routing approach in a channel, i.e. a chan
nel is routed track by track from top (bottom) to bottom (top) by running t
op (bottom) routing. In the proposed routing approach, the routing process
is divided into two phases: iterative-construction phase and merging- impro
vement I phase. In the iterative-construction phase, the net interval of ea
ch routing net is split into horizontal segments and these segments are fur
ther assigned track by track in a top-down or bottom-up manner. In the merg
ing-improvement phase, the routing result is further improved by merging sh
orter segments in different tracks into longer segments for the reduction o
f the total wire length and the number of vias. Finally, the proposed appro
ach has rested many published channels and the routing results are in the o
ptimal number of tracks. For example, the Deutsch's difficult channel is ro
uted in 19 tracks with automatic introduction of doglegs. In addition to th
e optimality of the number of tracks, the proposed approach obtains fewer v
ias and shorter total wire length than all other Manhattan channel routers.
(C) 1999 Elsevier Science Ltd. All rights reserved.