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

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