一种新的无网格拆线重布算法

A New Gridless Ripup and Reroute Algorithm

结合无网格布线的特点 ,提出一种新的无网格拆线重布算法 .该算法显式地表示并动态更新线网所属区域的拥挤程度 .在拆线重布进行待布线网的路径搜索时 ,每个扩展节点中增加拆除线网周边的拥挤权重 ,从而将待布线网的路径搜索过程和拆除线网的选择过程统一起来 ,有效地提高了被拆除线网重新布通的可能性 .该算法利用改进的二叉区间树有效组织中间数据 ,降低计算的复杂度 .实验结果表明 ,该算法能有效消除布线顺序对布线结果的影响 ,提高布通率 。

In accordance with the properties of gridless area routing,a new ripup and reroute algorithm is proposed.This algorithm records and dynamicly updates the congestion in the area of each net explicitly.Congestion weight along the explored path is calculated in each expansion node during the ripup and reroute process.Thus,the procedure of path exploration is unified with the selection procedure of nets to be ripped.The possibility that the ripped nets can be successfully rerouted is improved by this method.Besides,an enhanced interval tree is used to manage and organize the intermediate data so as to reduce the computation complexity.Test results indicate that this algorithm can effectively eliminate the influence of net order on routing.The complete ratio is improved after the ripup and reroute process and the operating speed of this algorithm is faster.