一种新的与线网顺序无关的随机优化总体布线算法  

A Novel Random Global Routing Algorithm Independent of Net Ordering

作　　者：鲍海云[1] 经彤[1] 洪先龙[1] 蔡懿慈[1] 

机构地区：[1]清华大学计算机科学与技术系,北京100084

出　　处：《计算机学报》2001年第6期574-579,共6页Chinese Journal of Computers

基　　金：国家"九七三"重点基础研究发展规划项目!(G-19980 30 411);国家自然科学基金!(6 9776 0 2 7);中国博士后科学基金!([2 0 0 0 ] 2 3

摘　　要：针对目前总体布线中仍然存在的 3个关键问题 :布线结果受布线顺序的影响、总体布线图中拥挤区域的不可预见性、线网连接式样受到算法的限制等 ,该文提出了一种新的不受线网顺序影响的总体布线算法 ,并实现了相应的总体布线器 RINO- Router.该算法采用随机优化方法来保证先后被拆线重布的线网有相同的通过拥挤区域的机会 ,并能得到 GRG边的拥挤度估计值 ;采用高效的 Steiner树改造算法构造避开拥挤区域的布线树 .采用典型电路实例进行了测试 ,并将布线结果与基于多商品流算法的总体布线器 Matula- Router进行了对比 .结果表明 ,RINO- Router能够在短得多的运行时间内求得质量与 Matula-Global routing is a significant part of VLSI computer aided physical design, i.e., layout design. It is proved that the optimal global routing is a NP hard problem. In recent two decades, many global routing algorithms have been presented. However, the following three problems are still the critical problems in global routing. (1) The final routing solution is sensitive to the order in which the nets are considered; (2) It is very difficult for global routers to predict congested areas, i.e., congested edges, in global routing graph (GRG); (3) The net connection patterns that can be produced are restricted by the routing algorithm. To solve these three problems, we propose a novel global routing algorithm independent of net ordering (RINO) in this paper. RINO uses random dynamic optimization method and six special optimization strategies to keep the equality of earlier routed nets and later routed ones in passing congested edges and to get the accurate estimation of congested area step by step. That is, let the nets routed earlier give up passing some edges if the nets routed later really need to pass them. RINO also uses an effective generating steiner tree method to let a net not pass any congested edges. As a result, all congested nets are able to have almost equal chances to pass the hot edges. According to RINO algorithm, a global router called RINO Router is implemented in the C language on a Sun Enterprise 450 under the Unix operating system. We tested five Microelectronics Center of North Carolina (MCNC) benchmark circuits, which are C2, C5, C7, S13207, and Avq. Furthermore, the experimental results are compared with those of Matula Router, a very good global router since 1991. The experimental results show that RINO Router performs much faster than Matula Router does while they get solutions with approximate quality (evaluated by the number of overflow edges and total wire length).

关 键 词：总体布线图 布图设计 计算机辅助设计 超大规模集成电路 随机优化总体布线算法 

分 类 号：TN47[电子电信—微电子学与固体电子学] TP391.72[自动化与计算机技术—计算机应用技术]