廖海涛，史 峥，张 腾

(浙江大学超大规模集成电路设计研究所，杭州 310027)

基于边界扩张的点对点布线新算法

廖海涛，史 峥，张 腾

(浙江大学超大规模集成电路设计研究所，杭州 310027)

在超大规模集成电路设计中，全局布线是非常重要的步骤。工业界普遍采用经典的迷宫算法及其改进算法解决全局布线问题。随着工艺节点的减小，传统迷宫算法复杂度高的缺点越来越明显。针对传统迷宫算法的复杂度会随着布线规模的扩大而迅速增加的问题，借助于边界扩张的概念，提出一种新的点对点布线路径的搜索算法。摒弃了迷宫算法低效率的逐个节点扩张的思想，通过自由节点的定义对节点边界进行迅速扩张并不断地找到新的自由节点，直到找出路径或确定无解时结束。将该算法与经典的布线算法进行理论和实验比较，结果表明在大多数情况下该算法使用经典算法7%～14%的运行时间即可完成路径搜索。

超大规模集成电路；全局布线；迷宫算法；点对点布线；边界扩张；自由节点

1 概述

全局布线是物理设计中布局之后的重要步骤，布局确定了模块在芯片上的位置以及模块上各引脚的分布，并通过网表提供了各引脚间的互连信息。布线过程就是实现各模块间的连接。全局布线作为布线过程的第一步，目的就是把每条线网的各个部分合理地分配到各个布线通道中去，为之后的详细布线提供初始布线走向，这一阶段布线结构的好坏决定芯片的整体性能。……