基于多阶段拆线重布的总体布线算法  

A Global Routing Algorithm Based on Multistage Rip-up and Reroute

作　　者：朱自然 陈建利[1] 朱文兴[1] Zhu Ziran;Chen Jianli;Zhu Wenxing(Center for Discrete Mathematics and Theoretical Computer Science, Fuzhou University, Fuzhou 350116)

机构地区：[1]福州大学离散数学与理论计算机科学研究中心,福州350116

出　　处：《计算机辅助设计与图形学学报》2016年第11期2000-2008,共9页Journal of Computer-Aided Design & Computer Graphics

基　　金：国家自然科学基金(11501115;61672005);福建省自然科学基金(2014J01228)

摘　　要：超大规模集成电路总体布线是集成电路物理设计的关键环节之一,对芯片的可布线性、线长、通孔数等性能指标有重大影响.针对拆线重布方法容易陷入局部最优解的问题,提出一种基于多阶段拆线重布的总体布线算法.该算法根据不同布线阶段对最小化溢出值和最小化线长这两个目标的侧重点不同,通过构造不同的布线代价函数、确定不同的布线顺序、选取不同的布线模型及布线算法对线网进行拆线重布,使得基于多阶段拆线重布的总体布线算法可以有效地跳出局部最优解,快速地提高布线质量.采用ISPD08总体布线竞赛中的标准测试例子集的实验结果表明,与NTUgr,NTHU-Route2.0和NCTU-GR2.0相比,所提出的总体布线算法在平均总溢出方面分别减少了1.4%,2.4%和21.5%,在平均运行时间方面分别快了10.4倍,1.6倍和1.3倍.Global routing is a crucial step in very large scale integration (VLSI) physical design, which will affectroutability, wirelength and the number of vias of a chip. In this paper, a multistage rip-up and reroute based globalrouting algorithm is presented to reduce the probability of getting stuck in local optima of traditional rip-up andreroute routing algorithms. In each rip-up and reroute stage, the proposed method focuses on different aspects ofoverflow minimization and wirelength minimization. It constructs different cost functions, determines differentorderings for rip-up and reroute, and selects different routing models and algorithms to rip-up and reroute themarked nets. Using the strategies above, the multistage rip-up and reroute based global routing algorithm can escapelocal optima effectively, and improve routing quality and speed. Experimental results on ISPD 2008 globalrouting contest benchmarks show that the proposed global routing algorithm can obtain less total overflow thanthose of NTUgr, NTHU-Route2.0 and NCTU-GR2.0 by 1.4%, 2.4% and 21.5%, respectively; and runs 10.4 times,1.6 times and 1.3 times faster than NTUgr, NTHU-Route2.0 and NCTU-GR2.0, respectively.

关 键 词：VLSI 总体布线 可布线性 多阶段拆线重布 

分 类 号：TP302.1[自动化与计算机技术—计算机系统结构]