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

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

几类特殊的斯坦纳最小树问题

通过三角形3个顶点和正方形4个顶点的斯坦纳最小树设计的讨论,总结斯坦纳最小树的性质.在此基础上,给出了不多于4个点的斯坦纳最小树的设计和算法.

无线Ad Hoc网络Steiner树实现协议研究

针对无线Ad hoc网络多跳,拓扑结构随时可能动态变化,协作节点间数据传输需实时性强等问题,利用Netlog语言宣告声明最小Steiner树协议的构造算法方法适应解决。协议可快速构造一棵近似最小的Steiner树,每个节点独立运行声明Steiner树协议,构造Steiner节点间的虚拟全联通网络,在此网络上构造最小代价生成树;然后将此树的节点与边对应原网络的节点和边,继续构造最小代价生成树,最后将此树上的非Steiner节点的叶子节点删除,近似得到最小代价Steiner树,该方法在实验平台上得以验证,为无线移动网络中资源的选择利用提供了一种新的可尝试性的新方法。

欧几里德Steiner树问题介绍及一种特殊情况的讨论

本文是对欧几里德斯坦纳树问题的一个简单介绍,其中包括斯坦纳问题及性质和复杂性。此外,介绍了三个点和四个点的图的斯坦纳树的结构,并对五个点的图之中一种特殊情况的斯坦纳树的结构进行了讨论。

航空发动机外部管路自动敷设研究

采用三维加权网格对发动机复杂三维模型进行网格划分,描述敷管的自由空间,在此基础上利用改进的Lee算法以及最小斯坦纳树生成法,结合各种启发式规则,开发出航空发动机网格敷管系统(AEGRS)。并通过实例,验证了自动敷管的可行性。

基于SMT和LDOB-PRM算法的分支线缆自动布局设计方法

针对机电产品中的分支线缆自动布局设计与优化难题,提出一种基于最小斯坦纳生成树和改进的随机路径图算法的分支线缆自动布局设计方法。该方法采用最小斯坦纳生成树算法求解带有约束的斯坦纳点,并将该点确定为分支线缆的分支点;以基本随机路径图算法为基础,采用低离散度和基于障碍物的混合采样策略,构建一幅覆盖全空间障碍物表面的路径图,再利用A*算法搜索各线缆段的最短路径;对求解得到的路径点进行拟合,并最终获得分支线缆布局设计结果。设计并开发了分支线缆自动布局设计软件原型系统,并进行了算例测试与实例验证,证明了所提方法的可行性。

MCM布线中v4R算法的改进方法

对多芯片组件的布线方法提出了一种新的方法 .以 MCM布线中的四通孔算法 (v4R)为基础 ,针对其易对图的拓扑结构信息丢失的缺陷 ,通过引入最小斯坦纳树 (Minimum Steiner Tree,MST) ,减少总布线层数 ,使总布线长度缩短 ,减少延迟 ,以达到总体布线结果优化 .此外 ,针对 v4R算法自动布线结果不均匀的缺点 ,引入预分配层进行手动预布线 ,使最后 MCM总布线层数减少 .软件模拟表明 ,改进算法有效利用了整个布线空间 ,在电特性方面使整体延时减少 .

粒子群优化的集成电路多端点线网全局布线方法

集成电路(IC)规模激增,从可计算角度上来看,基于传统图论的全局布线方法对解决多端点线网的布线问题已不可行.针对多端点线网互连问题重新建模,设计了新型的构建最小矩形斯坦纳树方法,提出了一种带变异机制的基于改进离散粒子群优化算法的多端点线网全局布线方法(MDPSO—RA).该方法重新设计了粒子群编码及算法的相关操作,在粒子群优化算法全局寻优、快速收敛的基础上,引入遗传算法变异机制,提高了算法性能.实验结果表明,本方法具有全局寻优能力、鲁棒性强等特点,可在时限内,快速得到最优或近似最优多端点线网布线方案.

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

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

改进的Prim启发式算法在VLSI布线中的应用

总体布线在超大规模集成电路的设计中有着举足轻重的作用.为了寻求总体布线图的最优斯坦纳树,改进了普里姆(Prim)算法,提出了一种基于改进的普里姆启发式算法寻求最小矩形斯坦纳树(RST)的方法,不同于以往的先求最小生成树(MST)然后再把树的边矩形化的方法;同时考虑到时延在深亚微米、超深亚微米阶段的重要影响,在算法中又加入了总体布线设计时的时延要求,最后通过仿真实例验证了算法的可行性.

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

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

基于LTL-PRM算法的分支管路自动布局方法

针对非正交分支管路的自动布局问题,提出一种基于局部二次学习概率路径图算法(LTL-PRM)的分支管路自动布局方法,该方法首先采用回溯算法计算出端点之间的最小斯坦纳树,并对其中的斯坦纳点位置进行优化处理,从而获得管路系统的分支点位置,在此基础上通过局部二次学习构建路径图,并利用DIJKSTRA算法搜索出各分支管路的最短路径,最后对搜索出的路径进行优化,从而获得分支管路的最终布局结果.基于此方法,开发了管路自动布局设计软件系统并进行了实例分析,验证了该方法的可行性.

大型城市地下物流网络优化布局的模拟植物生长算法

交通拥堵问题的加剧使传统物流网络在我国大型城市已达到极限,未来地面物流系统将逐步向地下不同层次里转移并释放出城市地上空间.本文以斯坦纳最小树(SMT)为理论模型,建立了符合我国大型城市不断扩展这一特点的树状地下物流网络布局模型.由于SMT为NP-完全问题,因此算法的寻优能力是研究的关键.本文所采用的模拟植物生长算法(PGSA)是以植物向光性理论为启发式准则的智能算法,该算法是利用人工植物在给定物流节点集解空间中的生长过程得到城市地下物流网络的最优布局.通过对国际公布的STEINLIB实例数据计算并与蚁群算法和模拟退火算法进行比较,表明模拟植物生长算法具有较强的精确性、稳定性和全局搜索能力.

Steiner minimal trees——the final destinations for lipid nanotube networks with three-way junctions

Through the combination of the minimum energy principle in physics and the Steiner minimal tree (SMT) theory in geometry,this paper proves a universal law for lipid nanotube networks (LNNs):at stable equilibrium state,the network of three-way lipid nanotube junctions is equivalent to a SMT.Besides,an arbitrary (usually non-equilibrium) network of lipid nanotube junctions may fission into a SMT through diffusions and dynamic self-organizations of lipid molecules.Potential applications of the law to the micromanipulations of LNNs are presented.