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