Hierarchical bubble-sorting-based non-Manhattan channel routing
Jin-Tai Yan · IEE Proceedings - Computers and Digital Techniques · 2000
For a bubble-sorting-based non-Manhattan channel routing (BSNMCR) problem, Chen's O(k2n) optimal algorithm and Yan's O(kn) optimal algorithm have been proposed respectively where n is the number of terminals and k is the number of routing tracks in a channel. For the sorting process of a given vector, these two optimal algorithms consider that a left-swap pass or a right-swap pass is an overall pass. As the distribution of most of the routing nets in a channel has a local property, a vector may be divided into several smaller subvectors, and each subvector can be sorted by a left-swap pass or a right-swap pass to further optimise the number of tracks in a channel. In the paper, based on an optimality-oriented swap-direction selection and a `divide-and-conquer' technology, a hierarchical BSNMCR (HBSNMCR) problem is formulated and an O(hn) optimal algorithm is proposed, where h is the number of routing tracks in a HBSNMCR solution, for h≤k.