CAJ | 학술논문

在超大规模集成电路设计中，全局布线是非常重要的步骤。工业界普遍采用经典的迷宫算法及其改进算法解决全局布线问题。随着工艺节点的减小，传统迷宫算法复杂度高的缺点越来越明显。针对传统迷宫算法的复杂度会随着布线规模的扩大而迅速增加的问题，借助于边界扩张的概念，提出一种新的点对点布线路径的搜索算法。摒弃了迷宫算法低效率的逐个节点扩张的思想，通过自由节点的定义对节点边界进行迅速扩张并不断地找到新的自由节点，直到找出路径或确定无解时结束。将该算法与经典的布线算法进行理论和实验比较，结果表明在大多数情况下该算法使用经典算法7%~14%的运行时间即可完成路径搜索。
재초대규모집성전로설계중，전국포선시비상중요적보취。공업계보편채용경전적미궁산법급기개진산법해결전국포선문제。수착공예절점적감소，전통미궁산법복잡도고적결점월래월명현。침대전통미궁산법적복잡도회수착포선규모적확대이신속증가적문제，차조우변계확장적개념，제출일충신적점대점포선로경적수색산법。병기료미궁산법저효솔적축개절점확장적사상，통과자유절점적정의대절점변계진행신속확장병불단지조도신적자유절점，직도조출로경혹학정무해시결속。장해산법여경전적포선산법진행이론화실험비교，결과표명재대다수정황하해산법사용경전산법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.