|
In the field of channel routing problem, Mixed Slope Model
(MSM) is a young routing model.Mixed Slope Model has two wiring
directions(+45°,-45°) than the directions (0°,90°) that
Manhattan Model has.In this thesis, we propose a new multi-
terminal channel router for Mixed-Slope Model.The proposed
method is essentially a combination of the methods of greedy
router and maze router. The algorithm in this thesis has
following benefits: 1.Mixed Slope Model has less constraints
than the Manhattan Model. And we have more chance to obtain
better solution in channel routing. 2.We initially use greedy
routing method to rapidly interconnect most of nets, and then
employ minimum cost oriented maze router in order to
interconnect the remaining nets. As a result, high connection
ratio can be achieved. 3.The router algorithm in this thesis
provides that net on one layer can be overlapped by other net
on different layer. 4.We use objected-oriented technology to
develop this algorithm. And it is convenient for modifying and
extending. Extensive experiments have been made to test the
performance of our router. As we expected, in most of the
channels under tested, fewer tracks are needed in Mixed-Slope
model than that in the MM. to route the channel completely. In
some classical examples such as Shift by N Channel and Reverse
by N channel, we can get solutions as well as other routers or
better. In particular for Perfect Shuffle Permutation Channel
we can get better solution which use tracks of the optimal
solution. And we can also get better solution of Burstein
Difficult Channel than the result of other router.
|