%0 Journal Article
%T A New Gridless Ripup and Reroute Algorithm<br>一种新的无网格拆线重布算法
%A Xie Min
%A Cai Yici
%A Hong Xianlong
%A <br>谢民
%A 蔡懿慈
%A 洪先龙
%J 半导体学报
%D 2002
%I 
%X 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.
%K gridless area routing
%K ripup and reroute
%K interval tree<br>无网格区域布线
%K 拆线重布
%K 区间树
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=1319827C0C74AAE8D654BEA21B7F54D3&jid=025C8057C4D37C4BA0041DC7DE7C758F&aid=5A9543DAAA608A62&yid=C3ACC247184A22C1&vid=EA389574707BDED3&iid=CA4FD0336C81A37A&sid=D767283A3B658885&eid=4BB057F167CF3A60&journal_id=1674-4926&journal_name=半导体学报&referenced_num=0&reference_num=16