VLSI中X结构多层总体布线问题：X结构带来物理设计诸多性能的提高,该结构的引入和多层工艺的普及,使得总体布线算法更复杂，目前缺乏一种解决非曼哈顿结构下多层总体布线问题的有效算法。
鉴于总体布线是VLSI物理设计中极为重要的一部分,学者们提出很多有效的算法。（1）大部分总体布线算法都是以曼哈顿结构为模型基础开展相关工作,而基于曼哈顿结构的优化策略在进行互连线线长优化时,由于绕线方向只能为水平和垂直,其优化能力受限。因此,研究人员开始尝试以非曼哈顿结构为基础模型进行布线,实现芯片整体性能的优化。（2）此外,随着集成电路设计进入纳米领域,布线层数增加,使电路的性能和密度得到了很大的提高,因此多层布线应运而生,并且引起了诸多研究机构的广泛关注。
而现有关于非曼哈顿结构总体布线问题的研究中,仅局限于单层结构总体布线问题的研究,尚未开展考虑到非曼哈顿结构、多层结构两个条件的总体布线算法研究。因此,本文以X结构作为非曼哈顿结构的代表,基于整数规划模型(Integer Linear Programming,ILP)和粒子群优化算法(Particle Swarm Optimization,PSO) ,提出了三种有效的加强策略 ,从而构建了一种高性能X结构多层总体布线器，ML-XGRouter。
（1）ML-XGRouter采用“增加新型走线方式”策略,增加新型走线方式有助于初始阶段中放弃连接的线网集在主阶段的布通率。
在本文主阶段中,设计了新型走线方式,针对水平或垂直关系的线网采用图1(a)和1(b)的两种连接方式,而针对450或1350关系的线网(N2)采用图1(c) 的连接方式,通过新增布线方式,主阶段可合理避开拥挤区域。实验结果表明通过采用“增加新型走线方式”策略相对未采用该策略的总体布线结果在总溢出数方面取得了16.63%的减少率，从而表明该策略有助于主阶段尽可能多连接线网，从而提高布通率。
图1 “增加新型走线方式”策略
（2）ML-XGRouter采用“PSO与迷宫算法的结合”策略, 将基于新布线代价的迷宫布线策略移至主阶段中每次box区域内的PSO布线后,可有效提高当前box未布通线网集的布通率。
先前工作的迷宫布线是放在主阶段之后,容易堆积非常多的未布通线网,严重影响到PSO算法的求解质量.如图2所示, P1和P2在box0的阶段中,由于灰色拥挤区域的存在,P1和P2在采用先前工作的边接连方式,是不能在box0阶段完成布线.而如果等到box0扩张到整个芯片的阶段,P1和P2可能要采用图2的实线连接,占用更多的布线资源,从而导致溢出数的增加.而ML-XGRouter会在box0布线结束后,立即引入迷宫布线连接PSO未能布线的线网,即采用图2的虚线进行连接,尽可能占用box0附近的资源 ,可有效减少布线资源的冗余占用,有效提高布线的完成率。实验结果表明采用“PSO与迷宫算法的结合”策略相对未采用该策略的总体布线结果在总溢出数取得了77.01%的大幅度减少率,表明该策略有助于在主阶段合理使用线网附近的布线资源,从而产生更少的溢出。
图2 “PSO与迷宫算法的结合”策略
（3）ML-XGRouter采用“初始布线阶段的布线容量缩减”策略, 将初始布线阶段的布线容量缩减到原容量的一半,使得部分线网留在主阶段用PSO算法布线,从而可有效利用PSO算法的全局优化能力,同时进一步加强上述（1）和（2）两种策略的优化效果。
如图3所示,假设初始布线中线网的布线顺序为N1(包含N11和N12引脚),N2(包含N21和N22引脚),N3(包含N31和N32引脚),布线边的最大容量为2.采用先前工作的布线策略,即将N1和N2优先连接,而在主阶段中N3的连接需要占用非常多的布线资源,如图3(a)所示。但如果采用本文的“初始布线阶段的布线容量缩减”策略,预留一半的布线资源,初始布线只连接N1,而N2和N3则留在主阶段处理,PSO算法可从全局的角度去衡量N2和N3的布线方式,从而得到图3(b)的方案,以更少的布线资源完成N1,N2和N3的连接。
(a) 未采用“初始布线阶段的布线容量缩减”策略
(b) 采用“初始布线阶段的布线容量缩减”策略 图3 “初始布线阶段的布线容量缩减” 策略
ML-XGRouter是第一次求解非曼哈顿结构下多层总体布线问题。实验结果表明本文提出的三种策略对溢出数和线长总代价优化的有效性。最终的实验结果表明ML-XGRouter在两类基准电路上均可取得相对当前总体布线器而言最佳的溢出数和线长总代价。此外，时延目前也是VLSI芯片设计中一个非常重要的指标，未来的工作中我们将基于Elmore延迟模型进一步研究时延驱动的总体布线算法。
文章信息：刘耿耿, 庄震, 郭文忠, 陈国龙. VLSI中高性能X结构多层总体布线器. 自动化学报, 2020, 46(1): 79-93.
