高级检索

基于多阶段优化的高质量总体布线算法

High Quality Global Routing Algorithm Based on Multi-Stage Optimization

  • 摘要: 总体布线是VLSI物理设计中关键的一个环节.针对现有总体布线算法的布线容量利用率低和布线结果容易陷入局部最优的问题,提出一种基于多阶段优化的高质量总体布线算法.首先在预连接阶段和全局考量下的布线重组阶段中引入虚拟容量动态调整策略,提高布线容量利用率;然后在布线重组阶段引入布线子区域自适应扩展策略,缩小算法全局搜索的空间,提高算法的布线效率;最后采用A*算法启发式搜索并结合粒子群算法全局搜索的能力,避免算法在布线过程中单一地选择最短路径,陷入局部最优.与现有总体布线算法在ISPD基准电路上的实验结果表明,所提算法的布线结果取得了6.0%~22.8%的线长优化.

     

    Abstract: Global routing is a crucial step in VLSI physical design. To address the problems that the low utilization rate of capacity and easy to fall into local optimum in the existing global routing algorithms, a high-quality global routing algorithm based on multi-stage optimization is proposed. First, the virtual capacity dynamic adjustment strategy is introduced in the pre-connection stage and the routing reorganization stage to improve the utilization rate of capacity. Then, in the routing reorganization stage, the routing subarea adaptive expansion strategy is proposed to narrow the search space and improve the routing efficiency. Finally, the A* algorithm heuristic search is combined with the global search capability of the particle swarm algorithm to avoid the algorithm to choose the shortest path in the routing process, and thus avoid the algorithm to fall into the local optimum. Experimental results comparing with existing global routing algorithms on ISPD benchmark circuits show that the routing results of proposed algorithm reduce the wirelength by 6.0% to 22.8%.

     

/

返回文章
返回