首页 | 本学科首页   官方微博 | 高级检索  
     

一种新的与线网顺序无关的随机优化总体布线算法
引用本文:鲍海云,经彤,洪先龙,蔡懿慈.一种新的与线网顺序无关的随机优化总体布线算法[J].计算机学报,2001,24(6):574-579.
作者姓名:鲍海云  经彤  洪先龙  蔡懿慈
作者单位:清华大学计算机科学与技术系
基金项目:国家“九七三”重点基础研究发展规划项目!(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-Router相近的总体布线解。

关 键 词:总体布线图  布图设计  计算机辅助设计  超大规模集成电路  随机优化总体布线算法
修稿时间:2000年2月25日

A Novel Random Global Routing Algorithm Independent of Net Ordering
BAO Hai-Yun,JING Tong,HONG Xian-long,CAI Yi-ci.A Novel Random Global Routing Algorithm Independent of Net Ordering[J].Chinese Journal of Computers,2001,24(6):574-579.
Authors:BAO Hai-Yun  JING Tong  HONG Xian-long  CAI Yi-ci
Abstract: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).
Keywords:global routing  global routing graph(GRG)  random route independent of net ordering(RINO)  layout  computer aided design(CAD)
本文献已被 CNKI 维普 万方数据 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号