带有引线端预处理的区域布线算法

提出一种带有引线端优化处理的多层区域布线算法，能处理端点障碍在区域内任意分布的大量布线问题，首先将多端线网划分为二端子线网，并在此基础上根据二端子线网之间的相对位置关系进行分类；然后对每个类型的二端子线网，采用双向迷宫和朝向目标的深度优先搜索策略依次布线；最后通过拆线-重布策略来解决布线冲突．在进行布线搜索之前，对引线端映射到网格点上这一过程引入了一种有效的优化预处理机制，采用二分图中多目标约束寻找最佳匹配的思想和策略来解决引线端优化映射问题．测试并比较了有／无这种优化处理的2种情况，实验结果表明，该算法有效地改善了网格映射的精度和准确性，可缩短线长和提高布通率．     

一种考虑可制造性的高性能多层布线算法

本文采用改进的“V”字型布线流程,提出了一个考虑可制造性的多层布线算法,通过粗化和细化两个阶段完成布线。粗化阶段进行资源估计,在“V”字型框架的最底层通过多商品流算法获得总体布线的粗略解;细化阶段通过基于图的Steiner树方法细化布线拓扑树。详细布线采用改进的非均匀网格图,通过考虑OPC的迷宫布线算法,提高设计的的可制造性。     

新型实用布线算法──L─M算法

本文提出新型布线算法，集李氏迷宫法与线搜索法的长处为一体，以饱和带法进行动态排序，以线搜索法确定借孔位置，然后用李氏法进行单层布线，获得最佳路径，从而达到线型好，布通率高的效果。     

确定区域详细布线算法

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

自动布局布线程序

功述描述了用于规划芯片的自动布局布线程序。其特点是在单元电路版图实现之前进行布局布线以及布线是在单元内部进行，不存在专门的布线通道。这种布图模式，以多端网连接模型作为布局布线的连接模型，并以布线均匀作为主要的目标函数。 整个程序模块分为矩阵网格规划和布局，总体布线，端口分配三部分。在布局中采用最小切割算法。初始布线以布线均匀，连线长度最短为目标，并采用一个基于布线均匀的“重心“算法。通过再布线和通     

VLSI中高性能X结构多层总体布线器

X结构带来物理设计诸多性能的提高,该结构的引入和多层工艺的普及,使得总体布线算法更复杂.为此,在XGRouter布线器的基础上,本文设计了三种有效的加强策略,包括:1)增加新类型的布线方式;2)粒子群优化(Particle swarm optimization,PSO)算法与基于新布线代价的迷宫布线的结合;3)初始阶段中预布线容量的缩减策略,继而引入了多层布线模型,简化了XGRouter的整数线性规划模型,最终构建了一种高性能的X结构多层总体布线器,称为ML-XGRouter.在标准测试电路的仿真实验结果表明,ML-XGRouter相对其他各类总体布线器,在多层总体布线中最重要的优化目标|溢出数和线长总代价两个指标上均取得最佳.     

基于边界扩张的点对点布线新算法

在超大规模集成电路设计中,全局布线是非常重要的步骤。工业界普遍采用经典的迷宫算法及其改进算法解决全局布线问题。随着工艺节点的减小,传统迷宫算法复杂度高的缺点越来越明显。针对传统迷宫算法的复杂度会随着布线规模的扩大而迅速增加的问题,借助于边界扩张的概念,提出一种新的点对点布线路径的搜索算法。摒弃了迷宫算法低效率的逐个节点扩张的思想,通过自由节点的定义对节点边界进行迅速扩张并不断地找到新的自由节点,直到找出路径或确定无解时结束。将该算法与经典的布线算法进行理论和实验比较,结果表明在大多数情况下该算法使用经典算法7%~14%的运行时间即可完成路径搜索。     

面向区域布线的层次式PB角勾链版图数据结构

无网格区域布线具有存储量小、布通率较高、易实现混合设计规划布线并可解决串扰问题等优点,无网格区域布线算法中,找到路径后对底层图数据库的修改时间在整个算法运行时间中占很大比例,因此,操作简便、快捷的版图数据结构对于网格区域布线算法非常重要,目前无网格区域布线算法中应用最广泛的版图数据结构是矩形勾链,其点查找和模块插入操作的复杂度均匀Ｏ（Ｎ＾１／２）,文中提出一种新型的结合了Ｂｉｎ结构与梯形角勾链结构     

基于图论模型的一类集成电路布线算法

针对具有曼哈顿模型的一类通道布线,提出了一个依据图论模型的最优轨道高度布线算法。算法根据通道上结点的水平约束图和垂直约束图,依次安排好每一个结点的布线轨道,进而通过通孔可以把所有的结点在2层轨道上布线完成。通过计算分析,该算法相对以前的算法能够达到更优的布线高度,并且其复杂性保持不变。     

求解迷宫布线问题的人工智能图搜索产生式系统

本文提出了一个求解迷宫布线问题的人工智能图搜索产生式系统。当取不同的控制策略,本系统可分别实现Lee算法和Rubin算法。基于上述系统本文还提出了一个启发性迷宫布线过程,其搜索的面积元素比Rubin算法减少30％左右。本文最后对Lee,Rubin算法和本文提出的过程作了统计比较。     

多层印制电路板的线探索布线

本文介绍适合于多层印制板的一种高效快速的线探索布线方法,并讨论了改善全局布线效果和布线合理性的一些途径:通过扩充探索线的概念,将朝向目标线探索的思想推广至多层板布线;采用分级探索和多层同时探索的策略,改善全局布线效果;采用多级优化措施,保证布线的合理性。     

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

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

无线HART网络点到点图路由的研究与实现

无线HART是一个开放的用于工业测量和控制的无线通信标准。无线HART标准在网络层采用图路由机制,通过提供链路冗余,以满足工业应用中安全、可靠的通信需求。现有的图路由算法研究仅局限于集中式通信,文中设计并实现了局部分布式通信的点到点图路由算法。该算法利用跳数、链路质量作为度量进行选路,提供跳间冗余以保证路由健壮性,并通过对跳间链路数的限定以及路由图范围的集中,可以为网络中任意两点间建立会话,减少控制时延,有效避免通信资源的浪费。该算法实现的通信模式不仅保留了集中式图路由的可靠性,也可以满足无线工业控制的灵活性和实时性需求。     

基于节点多样性的域内路由保护算法

已有的路由保护方案都没有考虑网络中节点的重要程度,然而在实际网络中不同节点在网络中的重要程度是不相同的。针对该问题,提出一种基于节点多样性的域内路由保护算法（intra-domain routing protection algorithm based on node diversity,RPBND）。计算节点构造以目的为根的最短路径树（shortest path tree,SPT）,从而保证RPBND算法和目前互联网部署的路由算法的兼容性;在该最短路径树的基础上构造特定结构的有向无环图（directed acyclic graph,DAG）,从而最大化路由可用性。实验结果表明,RPBND极大地提高了路由可用性,降低了故障造成的网络中断时间,为ISP部署域内路由保护方案提供了充分的依据。     

一种基于迷宫算法的有效FPGA布线方法

在本篇论文中,我们介绍了在标准对称阵列（隔离岛状）现场可编程逻辑阵列结构下的一种基于迷宫布线算法的新型有效布线方法,Pathfinder.实验结果显示,相比普通的迷宫布线法,Pathfinder算法在布线时间上减少了90%.     

基于多层混合结构的IPv6路由表查找算法

针对现有的大多IPv6路由表查找算法采用各种优化手段提高查找性能,却使得路由更新需要重构整个路由表的问题,提出基于多层混合结构的IPv6路由表查找算法。该算法在第一层借鉴最优查找树的优点,把前缀1~16位的不同取值按其在路由表中出现的概率降序存储在线性表中,在第二、三层把前缀的17~32位和33~48位分别用二叉平衡树组织,在第四层把49~64位使用线性表组织。实验结果表明,该算法查找速度快,占用内存少,动态增量更新速度快。     

Conjugate conflict continuation graphs for multi-layer constrained via minimization

A graph model for describing the relationships among wire segments is crucial to constrained via minimization (CVM) in a VLSI design. In this paper we present a new graph model, called the conjugate conflict continuation graph, for multi-layer CVM with stacked vias. This graph model eases the handling of stacked via problems. An integer linear programming (ILP) formulation and a simulated annealing (SA) algorithm based on this graph model are developed to solve multi-layer CVM. The ILP model is too complicated to solve efficiently. The SA algorithm on average achieves 6.4% via reduction for layouts obtained using a commercial tool under a set of practical constraints in which the metal wires (including pins) used in cell layouts, power rails and rings, and clock routing are treated as obstacles or fixed-layer objects to a multi-layer CVM.     

基于免疫Memetic算法的网络组播路由优化

为了求得代价最小的网络组播路径,提出了一种基于免疫Memetic算法的优化求解方法。算法充分结合免疫全局搜索和局部搜索机制,设计了适合组播路由问题的各种免疫算子,加快了算法的收敛速度。实验结果表明,该算法在无需备选路径集的情况下,可以较快地找到最优路径,并且算法更加简单。