Steiner树

摘要： 无线网络中的虚拟骨干(VB)是一些无线节点的子集,因此只有VB中的节点负责路由相关任务,并且VB总权值越小会导致开销越少.在一个点赋权的无线网络中,不单要考虑VB中节点数的多少,更重要的是要考虑其总权值的大小.通常,一个赋权无线网络被模型化为一个点赋权单位圆盘图(UDG),相应地赋权无线网络中的最小权VB问题被抽象为点赋权UDG中的最小权连通控制集(MWCDS)问题进行研究.求MWCDS是一个NP-难问题.为降低点赋权UDG中MWCDS问题的近似比,在连通部分提出一种新方法——基于度的点赋权Steiner树算法.结合目前最好的结果,对于UDG中的MWCDS问题将得到一个(3.32+ε)-近似算法.同样地,对于UDG中的最小权顶点覆盖(MWCVC)问题也将得到一个(3.32+e)-近似算法.证明了通过改进连通部分的近似比令点赋权UDG中MWCDS问题的近似比降低的方法是可行的.

摘要： Internet是连接云端与分布在不同区域边缘端的重要传输载体,其尽力而为的服务模式在支持群组控制命令传输时,会造成快速消耗网络资源及路径竞争等问题.首先,把Internet群组控制命令传输问题转换为不相交带约束的多Steiner树问题(constrainted multi-Steiner trees with disjoint problem,CMSTDP),并提出一种改进型遗传算法.该算法聚焦于提升全局搜索能力和缓解路径竞争两个方面.实验从群组命令传输成功率、收敛延时比及解误差率三个方面验证,该算法适合应用于边缘端—云端之间的群组命令传输.

摘要： Steiner最小树是超大规模集成电路中布线阶段的最佳模型,进一步考虑能够有效防止信号失真的电压转换速率(Slew)约束这一个更为贴近实际芯片设计模型和更具线长优化能力的X结构,首次提出基于混合离散粒子群优化的Slew约束下X结构Steiner最小树算法.首先,为了避免频繁的Slew约束计算,提出了高效的预处理策略,并且提出一种能够有效考虑Slew约束的针对性的惩罚机制.其次,为了能够有效求解该离散问题,基于遗传算子重新设计了粒子群优化算法的离散更新机制,并提出一种更适合遗传算子的引脚对编码方式.然后,为了进一步优化布线树的长度,提出一种有效的精炼策略.最终,提出一种混合修正策略以完全满足Slew约束.实验表明,所提算法可完全满足电压转换速率约束并取得同类工作中最佳的布线结果.

摘要： 本文针对最小代价Steiner树问题,提出一种前驱编码粒子群算法.为了避免环的产生,粒子向量采用前驱节点编码表示;重新设计粒子飞行实现方式,引入了基于邻接矩阵的"开发"算子以及基于剔除相同适应度值粒子策略的"勘探"算子.仿真实验表明,本文提出的算法能有效解决Steiner树问题,并且在多数测试算例上的表现优于已有算法.

摘要： 在已有配电网网架规划问题研究成果的基础上,提出了一种基于灾害地图的配电网网架规划方法.首先,建立配电网网架规划的数学模型;然后,将该数学模型抽象成Steiner(斯坦纳)树问题,同时绘制规划区域的灾害地图,通过灾害地图量化不同区域的中间节点建设成本,确定Steiner树的权重,采用模拟退火算法求解,生成最优网架结构并判断约束条件;最后,通过算例分析验证了算法的性能和有效性.所提基于灾害地图的规划方法突破了传统配电网网架规划方法在有限点集内搜索最优解的瓶颈,使得配电网网架规划方法更加灵活,扩大了中间节点的选取范围,增大了搜索到全局最优解的概率,为配电网网架规划提供了一种新的思路.

摘要： X结构Steiner最小树(XSMT)是非曼哈顿结构总体布线算法中多端线网的最佳连接模型,属于NP难问题.文中基于混合转换策略和自适应粒子群优化算法,提出XSMT构造算法.首先设计有效的混合转换策略,扩大算法寻优空间,提高算法收敛效率.为了满足粒子编码的健全性,算法的更新方式引入带并查集策略的交叉和变异算子,同时采取自适应调整学习因子的策略,加快粒子群优化算法的收敛速度.实验表明,文中算法能得到较好的XSMT求解方案,获得多种不同拓扑的XSMTs,有利于VLSI总体布线阶段的拥挤度优化.%X-architecture Steiner minimal tree ( XSMT) problem is an NP-hard problem, and it is the best connection model for a multi-terminal net in non-Manhattan global routing problem. An XSMT construction algorithm based on hybrid transformation strategy and self-adapting particle swarm optimization( PSO) is proposed. Firstly, an effective hybrid transformation strategy is designed to enlarge the search space and enhance the convergence of the algorithm. Secondly, the crossover and mutation operators based on union-find sets and a self-adapting strategy to adjust the learning factors are proposed to satisfy the robustness of particle coding and further speed up the convergence of algorithm. The experimental results show that the proposed algorithm efficiently produces a better solution than others. Moreover, it obtains a series of XSMTs with different topology but same length. Thus, it provides a variety of options for global routing and opportunities to reduce congestion.

摘要： 在无线传感器网络中,由于能量耗尽以及恶劣环境的影响,传感器节点容易出现故障导致网络不连通.为此,针对无线传感器网络中的拓扑修复问题,总结和分析近年来相关的主要方向和研究成果,同时根据网络故障规模的不同对小规模故障和大规模故障的网络修复算法进行分类总结以及优缺点分析.此外,从算法触发条件以及实现角度等方面对修复算法作进一步分类,并指出当前研究的不足和未来的改进方向.

摘要： 考虑到粒子群优化算法具有非常出色的全局优化能力,针对X结构布线问题的复杂性提出了X结构下的多层Steiner最小树构建算法.实验结果表明,该算法可以在合理的时间内取得优异的布线解.

摘要： 本文讨论了给定点着色数和匹配数的图类中k-Steiner Wiener指数的下界,并刻画了极图。图G 的k-Steiner Wiener指数定义为图G 中任意k-点集S 的Steiner距离的d(S)和,而点集S 的Steiner距离d(S)是包含点集S 的最小子树的边的数目。

摘要： Steiner最小树作为VLSI布线的基础模型,应进一步考虑到X结构、障碍物、多层等条件,文中基于粒子群优化提出了多层绕障X结构Steiner最小树算法.首先引入边变换操作以改变布线树的拓扑,使其具有较强的绕障能力;为了避免边变换操作带来的布线树环路问题,结合并查集策略设计新的操作算子;为了保证布线边不违反约束,提出一个与绕障情况及通孔数相关的惩罚函数策略,从而优化了多层布线中布线总代价这一最重要的目标.实验结果表明,相对于同类算法,该算法在布线总代价的优化能力上是最强的.

摘要： DNH算法有较好的近似比,所得到Steiner树具有2(1-1/|S|)的性能,但其时间复杂度为O(|S|(|V|log|V|+|E|)).本文将对DNH算法加以改进,使复杂度降为O(|V|log|V|+|E|),并证明了改进算法的性能将保持不变.

摘要： DNH算法有较好的近似比,所得到Steiner树具有2(1-1/|S|)的性能,但其时间复杂度为O(|S|(|V|log|V|+|E|)).本文将对DNH算法加以改进,使复杂度降为O(|V|log|V|+|E|),并证明了改进算法的性能将保持不变.

摘要： DNH算法有较好的近似比,所得到Steiner树具有2(1-1/|S|)的性能,但其时间复杂度为O(|S|(|V|log|V|+|E|)).本文将对DNH算法加以改进,使复杂度降为O(|V|log|V|+|E|),并证明了改进算法的性能将保持不变.

摘要： 本发明涉及一种考虑电压转换速率的X结构Steiner树构造方法，包括以下步骤：S1）生成初始的Steiner树结构；S2）预先处理及记忆引脚与障碍之间的信息；S3）采用离散粒子群优化算法优化Steiner树结构，通过包括速度更新、自我感知及群体感知的粒子更新过程，得到优化的Steiner树结构；S4）对Steiner树结构进行局部优化，使其局部结构达到最优，以进一步缩短布线线长；S5）通过混合修正策略，对Steiner树结构中违反约束的部分进行调整，使Steiner树满足电压转换速率约束，得到最终的Steiner树结构。该方法有利于在满足电压转换速率约束的同时，优化布线线长。

摘要： 本发明提出一种基于多策略优化的Slew约束下的X结构Steiner树构造方法，包括以下步骤：步骤S1：结合三角剖分方法和最小生成树方法获得点集为引脚集的最小生成树；步骤S2：生成用于记录引脚以及障碍之间的信息的预查表，并将最小生成树转换成Steiner树；步骤S3：进行重布线，通过消除布线中经过障碍的较长片段并重新布线以降低Slew大小，使Steiner树部分满足Slew约束；并采用精炼策略，以进一步减少Steiner树的布线代价；步骤S4：逐个计算并修正不满足Slew约束的布线，使得内部树完全满足Slew约束。经过实验表明，本发明方案在线长及算法运行时间上均取得最优的结果。

摘要： 标准单元总体布线时障碍下的直角Steiner树方法属于集成电路计算机辅助设计技术领域，其特征在于：它首先将所有障碍视为不存在，求得待连线网的端点集在无障碍下的Steiner树即预-Steiner树；然后，使预-Steiner树中在障碍内部的树边绕过障碍，生成有障碍下的Steiner树；在生成有障碍Steiner树的过程中，根据图的拓扑结构，进行适当的预处理和后期处理，以在考虑时间效率下优化线长的优化问题。它解决了在待连线网有多个端点情况时标准单元总体布线时有障碍下优化了线长和时间效率的直角Steiner树构造方法。

摘要： 超大规模集成电路避障碍的直角Steiner树方法属于集成电路计算机辅助设计技术领域，尤其超大规模集成电路布线设计领域，其特征在于：提出基于完全Steiner树(FST)的端点划分方法，然后在划分出来的每个子集中针对不同情况分别使用蚁群方法和贪婪FST方法构造子Steiner树，最后用detour方法的思想来连接所有的子Steiner树。该算法能处理多端点(包括能处理两端点)的线网；能处理复杂障碍(包括凹多边形障碍)的情况；能够在较短时间里很好地处理大规模问题。它实现了在待连接线网有多个端点情况下的超大规模集成电路布线时避障碍的优化线长与时间效率的直角Steiner树构造方法。

摘要： 本发明提出一种基于多策略优化的Slew约束下的X结构Steiner树构造方法，包括以下步骤：步骤S1：结合三角剖分方法和最小生成树方法获得点集为引脚集的最小生成树；步骤S2：生成用于记录引脚以及障碍之间的信息的预查表，并将最小生成树转换成Steiner树；步骤S3：进行重布线，通过消除布线中经过障碍的较长片段并重新布线以降低Slew大小，使Steiner树部分满足Slew约束；并采用精炼策略，以进一步减少Steiner树的布线代价；步骤S4：逐个计算并修正不满足Slew约束的布线，使得内部树完全满足Slew约束。经过实验表明，本发明方案在线长及算法运行时间上均取得最优的结果。

摘要： 本发明涉及一种考虑电压转换速率的X结构Steiner树构造方法，包括以下步骤：S1）生成初始的Steiner树结构；S2）预先处理及记忆引脚与障碍之间的信息；S3）采用离散粒子群优化算法优化Steiner树结构，通过包括速度更新、自我感知及群体感知的粒子更新过程，得到优化的Steiner树结构；S4）对Steiner树结构进行局部优化，使其局部结构达到最优，以进一步缩短布线线长；S5）通过混合修正策略，对Steiner树结构中违反约束的部分进行调整，使Steiner树满足电压转换速率约束，得到最终的Steiner树结构。该方法有利于在满足电压转换速率约束的同时，优化布线线长。

摘要： 本发明涉及一种X结构下考虑障碍内布线的Steiner树构建方法，包括以下步骤：步骤S1:初始化粒子群，其中每个粒子表示一个连接所有给定引脚的X结构Steiner树；步骤S2:对粒子群进行预处理，生成包含所有粒子的任意两个引脚之间的所有连接信息的查找表；步骤S3:粒子群飞行，并通过变异策略，交叉策略以及粒子适应值函数迭代,得到优秀粒子;步骤S4:对得到的优秀粒子继续调整，引入障碍物角点为Pseudo‑Steiner点的调整策略，确保所有边在障碍内的连通分量长度都不超过门限值L，得到调整后的优秀粒子；步骤S5:对调整后的优秀粒子进行进一步的精炼，得到最优粒子，即最优的X结构Steiner树。本发明能够充分利用障碍内资源进行布线，显著缩短了总布线长度。

摘要： 超大规模集成电路避障碍的直角Steiner树方法属于集成电路计算机辅助设计技术领域，尤其超大规模集成电路布线设计领域，其特征在于：提出基于完全Steiner树(FST)的端点划分方法，然后在划分出来的每个子集中针对不同情况分别使用蚁群方法和贪婪FST方法构造子Steiner树，最后用detour方法的思想来连接所有的子Steiner树。该算法能处理多端点(包括能处理两端点)的线网；能处理复杂障碍(包括凹多边形障碍)的情况；能够在较短时间里很好地处理大规模问题。它实现了在待连接线网有多个端点情况下的超大规模集成电路布线时避障碍的优化线长与时间效率的直角Steiner树构造方法。

摘要： 标准单元总体布线时障碍下的直角Steiner树方法属于集成电路计算机辅助设计技术领域，其特征在于：它首先将所有障碍视为不存在，求得待连线网的端点集在无障碍下的Steiner树即预－Steiner树；然后，使预－Steiner树中在障碍内部的树边绕过障碍，生成有障碍下的Steiner树；在生成有障碍Steiner树的过程中，根据图的拓扑结构，进行适当的预处理和后期处理，以在考虑时间效率下优化线长的优化问题。它解决了在待连线网有多个端点情况时标准单元总体布线时有障碍下优化了线长和时间效率的直角Steiner树构造方法。

摘要： 本申请涉及集成电路技术领域，尤其涉及一种基于R树MBR算法的集成电路自动打孔方法及装置。其中，一种基于R树MBR算法的集成电路自动打孔方法，包括：对每一个生成的金属矩形进行空间索引，确定生成的金属矩形与相邻层的金属矩形的重叠区域；保证所有重叠区域通过DRC规则检查；根据通过DRC规则检查的重叠区域，对集成电路进行自动打孔。采用上述方案的本申请通过空间索引，能够自动检索满足条件的重合区域，再根据DRC规则，对重合区域进行自动打孔，从而提高电路设计效率,缩短电路产品的上市时间。