A new approach to three- or four-layer channel routing
A new approach to three- or four-layer channel routing
复制标题
三层或四层通道路由的新方法
DOI：
10.1109/43.7808
复制
发表时间：
1988
期刊：
影响因子：
--
通讯作者：
C. Liu
中科院分区：
文献类型：
--
作者：
J. Cong;Martin D. F. Wong;C. Liu
提出了一种解决三层或四层信道路由问题的方法。提出了一种将两层路由方案系统地转换为三层路由方案的通用技术。与目前提出的其他三层通道路由器相比，所提出的路由器性能良好。特别是，它为著名的Deutsch困难例子提供了一个十轨的最优解决方案，而其他著名的三层信道路由器需要11或更多的轨道。该方法被扩展到四层通道路由。给定任何两层通道路由解决方案，没有使用w路的无限制狗腿，路由器可以获得使用不超过w/2路的四层路由解决方案。给出了任意四层信道路由问题的理论上限d/2+2。>
An approach to the three-layer or four-layer channel-routing problem is presented. A general technique that transforms a two-layer routing solution systematically into a three-layer routing solution is developed. The proposed router performs well in comparison with other three-layer channel routers proposed thus far. In particular, it provides a ten-track optimal solution for the famous Deutsch's difficult example, whereas other well-known three-layer channel routers required 11 or more tracks. The approach is extended to four-layer channel routing. Given any two-layer channel-routing solution without an unrestricted dogleg that uses w tracks, the router can obtain a four-layer routing solution using no more than w/2 tracks. A theoretical upper bound d/2+2 for arbitrary four-layer channel routing problems is also given. >