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

Abstract

In this paper, based on the hybrid methodology of top routing and bottom routing, we propose an O(N-col) approach for the channel routing problem, where N-col is the number of columns in a channel. Basically, top (bottom) routing is a track-assignment-based routing approach in a channel, i.e. a channel is routed track by track from top (bottom) to bottom (top) by running top (bottom) routing. In the proposed routing approach, the routing process is divided into two phases: iterative-construction phase and merging- improvement I phase. In the iterative-construction phase, the net interval of each routing net is split into horizontal segments and these segments are further assigned track by track in a top-down or bottom-up manner. In the merging-improvement phase, the routing result is further improved by merging shorter segments in different tracks into longer segments for the reduction of the total wire length and the number of vias. Finally, the proposed approach has rested many published channels and the routing results are in the optimal number of tracks. For example, the Deutsch's difficult channel is routed in 19 tracks with automatic introduction of doglegs. In addition to the optimality of the number of tracks, the proposed approach obtains fewer vias and shorter total wire length than all other Manhattan channel routers. (C) 1999 Elsevier Science Ltd. All rights reserved.