针对VLSI布线的多层X结构斯坦纳最小树构建算法
2016-03-15黄昉菀陈志盛刘耿耿
黄昉菀, 陈志盛, 刘耿耿
(1. 福州大学至诚学院， 福建 福州 350002；(2. 福州大学数学与计算机科学学院， 福建 福州 350116)
针对VLSI布线的多层X结构斯坦纳最小树构建算法
黄昉菀1, 2, 陈志盛2, 刘耿耿2
(1. 福州大学至诚学院， 福建 福州 350002；(2. 福州大学数学与计算机科学学院， 福建 福州 350116)
考虑到粒子群优化算法具有非常出色的全局优化能力， 针对X结构布线问题的复杂性提出了X结构下的多层Steiner最小树构建算法. 实验结果表明， 该算法可以在合理的时间内取得优异的布线解.
X结构； 多层布线； Steiner树； 粒子群优化
0 引言
Steiner最小树在图论领域中是最重要的数学模型之一， 已经在许多研究领域中得到广泛运用， 并且作为X结构下多层Steiner最小树(multilayer X-architecture Steiner minimal tree， ML-XSMT)构建问题的基本模型， 成为布线中多端线网的最佳连接模型[1-2]. 在超大规模集成电路设计中ML-XSMT问题考虑了X结构和多层这2个条件.
此外， 近年来粒子群优化算法成为智能计算领域一个非常热门的群智能算法， 已被成功地应用到了诸多优化领域[3]. 在粒子群算法中， 每一个优化问题的解看作是搜索空间中的一只鸟， 即“粒子”. 首先初始化种群， 在可行解的空间中随机初始化一群粒子， 每个粒子都为优化问题的一个可行解， 并用合适的目标函数评价其适应度值. 每个粒子都在解空间中运动， 并由速度决定其飞行的方向和距离， 通常粒子追随当前的最佳粒子在解空间中进行搜索. 通过每一代群体的位置更新产生新的群体. 这样可以保证群体的优良性， 并加快寻优速度， 不断地搜索全局最优个体.
1 问题模型
1.1 X结构下VLSI多层斯坦纳最小树构建问题模型
ML-XSMT问题的数学模型可描述如下： 给定布线层的层数N和单个通孔的代价Cv， 设定P={P1,P2,P3,…,Pn}为多层布线网络上需要连接的一组引脚， 其中每个引脚Pi对应一个三维坐标(xi,yi,zi)， 分别表示引脚的横坐标、 纵坐标和层数， 如图1所示. 本研究需要构建一棵满足以下条件的多层X结构斯坦纳最小树来连接集合P中的所有引脚： 1)布线树的每条边需要符合X结构的连接方式； 2)通道是用来连接两个不同布线层的边； 3)最终得到的布线总代价是最小的. 例如图2所示是通孔数为2的ML-XSMT问题的一种有效连接方式.
1.2X结构连接模型
在λ-几何学中， 布线方向被定义为iπ/λ. 其中i是任意整数， 不同的正整数λ值表示不同的布线结构. 当λ的值被设置为4时， 即布线方向为iπ/4， 它包括0°、 45°和90°、 135°走线方向， 被称为八角(或X)布线结构.
图3定义了多层芯片环境下4种不同的X结构走线模型. 其中：P1，P2为线段的两个端点;S1为P1所在布线层的斯坦纳点;S2为P2所在布线层的斯坦纳点.S1和S2之间的虚线表示通孔连接， 如果P1和P2位于相同布线层， 则此时S1和S2是重合点， 无需用通孔连接.
2 算法实现
2.1 粒子编码策略
由于要考虑X结构和多层布线结构这两个条件， 因此采用边点对编码模式. 这个编码策略可以满足完整性和非冗余性原则[4]. 用一组生成树的边来表示一棵候选的Steiner树， 生成树的每条边选择一种走线方式来选取斯坦纳点， 从而转换成X结构的布线边. 走线方式spc表示边的斯坦纳点的选取方式， spc的值可取0， 1， 2， 3， 分别代表图3所定义的四种走线选择. 每条布线边采用4位数字编码来表示， 前三个数字(前两位数字代表了布线边两个端点的引脚标号， spc的第三位表示Steiner点的选取方式)可以表示一条布线边， 最后一位走线状态label表示布线边产生的通孔数量， 还有一个额外的数值为粒子的适应度值.
2.2 预处理策略
根据多层X结构斯坦纳最小树的构建过程， 首先构建一棵三维的最小生成树， 然后将这个基础构架转换成多层X结构斯坦纳树. 但是， 每条最小生成树的边有四种不同的X结构布线走位. 因此， 需要评估哪种布线走位的选择会使得该转换后的边的布线代价最小. 而且， 在算法每次的迭代过程中， 都要计算粒子的适应度值， 这就需要重新判断布线树各边的布线走位以及产生的通孔数量. 为此， 预先计算了三维最小生成树的所有布线边的X结构走位方式的信息并存储在数组当中， 在算法迭代过程中直接查询所需要的数据， 减少计算次数， 加快算法的速度.
2.3 适应度函数的定义及计算
构建X结构下超大规模集成电路的多层Steiner树的布线总代价不仅包括布线树的总长， 还需要找到合适的位置来形成通孔并计算通孔的布线代价. 本研究应用了边点对的编码方式， 则引脚i和引脚j的距离计算如下：
(1)
(2)
在多层布线条件下， 一定会产生通孔的， 而通孔数量是超大规模集成电路中一项至关重要的优化指标， 但是可以采用合理而有效的策略在一定程度上减少通孔的数量. 因此， 通过运用惩罚机制来惩罚通孔的产生. 惩罚函数为：
(3)
其中：P(X,Q)为惩罚函数;Q×S(X)为惩罚项;Q是惩罚因子且取值的极限为无穷大; 惩罚函数中的N(X)通常表示没有考虑约束条件下得到的解的代价;S(X)表示在约束条件下得到的解的代价.N(X)和S(X)也可以表示其他的含义， 但是它们可能取值会相同.
2.4 粒子的更新公式
基本的粒子群优化算法的粒子更新公式不再适用于解决本研究所提出的离散优化问题. 因此本研究引入交叉和变异算子， 并结合并查集思想来构建多层X结构Steiner最小树.
改进后的粒子更新公式为：
(4)
上式中， 粒子的速度更新公式为：
(5)
其中: 惯性权重w表示粒子间变异操作的概率;r1是0至1内的随机数;M表示变异操作.
变异操作是从生成树中随机选择一条边进行变异， 然后再随机生成一条能使该生成树保持连接状态且无环路的布线边. 当生成树的一条边被去掉时， 所有的引脚点也因此分到两个集合内. 本研究应用并查集来记录所有点的情况， 然后从两个集合内分别随机选择一个点来相互连接从而构建新的生成树, 变异操作如图4.M1是进行删除的边，M2是新生成的边.
粒子的自身经验感知公式：
(6)
其中: 加速因子c1表示粒子和个体历史最优解进行交叉操作的概率;r2是0至1的随机数;C表示交叉操作.
粒子的全局经验感知公式：
(7)
其中: 加速因子c2表示粒子和全局最优解进行交叉操作的概率;r3是0至1的随机数;C表示交叉操作.
当进行交叉操作时， 首先运用并查集划分两棵已从小到大排序好边的生成树, 并从中选择相同的边放到一个集合. 剩下的不同边便放到另一集合内， 第一个集合中的边直接做为新生成树的边. 最后， 重复地从另一个集合内随机选择一条边来加入到新生成树. 交叉操作如图5所示.
2.5 精炼策略
对于Steiner树一个度为d的结点P1(此处为2度顶点)， 这d条X结构布线路径的组合便可以看做是结点P的连接结构. 每条路径都有四种不同的X结构走线方式， 所以对于点P1就存在16种不同的连接结构， 详见图6. 显而易见， 如果P1P3采用“0选择”或者“3选择”， 那样就无法和边P1P2的X结构布线路径共享任何的布线资源. 当P1P3采用“1选择”走线方式来连接时， 如果P2的横坐标在P1横坐标和S12横坐标之间， 则可见图6(a)便是P1的最佳连接结构. 另外， 如图6(b)所示， 当P2的横坐标在S12横坐标和S22横坐标之间时， 点S22是边P3P1为“2选择”的X结构连接方式时的Steiner点. 在这种情况下，P1的最佳连接结构取决于P2S1和P2S2+S2S12的值(这里的P2S1、P2S2和S2S12表示的是两点间的距离)，S1是边P2P1为“1选择”的X结构连接方式时的Steiner点，S2是边P2P1为“2选择”的X结构连接方式时的Steiner点. 例如， 如果P2S1 表1给出了在算法中运用精炼策略和未使用精炼策略在相同的运行环境下， 通过18组不同的测试数据， 在线长优化方面的实验对照情况. 表1 精炼策略的实验验证对比Tab.1 The experimental verification and comparison of refinement strategy 续表 数据(ind1～ind5)是来自于美国新思科技公司的工业测试数据， 数据(rt1～rt5)是来自于其他工业标准测试集数据， 数据(rd1～rd8)是基于二维标准测试集改进随机生成的. 表格的第二列为每组测试数据的引脚数和层数的设定值. 精炼策略对于本研究所提出的构建算法的最终布线质量具有重要作用， 通过对比在算法中运用精炼策略前后的布线总代价， 从而可知精炼策略的高效性. 表1列举了不同引脚数和布线层数在通孔代价都为3的条件下， 运用和未运用精炼策略情况下的不同的布线总代价. 使用精炼策略来构建X结构多层Steiner最小树能获得1.19%～7.29%的线长优化率. 由于精炼策略能充分利用未被使用的布线资源， 通过改变布线树的连接结构来极大地增加共享的布线长度， 所以能有效减少线长. 本研究结合遗传算法中的变异算子和交叉算子， 并基于离散粒子群优化算法提出一个有效的算法来构建多层X结构Steiner最小树. 粒子群优化算法在算法的迭代过程生成的解能不断自我提升并进行信息的交互， 从而使得个体不断向最优解收敛并且具有较快的收敛速度. 此外， 本研究算法中引入打破传统的非曼哈顿布线结构[6]， 该结构巧妙地通过45°和135°的走线方向极大缩短了布线长度. 实验结果表明, 本研究算法提出的精炼策略在原算法的基础上对于布线总代价具有较好的优化作用. [1] 徐宁， 洪先龙.超大规模集成电路物理设计理论与算法[M]. 北京： 清华大学出版社， 2009. [2] TEIG S.The X architecture： not your fathers diagonal wiring[C]//Proceedings of the 2002 International Workshop on System-level Interconnect Prediction. San Diego: IEEE, 2002: 33-37. [3] EBERHART R, KENNEDY J. A new optimizer using particles warm theory[C]//Proceedings of the 6th International Symposium on Micro Machine and Human Science. Los Alamitos: IEEE Computer Society Press, 1995: 39-43. [4] GUO W Z, LIU G G, CHEN G L,etal. A hybrid multi-objective PSO algorithm with local search strategy for VLSI partitioning[J]. Front Comput Sci, 2014, 8(2): 203-216. [5] LIN C W, HUANG S L, HSU K C,etal. Multilayer obstacle-avoiding rectilinear steiner tree construction based on spanning graphs[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2008, 27(4): 643-653. [6] KOH C K, MADDEN P H. Manhattan or non-manhattan?: a study of alternative VLSI routing architectures[C]//Great Lakes Symposium on VLSI.[S.l.]: ACM, 2002: 47-52. (责任编辑： 林晓) Multi-layer X-architecture steiner tree construction algorithm for VLSI routing HUANG Fangwan1, 2, CHEN Zhisheng2, LIU Genggeng2 (1. Zhicheng College， Fuzhou University， Fuzhou， Fujian 350002， China;(2. College of Mathematics and Computer Science， Fuzhou University， Fuzhou， Fujian 350116， China) Because the complexity of X-architecture routing problem. Considering particle swarm optimization (PSO) algorithm has very excellent global optimization capability, this paper proposes a PSO based algorithm for multilayer X-architecture Steiner tree construction. Experimental results show that the proposed algorithm can achieve great results with reasonable runtime. X-architecture； multilayer routing； Steiner tree； particle swarm optimization 10.7631/issn.1000-2243.2016.05.0639 1000-2243(2016)05-0639-05 2015-05-18 黄昉菀(1980-)， 讲师， 主要从事智能信息技术研究，hfw@fzu.edu.cn 福建省教育厅科技资助项目(JA13356)； 国家自然科学基金资助项目(11501114) TP39 A3 实验验证分析
4 结论
