On New Algorithm for Channel Routing
Abstract
We present new channel routing algorithms that consider the characteristic of net crossings. The routing strategy is based on parallel bubble sorting technique. NonManhattan wires as well as overlapping wires are introduced. Preliminary results show that a class of channel routing problems can be routed in height less than the Manhattan density.
References
T. Ohtsuki, Layout design and verification, 1986
В.А. Селютин, Машинное конструирование электронных устройств. Москва, “Советское радио”, 1977.
A. Frank. Disjoint paths in a rectilinear grid. In Combinatorica, 2(4), pages 361-371, 1982.
K. Mehlhom, EP. Preparata, and M. Sarrafzadeh. Channel routing in knock-knee mode: simplified algorithms and proof, in Algorithmica, 1(2), pages 213-221,1986.
Ronald L. Rivest , Charles M. Fiduccia, A “greedy” channel router, Proceedings of the 19th conference on Design automation, p.418-424, January 1982.
M. Sarrafzadeh. Channel-routing problem in the knock-knee mode is np-complete. In IEEE Trans. on CAD, CAD-6(4), pages 503-506, 1987.
T. Yoshimura and E.S. Kuh. Efficient algorithms for channel routing. In IEEE Trans. on CAD of lntegrated Circuits and Systems, V. CAD.l, pages 25-35, 1982.
Downloads
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
