基于图论的VLSI中最小斯坦纳树问题及其改进算法

超大规模集成电路(VLSI)中,对于多端线网的最佳布线结果是构造最小直角斯坦纳树,该问题是典型的NP组合优化问题.利用图论中直角斯坦纳树的性质,在采用斯坦纳点编码方案寻找优化点位置的基础上,增加粒子趋同性判定及惯性权重系数调整策略,提出改进的粒子群优化算法,对一些实例模型进行了仿真测试,表明该算法的效果良好.

两种斯坦纳问题的近似算法

本文对图的斯坦纳问题和直角斯坦纳问题各设计了一个近似算法。算法不是以构造为主，而是先利用一简单方法构造出斯坦纳树，再用回路修改法对其进行全面改造，从而克服了以局部优化为目标的局限性。

一种求解RSMT布线问题的PSO算法

最小直角斯坦纳树(RSMT)问题是超大规模集成电路布线中的重要问题之一,是典型的NP困难组合优化问题.为了有效地解决超大规模集成电路布线中的RSMT问题,提出一种粒子群优化算法,借助直角Steiner树的一些性质,采用Steiner点编码方案,寻找优化的Steiner点位置以减少直角Steiner树的长度.对几组布线模型实例进行了仿真测试,表明了该算法的有效性.

VLSI总体布线算法研究与实现

总体布线是布图设计中一个极为重要的设计环节。本文提出了基于可分离最小生成树(SMST)的优化L形直角斯坦(Steiner)树(L_RST)和优化Z_RST的算法。该算法实现上绕开计算重合度问题,以新的角度计算代价。利用基于tile的结构,实现了伪管脚(pseudo pin)的分配,适用于现代多层布线需求。最后文章研究了同时考虑串扰和时延的综合性能驱动的总体布线算法改进。

沙洋县公路网布局方案设计

分析prime算法与直角斯坦纳树的优化计算,应用于沙洋县公路网总体规划布局设计中。将沙洋县的13个建制镇以及若干个行政村分别采用此法进行节点连接关系计算,由此得出沙洋县县域路网及对外路网的布局规划。

基于模式布线和A-Star搜索的总体布线

总体布线是超大规模集成电路布线流程中非常重要的一环,其布线结果的质量直接会影响到后续的详细布线。本文提出了一种基于模式布线和A-Star搜索的总体布线算法。该算法首先对线网进行二维投影,使用FLUTE分解得到所有多引脚线网的直角斯坦纳最小树,再使用三维模式布线快速得到初始解,随后在三维网格上进行基于A-Star搜索和拥塞协商的拆线重布迭代。实验结果表明,本文所述总体布线方法可以在较短的运行时间内,最小化溢出值,得到高质量的总体布线结果。