Hierarchical Channel Router
Hierarchical Channel Router
复制标题
分层通道路由器
DOI：
10.1016/0167-9260(83)90004-4
复制
发表时间：
1983
期刊：
影响因子：
--
通讯作者：
R. Pelavin
中科院分区：
文献类型：
--
作者：
M. Burstein;R. Pelavin
通道布线问题是布线问题的特例，当必须在位于矩形相对两侧的端子之间、在没有障碍物的矩形条带内执行互连时。我们在这里提出了一种新的通道布线算法，基于将问题简化为(2×FL)网格的情况，并一致地使用了“分而治之”的方法。对于当前的算法实现，运行时间与Nxnxlog(M)成正比，其中N是网数，n是通道长度(列数)，f？T是通道的宽度(轨道数)。假设传统的技术限制，即网络终端位于垂直网格线上，两个布线层可用于互连-一层专门用于垂直段，另一层用于水平段，每一层的变化都引入了通孔。该算法在布线质量方面始终优于几个已知路由器。我们在几个基准问题上测试了该算法。其中之一--Deutsch的“困难的例子”--布线时只有19条水平布线轨道(这是最小的水平布线轨道)，而所有其他已知的路由器需要20条或MNRE轨道。
The channel routing problem is a special case of the wire routing problem when interconnections have to be performed within a rectangular strip having no obstructions, between terminals located on opposite sides of the rectangle. We present here a new channel routing algorithm, based on reduction of the problem to the case of a (2 X fl) grid and on consistent utilization of a “divide and conquer” approach. For the cmrent implementation of the algorithm, the running time is proportional to Nxn x log (m), where N is the number of nets, n is the length of the channel (number of columns) and f? t is the width of the channel (number of tracks). Traditional technological restrictions are assumed, ie net terminals are located on vertical grid lines, two wiring layers are available for interconnections-one layer is used exclusively for vertical segments, another for horizontal and vias are introduced for each layer change. This algorithm consistently outperforms several known routers in quality of wiring. We tested the algorithm on several benchmark problems. One of them-Deutsch’s “difficult example”-was routed with only 19 horizontal wiring tracks (the absolute minimum for this case), whereas all other known routers required 20 or mnre tracks.