Designing a channel router by hybrid methodology of top routing and bottomrouting

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.