门阵列和标准单元布图中一种有效的走线道分配算法*

本文提出了一种用于门阵列和标准单元版图自动设计中的走线道分配算法一FARM，它连接总体布线和通道布线．算法目标是使通道的最大密度最小，同时考虑减小线网长度和通孔数．FARM由两部分组成：多行走线道分配和单行走线道分配它已用c语言在DE(：工作站和sun工作站上实现，并已用于我们开发的双层CMOS门阵列布图系统MALS3中．实验例子表明，它与Timborwolf 5.6的结果相当或更好．     

确定区域详细布线算法

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

门阵列和标准单元布图中一种有效的走线道分配算法

本提出了一种用于门阵列和标准单元图自动设计中的走线道分配算法－ＦＡＲＭ，它连接总体布张和通道布线，算法目标是使通道的最大密度最小，同时考虑减小线网长度和通孔数。ＦＡＲＭ同两部分组成，多行走线道分配和单行走线分配。它已用Ｃ语言在ＤＥＣ工作站和Ｓｕｎ工作上实现，并已用于我们开发的双层ＣＭＯＳ门阵布图系统ＭＡＬＳ３中，实验例子表明，它与ＴｉｍｂｏｒＷｏｌｆ５．６的结果相当或更好。     

一种连通孔最小化的通道布线算法

本文根据线网连接端的位置引进了线网位置关系图和线网分层图,从而把连通孔最小化通道布线问题归结为:拆开最少数目的线网使得线网分层图转换成可二着色图。文中导出了通道布线最少连通孔数的公式,并在此基础上提出了一种连通孔最小化通道布线算法。     

考虑总线时序匹配的多策略层分配算法

在总体布线的过程中,层分配阶段通过控制总线线网的层次影响总线的时序匹配效果.为此,提出考虑总线时序匹配的多策略层分配算法.首先基于线网属性的线网优先级策略,针对线网不同属性的特点得到一个兼顾线长和总线偏差的布线顺序;然后基于贪心策略的初始布线策略,每次布线都对正在布线的线网选择当前最短路径,使相同总线内的线网都尽可能等...     

宏单元阵列自动布局算法研究

本文研究并实现了一个用于宏单元阵列的自动布局算法。算法分为初始布局及迭代改善两部分，为提高布图成功率，以线网均匀分布为目标。在初始布图中，采用自下而上结群的方式将宏单元分配到各单元行上，再进行行内定位。在改善布局中，通过对单元行内及单元行间的迭代改善，进一步降低了布线密度，优化了初始布局的结果，从而可使布图成功率得到提高。算法已用Ｃ语言实现，并应用于自动布图系统中，实验结果表明了算法的有效性。     

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

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

BX—300布线系统中的迷路法

迷路法是BX—300印制板布线系统多布线器中的一个布线算法。算法从超高速计算机插件印刷板的实际出发,就提高布通率及加快速度两方面提出了一些改进办法并予以实现。此外,算法还提供给用户优化措施的选择手段,以达到最佳的布线效果。本文在分析YH—2插件印制板及现有各项加速方法的基础上,叙述了系统所采用的标准走线技术,以及加界和选择目标点集的加速措施。     

最小费用布线

本文提出最小费用布线,此是李氏算法的一种改进算法.定义了费用函数,在格同图G上已给两点s和t,按照最小费用,找s和t之间的最小费用连线.此比用李氏算法找线快,便于控制走线.最小费用布线法已经用FORTRAN语言编写程序,在M68000计算机上进行了试算.     

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

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

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

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

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

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

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.     

基于布线资源图的FPGA互连测试算法

分析基于静态随机访问内存的FPGA开关盒互连资源,提出一种自动生成且与应用无关的测试配置集算法,通过建立布线资源图,根据线网的走向动态设定各边的权重,利用改进的Kruskal算法,自动产生测试配置集。对于FPGA不同的互连结构,该算法对互连资源中的开路和短路故障的覆盖率能够达到100%,且具有测试配置个数少、运行速度快以及与具体硬件结构无关等优点。     

Priority-Based Routing Resource Assignment Considering Crosstalk

Crosstalk has become one of the most critical concerns in very deep sub-micron era. This paper deals with the problem of crosstalk mitigation at both methodological and algorithmic levels. Noting that intermediate operations between global routing and detailed routing are very effective in crosstalk estimation and reduction, the authors propose to incorporate several intermediate steps that are separated in traditional design flow into an integrated routing resource assignment stage, so that the operations could easily cooperate to fully exert their power on crosstalk reduction. An efficient priority-based heuristic algorithm is developed, which works slice by slice. Crosstalk avoidance, and many other aspects that are critical in routing practice including congestion, vias, layer preference, etc., are taken into account. A track reservation strategy is adopted in the algorithm framework to compensate the undesired effects caused by sequential routing. Experimental results on a series of ISPD98 and industrial benchmarks show that the proposed approach is able to reduce capacitive crosstalk by about 70% on average without compromising completion ratio compared with a previously reported graph based algorithm, demonstrating the advantages of the approach.     

Diagonal channel routing with vias at unit distance

We consider the «diagonal» channel routing model (DM), where the connections are laid in two layers, along tracks at +45° and ?45° respectively. A previous result [10] shows that, for a channel routing problem of density d, a DM layout exists with channel width w=2d. However, vias may appear at a distance 1/tr2. We prove here that another DM layout can be constructed with w-kd, k constant, and all vias at a distance ≥1. By a theoretical point of view this layout is superior to the one obtained in the classical Manhattan Model, in the worst case.     

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

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

拥挤度驱动的总体布线层分配算法

针对多层布线问题，提出以拥挤度为驱动目标，完成布线资源的合理分配，同时达到布线层资源占用少和通孔数少等优化目标的层分配算法．首先采用启发式方法获得初始分配方案，然后通过模拟退火技术优化分配结果，最后采用试探策略优化层资源占用．工业实验数据表明，该算法能够实现线网层合理分配，获得满足拥挤度的优化解．     

Optimal algorithms for adjacent side routing

We consider the switchbox routing problem of two-terminal nets in the case when all thek nets lie on two adjacent sides of the rectangle. Our routing model is the standard two-layer model. We develop an optimal algorithm that routes all the nets whenever a routing exists. The routing obtained uses the fewest possible number of vias. A more general version of this problem (adjacent staircase) is also optimally solved.This research was supported in part by NSA Contract No. MDA-904-85H-0015, NSF Grant No. DCR-86-00378, and by NSF Engineering Research Centers Program NSFD CDR 88003012.     

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.