|
|
半导体学报 2002
A New Gridless Ripup and Reroute Algorithm
|
Abstract:
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.
