消除拥挤的多层总体布线新流程

提出一种在布线前进行层分配的总体布线算法,基于一个多层布线的新流程,使用包含线网所有端点的边界盒来估计线网拥挤度,并基于拥挤度均匀的目标把线网分配到不同层对上.该算法已经实现并进行了测试,实验结果证明了其有效性.     

采用统一建模的拥挤度驱动三维芯片布局算法

三维芯片设计对于提高芯片性能以及减少线长显现了很好的优势,降低连线拥挤度是保证布线成功率和三维芯片实现的关键.为了解决三维芯片布局阶段的拥挤度问题,提出一种拥挤度驱动的三维芯片布局算法.该算法首先对拥挤度单元分布和线长等优化目标进行统一建模,利用二次规划求解单元位置,得到一个单元分布均匀、走线均匀以及线长优化的总体布局;然后利用拥挤度驱动的层分配算法将空间上均匀分布的单元分配到各个芯片层上;最后对各个芯片层进行详细布局,消除重叠,优化拥挤度和线长.实验结果表明,该算法能够改善走线拥挤度约15%,而线长仅有3%的增加.     

一种基于通孔数最小化的多层通道布线算法

该文提出了一种基于通孔数量小化的多层通道布线算法，算法采用非预留层模，首先根据线网之间的位置关系利用模拟退火算法将各线网合理地分配到对应的布线层中去，然后利用遗传算法得到相关布线层中线网的最佳布线顺序向量，最的根据得到的顺序向量利用“沉积法”将各线网布于合理的通道上，该算法克服了传统通孔优化算法中原始布线对优化结果的不利影响，使通孔的优化达到很好的效果。     

确定区域详细布线算法

提出了一种确定区域的详细布线算法,它能对不同设计模式进行布线。该算法能适用于任意多层布线情况,并且支持不同布线层具有的不同工艺参数,在构造布线树时,考虑芯片当前的走线拥挤度,使布线比较平均,并加快了算法运行速度、改善了布线质量,在连接两点线网时,构造基于二维迷宫布线结果的分层图,提出了一种对分层图的启发式染色算示来进行布线层分配,大大提高算法布线速度,采用拆线重布的方法来处理布线失败的线网。     

优化线长和拥挤度的增量式布局算法

随着IC技术的发展，降低连线拥挤度已经成为一个保证布线成功率的至关重要的因素．提出一种标准单元增量式布局算法C-ECOP．该算法通过一个新型的布线估计模型来精确估算布局以后的走线情况，利用力驱动的方法进行单元插入和单元推移来消除局部拥挤，同时进一步优化线长．来自美国工业界的测试实例表明，该算法能够很好地消除走线局部拥挤，同时尽量维持原有布局方案的电路性能，并且具有很高的效率．     

非默认规则线技术下基于多策略的时延驱动层分配算法

层分配作为超大规模集成电路物理设计中的关键环节,在决定布线方案的时延起到非常重要作用.为了优化集成电路的时延性能,现有的层分配工作通常注重优化互连时延和通孔数量,但要么未考虑到对线网中时序关键段的分配问题,要么对线网段的时序关键性的表示不够合理,最终使得算法的时延优化不够理想.为此,本文提出一种非默认规则线技术下基于多策略的时延驱动层分配算法,主要包含4种关键策略:(1)提出轨道数感知的层选择策略,增强层分配器为线网段选择合适布线层的能力;(2)提出多指标驱动的初始线网排序策略,综合考虑线长、信号接收器数和可布线轨道资源等多个指标为线网确定层分配优先级,从而获得高质量的初始层分配结果;(3)提出线网段调整策略,通过重绕线网,将时序关键段调整至上层布线层,优化线网时延;(4)提出线网段时延优化策略,对存在溢出线网进行拆线重绕,从而可同时优化时延和溢出数.实验结果表明,本文提出的算法相比于现有的层分配算法能够在时延和通孔数两个指标上均取得最佳,并且保证不产生溢出.     

一种新的与线网顺序无关的随机优化总体布线算法

针对目前总体布线中仍然存在的3个关键问题;布线结果受布线顺序的影响、总体布线图中拥挤区域的不可预见性、线网连接式样受到算法的限制等,该文提出了一种新的不受线网顺序影响的总体布线算法,并实现了相应的总体布线器RINO－Router。该算法采用随机优化方法来保 证先后被拆线重布的线网有相同的通过拥挤区域的机会,并能得到GRG边的拥挤度估计值;采用高效的Steiner树改造算法构造避开拥挤区域的布线树,采用典型电路实例进行了测试,并将布线结果与基于多商品流算法的总体布线器Matula-Router进行了对比。结果表明,RINO－Router能够在短得多的运行时间内求得质量与Matula-Router相近的总体布线解。     

矩形Steiner最小树布线灵活度

矩形Steiner最小树(RSMT)的布线灵活度影响其结构变形能力,直接影响芯片布线的收敛性.文中从树边形态、结构固有变形和拓扑变形3方面对线网的RSMT的布线灵活度进行刻画,给出了更能反映RSMT结构变形能力的计算模型.针对布线灵活度的"瓶颈"问题,提出了拥挤驱动的RSMT布线灵活度挖掘算法:根据树形的最短布线路径布线可能情况,定义了树边的布线灵活度;进而考虑RSMT结构中所有树边布线灵活度的组合情况和RSMT拓扑的变形性,得到RSMT布线灵活度.实验结果表明:将计算模型应用到拥挤驱动的RSMT布线灵活度挖掘算法,良好地改善了布线拥挤;将该挖掘算法应用到FastRoute4.1总体布线算法中,能够缩短14%的运行时间.     

考虑通孔电阻和耦合电容的时延驱动的层分配算法

针对集成电路设计的多层布线问题,提出了以直接优化互连时延为目标、同时考虑通孔电阻与耦合电容的层分配算法.通过基于路径的时延分析寻找电路的关键路径,以通孔的时延模型和概率耦合电容模型作为层分配模型计算资源分配的代价,利用基于启发式的贪婪算法进行层分配.实验结果表明:该算法比只控制通孔和耦合电容数量的层分配策略具有更大的优势.     

多目标差分进化在热连轧负荷分配中的应用

提出一种基于差分进化算法的多目标进化算法, 该算法个体的选择是通过非支配排序和拥挤度距离进行综合考虑. 保证了算法收敛到Pareto最优解集的同时, 提高了最优解个体分布的多样性. 通过与非支配排序遗传算法Ⅱ(NSGA Ⅱ)算法进行仿真对比, 结果显示基于拥挤度排序的多目标差分进化算法在收敛性和Pareto最优解集分布的多样性上均优于NSGA Ⅱ算法. 最后将其引入到热连轧负荷分配优化计算中, 给出了目标函数的表达方式, 对多目标进化算法在热连轧负荷分配计算中的应用进行了研究.     

多信道无线网状网跨层优化研究

针对多网卡多信道无线Mesh网络容量问题,基于无线信道干扰模型,在给定各节点物理层发射功率的条件下,联合考虑无线Mesh网络传输层的流速控制、网络层的路由算法和MAC层的信道分配等问题,通过采用二次路由计算策略,提出了一个跨层联合优化算法,仿真结果表示,提出的算法能提高网络吞吐量。     

IPv6无线传感器网络低功耗路由算法

为满足IPv6无线传感器网络低功耗的要求,采用适配层路由,在LOAD路由协议基础上提出一种简化的按需式路由算法。本算法采用精简的路由控制报文、路由表和路由请求表,简化了路由发现过程,优化了路由维护机制。仿真实验表明,该算法能有效的降低IPv6无线传感器网络的功耗。     

融合可行基规则的粒子群优化算法及其应用

基本粒子群优化算法对于离散的优化问题处理不佳,容易陷入局部最优。针对基本粒子群优化算法处理离散型优化问题时的缺陷,提出了一种融合可行基规则的改进型粒子群优化算法,并用该算法求解车辆路径问题。实验结果表明,该算法的优化性能和求解精度均优于其他文献算法,在求解车辆路径问题中具有较高的应用价值。     

基于退火下山法的源路由算法

虽然动态路由已经成为趋势,但是由于在某些考虑到安全性的路由系统(如洋葱路由系统)中,还是需要用源路由作为最主要的路由形式,而当需要路由的网络十分庞大的时候,传统的路由方法的效率实在是太低了,这里给出一种新的启发式算法用在源路由大规模网络上。结合模拟退火算法与下山法各自的优点,得到了一种高效、收敛的启发式算法：模拟退火下山算法,它是针对大规模网络路由的复杂性而提出的一种有效快速的算法。作为一种启发式算法,它本身有一定的优缺点,它可以保证得到全局最优解,但是如果要更快速地收敛于最优解的话,则对初始路径的设定有一定要求。一般来说,若初始路径是一个较优值,并且比较恰当,则寻优过程会很迅速。     

Crosstalk-Aware Routing Resource Assignment

Crosstalk noise is one of the emerging issues in deep sub-micrometer technology which causes many undesired effects on the circuit performance. In this paper, a Crosstalk-Aware Routing Resource Assignment (CARRA) algorithm is proposed, which integrates the routing layers and tracks to address the crosstalk noise issue during the track/layer assignment stage. The CARRA problem is formulated as a weighted bipartite matching problem and solved using the linear assignment algorithm. The crosstalk risks between nets are represented by an undirected graph and the maximum number of the concurrent crosstalk risking nets is computed as the max clique of the graph. Then the nets in each max clique are assigned to disadjacent tracks. Thus the crosstalk noise can be avoided based on the clique concept. The algorithm is tested on IBM benchmarks and the experimental results show that it can improve the final routing layout a lot with little loss of the completion rate.     

An optimal adaptive routing algorithm

An adaptive routing algorithm for packet-switched networks is proposed. This algorithm updates both the estimate of external traffic input and the routing assignments at each iteration. The routing assignments determine the proportions of the traffic destined for nodejto be sent from nodeithrough the outgoing links ofi. The algorithm maintains the loop freedom of the routing assignment at each iteration. It also achieves the minimum delay of the network as the limit of its successive updating procedure. The additional features of the algorithm are that it allows at any iteration some routing assignments which theoretically induce infinite delay and that it may utilize variable scaling factors to speed up the convergence.