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

New Algorithm for Point-to-Point Wiring Based on Boundary Expansion

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

Global wiring is a very important step in the Very Large Scale Integrated（VLSI） circuits design. Classic maze routing algorithm and its improved versions are widely used to deal with global routing problems in the industrial sector. With the decreasing process node, the shortcoming of the high complexity of the maze routing algorithm becomes increasingly evident. By means of a new concept boundary expansion, this paper presents a new point-to-point wiring path search algorithm to solve the high complexity problem of rapidly increase with the expansion of the scale of routing. With the definition of free node, the new algorithm abandons the inefficient node by node expansion method. Instead, this algorithm expands the boundary and finds new free nodes and will not terminate until find out a path or determine that no solution is available. The theoretical and experimental comparisons are conducted between the proposed algorithm and classic routing algorithms. Experimental results show that the proposed algorithm can complete the routing with the runtime of 7%~14%of the classic algorithm in most cases.