VLSI中高性能X结构多层总体布线器  

A High Performance X-architecture Multilayer Global Router for VLSI

作　　者：刘耿耿[1,2,3] 庄震 郭文忠 陈国龙[1] LIU Geng-Geng;ZHUANG Zhen;GUO Wen-Zhong;CHEN Guo-Long(College of Mathematics and Computer Sciences,Fuzhou University,Fuzhou 350116;Key Laboratory of Net-work Computing and Intelligent Information Processing,Fujian Province,Fuzhou 350116;Key Laboratory of Spatial Data Mining&Information Sharing,Ministry of Education,Fuzhou 350116)

机构地区：[1]福州大学数学与计算机科学学院,福州350116 [2]福建省网络计算与智能信息处理重点实验室,福州350116 [3]空间数据挖掘与信息共享教育部重点实验室,福州350116

出　　处：《自动化学报》2020年第1期79-93,共15页Acta Automatica Sinica

基　　金：国家重点基础研究发展计划(973计划)(2011CB808000);国家自然科学基金(61877010,11501114);福建省自然科学基金(2019J01243);福建省科技创新平台项目(2014H2005,2009J1007)资助~~

摘　　要：X结构带来物理设计诸多性能的提高,该结构的引入和多层工艺的普及,使得总体布线算法更复杂.为此,在XGRouter布线器的基础上,本文设计了三种有效的加强策略,包括:1)增加新类型的布线方式;2)粒子群优化(Particle swarm optimization,PSO)算法与基于新布线代价的迷宫布线的结合;3)初始阶段中预布线容量的缩减策略,继而引入了多层布线模型,简化了XGRouter的整数线性规划模型,最终构建了一种高性能的X结构多层总体布线器,称为ML-XGRouter.在标准测试电路的仿真实验结果表明,ML-XGRouter相对其他各类总体布线器,在多层总体布线中最重要的优化目标|溢出数和线长总代价两个指标上均取得最佳.The introduction of X-architecture can improve many performance standards of the chip in physical design.The proposed X-architecture and pervasive multilayer technology make the global routing problem more complex.For this reason,this paper presents the following enhancements based on XGRouter:1)the introduction of some new types of routing;2)the combination of particle swarm optimization(PSO)algorithm and maze routing with new routing cost;3)a reduction strategy of routing capacity in the initial stage.Then the multilayer routing model is introduced and the integer linear programming model of XGRouter is simpli ed.Finally,a high performance X-architecture multilayer global router,namely ML-XGRouter,is proposed.The experimental results on benchmark circuits have shown that our proposed ML-XGRouter is e ective and superior to state-of-the-art multilayer routing algorithms on over°ows and the total cost of wirelength,which are the two most important optimization goals for the multilayer global routing problem.

关 键 词：X结构 多层布线 超大规模集成电路 总体布线 粒子群优化 

分 类 号：TN47[电子电信—微电子学与固体电子学]