VLSI中高性能X结构多层总体布线器
发布时间：2020-12-15 21:05
X结构带来物理设计诸多性能的提高,该结构的引入和多层工艺的普及,使得总体布线算法更复杂.为此,在XGRouter布线器的基础上,本文设计了三种有效的加强策略,包括:1)增加新类型的布线方式; 2)粒子群优化（Particle swarm optimization, PSO）算法与基于新布线代价的迷宫布线的结合; 3)初始阶段中预布线容量的缩减策略,继而引入了多层布线模型,简化了XGRouter的整数线性规划模型,最终构建了一种高性能的X结构多层总体布线器,称为ML-XGRouter.在标准测试电路的仿真实验结果表明, ML-XGRouter相对其他各类总体布线器,在多层总体布线中最重要的优化目标—溢出数和线长总代价两个指标上均取得最佳.
【文章来源】：自动化学报. 2020年01期 北大核心
【文章页数】：15 页
【部分图文】：
总体布线图
在XGRouter的初始布线阶段中,针对分解后两引脚所构成的直线斜率值为0,-1,+1和∞的线网(此类线网集称为NA),如果采用该直线连接两引脚,不会超过连接边的容量,则用该直线连接该两端线网.但若造成溢出的情况,如图2所示,则放弃连接该类两端线网(此类线网集称为NC),并放在主阶段进行连接.而在主阶段其连接仍采用图2所示的方式,将导致这些N C线网在主阶段仍不可连接,从而导致非常多未能连接的线网,严重影响PSO算法的求解性能.因此,在本文主阶段中,针对NC1设计了新型走线方式,针对水平或垂直关系的线网采用图3(a)和3(b)的两种连接方式,而针对45?或135?关系的线网(NC2)采用图3(c)的连接方式,通过新增布线方式,主阶段可合理避开拥挤区域.
本文将未采用和采用E1策略的总体布线算法在ISPD07的基准电路上[22]进行实验对比,如表1所示.采用E1策略相对未采用E1策略(表中用E0表示)的总体布线结果在总溢出数(TOF)方面取得了16.63%的减少率,表明E1策略有助于主阶段尽可能多连接NC,提高布通率.虽然增加了少量的线长总代价(TWL),但针对溢出数带来可观的优化,从而表明E1策略的有效性.2.2.2 PSO与迷宫算法的结合策略(E2策略)
【参考文献】：
期刊论文
[1]Weather Prediction With Multiclass Support Vector Machines in the Fault Detection of Photovoltaic System[J]. Wenying Zhang,Huaguang Zhang,Jinhai Liu,Kai Li,Dongsheng Yang,Hui Tian. IEEE/CAA Journal of Automatica Sinica. 2017(03)
[2]An Optimized Oxygen System Scheduling With Electricity Cost Consideration in Steel Industry[J]. Zhongyang Han,Jun Zhao,Wei Wang. IEEE/CAA Journal of Automatica Sinica. 2017(02)
[3]A Chance Constrained Optimal Reserve Scheduling Approach for Economic Dispatch Considering Wind Penetration[J]. Yufei Tang,Chao Luo,Jun Yang,Haibo He. IEEE/CAA Journal of Automatica Sinica. 2017(02)
[4]基于变换函数与填充函数的模糊粒子群优化算法[J]. 吕柏权,张静静,李占培,刘廷章. 自动化学报. 2018(01)
[5]MLXR: multi-layer obstacle-avoiding X-architecture Steiner tree construction for VLSI routing[J]. Xing HUANG,Wenzhong GUO,Genggeng LIU,Guolong CHEN. Science China(Information Sciences). 2017(01)
[6]粒子群优化算法的性能分析和参数选择[J]. 王东风,孟丽. 自动化学报. 2016(10)
本文编号：2918901
【文章来源】：自动化学报. 2020年01期 北大核心
【文章页数】：15 页
【部分图文】：
总体布线图
在XGRouter的初始布线阶段中,针对分解后两引脚所构成的直线斜率值为0,-1,+1和∞的线网(此类线网集称为NA),如果采用该直线连接两引脚,不会超过连接边的容量,则用该直线连接该两端线网.但若造成溢出的情况,如图2所示,则放弃连接该类两端线网(此类线网集称为NC),并放在主阶段进行连接.而在主阶段其连接仍采用图2所示的方式,将导致这些N C线网在主阶段仍不可连接,从而导致非常多未能连接的线网,严重影响PSO算法的求解性能.因此,在本文主阶段中,针对NC1设计了新型走线方式,针对水平或垂直关系的线网采用图3(a)和3(b)的两种连接方式,而针对45?或135?关系的线网(NC2)采用图3(c)的连接方式,通过新增布线方式,主阶段可合理避开拥挤区域.
本文将未采用和采用E1策略的总体布线算法在ISPD07的基准电路上[22]进行实验对比,如表1所示.采用E1策略相对未采用E1策略(表中用E0表示)的总体布线结果在总溢出数(TOF)方面取得了16.63%的减少率,表明E1策略有助于主阶段尽可能多连接NC,提高布通率.虽然增加了少量的线长总代价(TWL),但针对溢出数带来可观的优化,从而表明E1策略的有效性.2.2.2 PSO与迷宫算法的结合策略(E2策略)
【参考文献】：
期刊论文
[1]Weather Prediction With Multiclass Support Vector Machines in the Fault Detection of Photovoltaic System[J]. Wenying Zhang,Huaguang Zhang,Jinhai Liu,Kai Li,Dongsheng Yang,Hui Tian. IEEE/CAA Journal of Automatica Sinica. 2017(03)
[2]An Optimized Oxygen System Scheduling With Electricity Cost Consideration in Steel Industry[J]. Zhongyang Han,Jun Zhao,Wei Wang. IEEE/CAA Journal of Automatica Sinica. 2017(02)
[3]A Chance Constrained Optimal Reserve Scheduling Approach for Economic Dispatch Considering Wind Penetration[J]. Yufei Tang,Chao Luo,Jun Yang,Haibo He. IEEE/CAA Journal of Automatica Sinica. 2017(02)
[4]基于变换函数与填充函数的模糊粒子群优化算法[J]. 吕柏权,张静静,李占培,刘廷章. 自动化学报. 2018(01)
[5]MLXR: multi-layer obstacle-avoiding X-architecture Steiner tree construction for VLSI routing[J]. Xing HUANG,Wenzhong GUO,Genggeng LIU,Guolong CHEN. Science China(Information Sciences). 2017(01)
[6]粒子群优化算法的性能分析和参数选择[J]. 王东风,孟丽. 自动化学报. 2016(10)
本文编号：2918901
本文链接：https://www.wllwen.com/kejilunwen/dianzigongchenglunwen/2918901.html
