一种T-树的优化设计与实现方法

一种求解RSMT布线问题的PSO算法陈秀华;朱自然【摘要】最小直角斯坦纳树(RSMT)问题是超大规模集成电路布线中的重要问题之一,是典型的NP困难组合优化问题.为了有效地解决超大规模集成电路布线中的RSMT问题,提出一种粒子群优化算法,借助直角Steiner树的一些性质,采用Steiner点编码方案,寻找优化的Steiner点位置以减少直角Steiner树的长度.对几组布线模型实例进行了仿真测试,表明了该算法的有效性.【期刊名称】《闽江学院学报》【年(卷),期】2014(035)005【总页数】6页(P39-44)【关键词】超大规模集成电路(VLSI);最小直角斯坦纳树;布线算法【作者】陈秀华;朱自然【作者单位】福建船政交通职业学院公共教学部,福建福州350007;福州大学数学与计算机科学学院,福建福州350116【正文语种】中文【中图分类】TP301.6布线问题是超大规模集成电路（VLSI）物理设计的关键环节之一.一个电路芯片会有大量的线网需要连接，同时对于每个线网，又有几百种甚至更多的布线方案.随着设计规模的不断增长，尤其是百万门级芯片的普遍应用，对VLSI布线问题的算法设计提出了巨大的挑战.VLSI布线问题中连接树的目标是连接树的总长度最短，对于多端线网的最佳布线结果是构造最小直角Steiner树（RSMT）［1］，该问题已被证明是一个NP完全问题［2］.研究者提出了许多基于智能优化技术的解决方法［3－8］，这些智能算法主要有模拟退火算法［9－10］，遗传算法［11－15］和蚁群算法［16－18］等.文献［3］提出了关于最小直角Steiner树的混合遗传算法，表明智能优化算法在解决这类问题中具有较好的应用前景.粒子群优化算法PSO（particle swarm optimization）是Kenney和Eberhart于1995年提出的一种基于种群搜索策略的自适应随机算法.它源于对鸟群和鱼群等群体运动行为的研究，是一种基于迭代的智能优化算法，可用于求解大部分的优化问题.与常规的遗传算法（GA）相比较，它具有算法简单，收敛速度快，且对目标函数要求少等特点，已成为一种重要的优化工具.文献［5］首先提出了一种用于解决VLSI布线问题的离散粒子群优化算法.此方法通过设计基于惩罚的适应度函数，引入遗传算法的变异和交叉算子，增加了种群的多样性并适当地扩展了粒子的寻优范围.文献［19］提出使用PSO算法求解RSMT问题，通过引入遗传算法中的变异算子来改进PSO的求解性能.本研究通过借助直角Steiner树的一些性质，采用Steiner点编码方案，寻找优化的Steiner点位置以减少直角Steiner树的长度，提出了一种求解RSMT布线问题的的粒子群优化算法.对几组布线模型实例进行了仿真测试，结果表明该算法的有效性.1.1 RSMT问题模型斯坦纳树（Steiner－tree）是一棵连接特定要求点（demand point）集合和一些斯坦纳点（Steiner points）的连接树.由于它连接树总长度比其他方法更小，常被用作总体布线中构造连接树的方法.因此，VLSI总体布线问题可以看作是在总体布线图中，在目标函数最优化的条件下，针对每个线网寻找一棵斯坦纳树的问题.通常典型的目标函数是所选择的连接树的总长度最小.定义1［20］一棵斯坦纳树（Steiner－tree）的长度为所有边长度之和，即l（ei）为边ei的长度.斯坦纳树的长度也称为费用.定义2［5］一棵斯坦纳树（Steiner－tree）中，若该斯坦纳树的每条边均为直角矩形边，则此Steiner－tree称为直角斯坦纳树（rectilinear Steiner tree，RST）.定义3 给定一个无向图G（V，E），一个要连接的端点集合N（N⊆V），最小Steiner树（SMT）就是一棵通过V中的点连接N中所有点的生成树，以边长最短为目标.与欧氏距离Steiner树不同，最小直角Steiner树（rectilinear Steinerminimal tree，RSMT）两点间的距离是直线距离，横轴距离和纵轴距离之和，即连线只有水平和垂直两种形式.定义4［20］总体布线问题就是给定一个网表N＝｛N1，N2，…，Nn｝，和一个总体布线图G＝（V，E），对∀Ni∈N，1≤i≤n，找到一棵斯坦纳树Ti，使得其中，L（Ti）为Ti的长度；U（ei）是通过通道边ei的线网数，如果ei在Ti中则xij＝1；否则xij＝0．在集成电路的布线问题中，多端线网的最佳连接就是构造最小直角斯坦纳树.1.2 问题分析最小直角Steiner树（RSMT）的相关性质：性质1 设RSMT有n个端点，则RSMT的Steiner点个数≤n－2.性质2［21］（Hanan定理）任意一棵最小直角Steiner树T的Steiner点均在经过T的水平线和竖直线的交点（Hanna网格）上，如图1所示.性质3［20］若分别用Ls和Lm表示最小直角Steiner树和最小生成树的长度，则在RSMT问题所给定的待连接的布线端点集合N中，通过这些端点分别各自引一条水平线和竖直线，这些线的交叉点就形成Hanan点集合［21］.从Hanan点集合中按一定规则选取的部分点作为Steiner点集合，这些Steiner点与普通的生成树构成了直角斯坦纳树.求最小Steiner树的关键是确定点集S，即s点的个数和位置.图2和图3给出了连接4个顶点的最小生成树（minimum spanning tree，MST）与其对应的最小直角斯坦纳树（RSMT）.由于RSMT问题已经被证明是NP完全的，解决这类问题的主要方法就是启发式算法或智能优化算法.2.1 粒子群优化算法（PSO）PSO算法是一种基于群体和适应度的智能优化技术［22］.在求解过程中，首先初始化一群粒子，将每个粒子个体抽象为一个在搜索空间中没有质量和体积的微粒（点），并在搜索空间中以一定的速度飞行［23］.每个粒子所处的位置都表示问题的一个解，它们通过不断调整自己的位置来搜索新解，同时记住个体最优解和全局最优解.空间中的粒子追随当前种群中的最优粒子运动，直到在整个解空间中搜索到最优解为止.对于每一次迭代，粒子根据个体最优解和全局最优解来动态调整自身的速度.粒子i的第j维根据式（1）和式（2）更新速度和位置：式中，w是惯性系数，c1和c2是学习因子，r1和r2是介于［0，1］之间的随机数，xtij是t时刻粒子i的第j维分量值，vtij是t时刻粒子i的第j维速度分量值.2.2 粒子的编码提出的求解最小直角Steiner树的PSO算法，是通过找出优化的s点位置来得到输入端点集合N的RSMT，根据性质1，若输入n个端点，则RSMT的s点最多有n－2个.因此粒子位置编码是由n－2个s点的坐标位置构成：X＝（x1，x2，x3，…，xi，…，xn－2），其中第i维数据xi表示这个s点在平面上的坐标．同时定义num，表示有效s点的数量，只有前num个s点才会被加入．与粒子位置的数据结构一样，速度v也是由n－2个二维向量组成.2.3 粒子的适应度函数位置与速度的加法运算实现了粒子位置变换，适应度函数在PSO算法中用于判断种群进化过程中粒子所在位置的优劣.提出的PSO算法是以最小代价生成树算法为基础，粒子适应度函数定义如下：式中，N是RSMT问题的端点集合，L是N用最小生成树算法——kruskal法确定的MST的长度，l（e）是边e的直线距离.由公式（2）可以观察到新的位置的某些s点可能不会落在Hanan网格上，因此在求适应度的时候，用离这些点最近的Hanan点表示它，即：S1为X中离每个有效s点最近的Hanan网格上的点组成的集合.2.4 粒子的初始化为了避免初始粒子位置分布过于集中，所有粒子每维数据随机选取一个Hanan点.初始化时，所有粒子的初始速度都设为0，第i个粒子s点数numi＝rand（1，n －2），在之后的迭代过程中粒子i的s点数采用如下方法动态更新：若个体最优解s点数为pbestnum，全局最优解s点数为gbestnum，则numi＝max （numi，pbestnum，gbestnum）.由于加入过多无用的s点反而会降低适应度值，因此在迭代过程中通过动态增加s点数量，能够有效地加快收敛速度.2.5 粒子的更新式（1）中的惯性系数w，表示原先的速度能在多大程度上得到保留，对全局搜索，较好的方法是在前期有较高的探索能力以得到合适的种子，防止迭代陷入局部最优解而发生早熟，而在后期有较高的求精能力以加快收敛速度．为此，可将w设定成随着进化而线性减少．文献［24］也指出w线性减少取得了较好的实验结果，经笔者多次实验，在算法中将w设成从0.9到0.4线性递减取得比较好效果.其中MaxNumber是算法的最大迭代次数.2.6 算法步骤以下是求解RSMT布线问题的PSO算法（PSO-RSMT）具体步骤：输入：n个端点的坐标位置；输出：RSMT的值和对应s点坐标位置；Step 1：读入数据集，生成Hanan点；Step 2：初始化算法参数并随机生成初始群；Step 3：评价各个粒子的适应度函数值，并初始化个体最优解Xpbest和全局最优解Xgbest；Step 4：根据式（4）计算惯性权值w，按式（1）更新粒子速度，按式（2）更新粒子位置，按2.5中的策略动态更新s点数量；Step5：重新评价各个粒子的适应度函数值，并更新各个粒子的个体最优解Xpbest；Step6：更新种群的全局最优解；Step7：若满足终止条件，则循环结束，否则返回Step4.PSO算法模拟了群体模型中的信息共享机制，由于粒子的运动紧跟当前最优解，并且惯性系数可以调整其搜索能力，防止早熟，因此在搜索过程中用较小规模的种群就可以收敛到最优解.表1是采用本文PSO算法解RSMT的结果与用经典遗传算法［15］解RSMT的结果比较，每个输入端点的横纵坐标取0到10 000上的随机数.两种算法都用Microsoft Visual C＋＋编程实现，在Windows XP平台上运行通过，可以看到PSO算法在运行结果要比遗传算法好，速度也更快.（1）在RSMT长度上，PSO算法在输入端点数为9、12和15时，得到的结果与遗传算法相同，但是当输入端点数为18和20时，均得到了明显的优化，分别减少了0.88%和2.46%.（2）在使用时间上，对于表1的所有实例，PSO算法相较于遗传算法均有明显缩短，并且当输入端点数为9和12时，时间缩短量超过了50%，分别是69%和70%.在深入分析最小直角Steiner树（RSMT）问题的基础上，提出了一种基于粒子群优化的算法.采用Steiner点编码方案来实现粒子的编码，引入s点数量动态调整策略，以期加快收敛速度，并通过寻找优化的Steiner点位置来减少RSMT的长度.对几组布线模型实例进行了仿真实验，实验结果验证了算法在RSMT长度和运行时间方面都具有较好的性能.【相关文献】［1］Hwang F K，Richards D S，W inter P.The Steiner tree problem［M］.Amsterdam：North-Holland，1992.［2］Garey M R，Johnson D S.The rectilinear Steiner tree problem is NP－complete ［J］.SIAM Journal on Applied Mathematics，1977，32（4）：826-834.［3］杨昌玲，严晓浪.基于树型编码的MRST混合遗传算法及其并行处理［J］.微电子学，1999，29（2）：89－95.［4］杨文国，郭田德.求解最小Steiner树的蚁群优化算法及其收敛性［J］.应用数学学报，2006，29（2）：352－361.［5］刘耿耿，王小溪，陈国龙，等.求解VLSI布线问题的离散粒子群优化算法［J］.计算机科学，2010，37（10）：197－201.［6］Zhang Y H，Chu C.Interleaved global routing and detailed routing for ultimate routability［C］／／Design Automation Conference（DAC）.San Francisco：IEEE，2012：597－602.［7］Huang TW，Ho T Y，A two－stage ILP－based droplet routing algorithm for pin－constrained digital microfluidic biochips［J］.IEEE Transactions on Computer－Aided Design of Integrated Circuits and Systems，2011，30（2）：215－228.［8］Zhang Y，Chu C.RegularRoute：an efficient detailed routerwith regular routing patterns［C］／／International Symposium on Physical Design.Santa Barbara：DBLP，2011：146－151.［9］Kirkpatrick S，Gelatt C D，Vecchi M P.Optimization by simulated annealing［J］.Science，1983，220（4 598）：671－680.［10］Cetin A.E，Weerackody V.Design of vector quantizers using simulated annealing ［J］.IEEE Transactions on Circuits and Systems，1988，35（12）：1 550.［11］Holland JH.Adaptation in natural and artificial systems：an introductory analysis with applications to biology，control，and artificial intelligence［M］.Cambridge：TheMIT Press，1995.［12］Goldberg D E.Genetic algorithms in search optimization and machine learning ［M］.Boston：Addison－Wesley，1989.［13］Melanie Mitchell.An introduction to genetic algorithms［M］.Cambridge：The MITPress，1996.［14］Anderson C A，Jones K F，Ryan J.A two－dimensional genetic algorithm for the traveling salesman problem［J］. Complex Syst，1991，5：327－333.［15］Griffith J.Closing the gap：near－optimal Steiner trees in polynomial time［J］.IEEE Trans on CAD，1994，13（11）：1351－1365.［16］Colorni A，Dorigo M，Maniezzo V.Distributed optimization by ant colonies［C］／／Proc of ECALL91—Eur Conf Artificial Life.Paris：Elsevier，1991：134－142.［17］Dorigo M，Gambardella L M.Ant colony system：a cooperative learning approachto the traveling salesman problem［J］.IEEE Transactions on Evolutionary Computation，1997，1（1）：53－66.［18］Hulldobler B，Wilson E O.The ants［M］.Berlin：Springer－Verlag，1990.［19］Khan A，Laha S，Sarkar SK.A novel particle swarm optimization approach for VLSI routing［C］／／Advance Computing Conference（IACC）.2013 IEEE 3rd International，2013：258－262.［20］徐宁，洪先龙.超大规模集成电路物理设计理论与算法［M］.北京：清华大学出版社，2009：167－177.［21］Hanan M.On steiner’s problem with rectilinear distance［J］.SIAM Journal of Applied Mathematics，1996，14（2）：255—265.［22］杨维，李歧强.粒子群优化算法综述［J］.中国工程科学，2004，6（5）：87－94.［23］郭文忠，陈国龙，陈振.离散粒子群优化算法综述［J］.福州大学学报：自然科学版，2011，39（5）：631－638.［24］Shi Y，Eberhart R C.Empirical study of particle swarm optimization［C］／／Proc of the 1999 Congress on Evolutionary Computation.Piscataway：IEEE Service Center，1999：1 945－1 950.。