Structure Of Non-manhattan Channel Routing Algorithms Research

This thesis deals with two optimal algorithms of Non-Manhattan channel routing in VLSI physics design. Now integrated circuit industry is progressing rapidly in deep sub-micron technology, the scale of integration and the degree of complexity of circuit increase rapidly, it is necessary and feasible to adopt Non-Manhattan model for channel routing ,in order to reduce routing area, wire lengthen and thus to reduce crosstalk. Base on those object just mentioned, our focus is placed on two algorithms as follow: By analysing the characteristic of the mapping which from sorting vectors to routing wire segment in bubble sort based Non-Manhattan channel routing, we present a dichotomy algorithm to improve the optimal bubble sort based Non-Manhattan channel routing. The dichotomy algorithm allows different swap direction in a same sorting step, and can decrease channel height (tracks) and wire length A greedy routing algorithm for irregular channel base on a non-Manhattan architecture called MD (Manhattan-Diagonal) model is proposed. The algorithm greedly to use less tracks, and minimizes the vias number and wire length by employing a heuristc topologic sore. It deals with both the regular and irregular channel routing cases, and extend it's ability to L-shaped channel without amend, where the irregular channel and L-shaped channel often occur in BBL layout. These two algorithms are implemented on PC and applied to some benchmark examples, the experimental results are satisfactory.