A "Greedy" Channel Router
A "Greedy" Channel Router
复制标题
“贪婪”通道路由器
DOI：
10.1145/62882.62912
复制
发表时间：
1983
期刊：
影响因子：
--
通讯作者：
C. M. Fiduccia
中科院分区：
文献类型：
--
作者：
Ronald L. Rivest;C. M. Fiduccia
我们提出了一种新的、“贪婪”的、快速、简单和高效的通道路由器。它总是成功的，通常使用的磁道不超过通道密度要求的一个磁道。(在极少数情况下，为了成功，它可能会被迫在通道的“末端”建立一些连接。)它假定所有接点和布线位于公共栅格上，垂直导线位于一个层上，水平位于另一个层上。贪婪的路由器以从左到右、逐列的方式连接频道，在开始下一列之前完成每一列的连接。在每一列中，路由器尝试使用简单的“贪婪”试探法来最大化所产生的布线的效用。它可以在几列的多个轨道上放置一张网，然后使用垂直慢跑将网“折叠”到一条轨道上。在未来的一些专栏中，它还可以使用慢跑将网移动到离其针脚更近的轨道上。路由器可能会偶尔向频道中添加新的曲目，以避免“卡住”。
We present a new, "greedy", channel-router that is quick, simple, and highly effective. It always succeeds, usually using no more than one track more than required by channel density. (It may be forced in rare cases to make a few connections "off the end" of the channel, in order to succeed.) It assumes that all pins and wiring lie on a common grid, and that vertical wires are on one layer, horizontal on another. The greedy router wires up the channel in a left-to-right, column-by-column manner, wiring each column completely before starting the next. Within each column the router tries to maximize the utility of the wiring produced, using simple, "greedy" heuristics. It may place a net on more than one track for a few columns, and "collapse" the net to a single track later on, using a vertical jog. It may also use a jog to move a net to a track closer to its pin in some future column. The router may occasionally add a new track to the channel, to avoid "getting stuck".