超平面概略布线算法的研究

本文提出体现多层布线内在本质约束的新模型：超平面布图模型及超平面概略布线算法．该算法以全新的逆向删冗策略成功地解决了布线线序问题，使线网布线真正达到并行处理；基于总体分析方法，以布线层数和通孔最少为目标，通过动态地分析线网间相互位置关系，全局考虑地释放各线网占据的不合理布线资源，使布线过程避免了迭代，以较高处理效率获得高精度的解．     

动态串扰优化的开关盒布线

针对超深亚微米芯片设计中的开关盒布线问题提出了可变参数的串扰优化布线算法.该算法充分利用了双层布线资源,将动态信号波形和耦合电容结合起来考虑,进一步减小了线网间的总串扰,并力求通孔数最少.实验证明,本算法能够获得更加优化的布线方案.     

动态串扰优化的开关盒布线

针对超深亚微米芯片设计中的开关盒布线问题提出了可变参数的串扰优化布线算法．该算法充分利用了双层布线资源,将动态信号波形和耦合电容结合起来考虑,进一步减小了线网间的总串扰,并力求通孔数最少．实验证明,本算法能够获得更加优化的布线方案．     

一个VLSI三层布线通孔最少化的启发式算法

该文在三层布线的线段-相交图模型基础上,提出了一个启发式算法来解决VLSI三层布线通孔最少化问题,该算法通过总体优化和局部优化两个阶段对三层布线进行通孔优化。算法考虑了实际约束的处理方法,并进行大量的布线实例验证。     

一个基于Hopfield神经网络的双层布线通孔最少化算法

本文在布线的群图模型基础上，利用离散型Ｈｏｐｆｉｅｌｄ神经网络解决群图的最大割问题，并着重论述了如何跳出局部优化点的问题，从而较好地解决了双层布线通孔最少化问题，算法考虑了许多来自实际的约束，并进行大量的布线实例验证。     

一种新的无网格拆线重布算法

结合无网格布线的特点,提出一种新的无网格拆线重布算法.该算法显式地表示并动态更新线网所属区域的拥挤程度.在拆线重布进行待布线网的路径搜索时,每个扩展节点中增加拆除线网周边的拥挤权重,从而将待布线网的路径搜索过程和拆除线网的选择过程统一起来,有效地提高了被拆除线网重新布通的可能性.该算法利用改进的二叉区间树有效组织中间数据,降低计算的复杂度.实验结果表明,该算法能有效消除布线顺序对布线结果的影响,提高布通率,且算法运行速度较快.     

一种新的无网格拆线重布算法

结合无网格布线的特点,提出一种新的无网格拆线重布算法.该算法显式地表示并动态更新线网所属区域的拥挤程度.在拆线重布进行待布线网的路径搜索时,每个扩展节点中增加拆除线网周边的拥挤权重,从而将待布线网的路径搜索过程和拆除线网的选择过程统一起来,有效地提高了被拆除线网重新布通的可能性.该算法利用改进的二叉区间树有效组织中间数据,降低计算的复杂度.实验结果表明,该算法能有效消除布线顺序对布线结果的影响,提高布通率,且算法运行速度较快.     

一种新的基于知识的四边通道布线算法

本文提出了一种新的基于知识的双层四边通道布线算法,该算法对四边通道的布线是通过以下四步完成的。首先,对四边通道的四个角布线,其次,对关键线网优先布线,接下来,利用线网间相互制约关系进行同步增长布线;最后,对仍然没有完成连接的线网,用李氏算法布线。由于使用了启发式规则,使得该算法具有较高的布通率和布线效率。     

设计规则驱动的多层布线算法

迷宫算法是集成电路两端线网优化布线问题的经典算法。多层布线受复杂版图设计规则约束．简单直接应用迷宫布线算法，或者无法获得优化的结果，或者无法满足设计规则。文章分析了迷宫算法特性与局限．提出基于群组图的多层迷宫算法，圆满地解决了上述问题。     

一个可处理多种约束的多层布线通孔最少化算法

本文分析了常用的VLSI多层布线图模型线段－相交图SCG的局限性,提出了对SCG模型的修正,并基于该模型用模拟退火算法来解决通孔最少化问题,算法可以处理严格和非严格分层的布线,并考虑了许多物理约束的处理方法.实验证明算法可以较大程度地减少通孔.     

General gate array routing using a k-terminal net routing algorithmwith failure prediction

A general approach to gate array routing based on an abstract routing space model is presented. An efficient k-terminal net maze runner is described. It does not partition nets into two-terminal net routing problems, but solves the problem by simultaneously growing k search waves. It is shown that the explored routing space diminishes when compared to bidirectional routing schemes. Experimental data show a reduction of CPU time up to 55% and a decrease of total net length up to 6% compared to a bidirectional maze router. For k-terminal nets it is shown that net length decreases with increasing k. Additional routing space restriction is attained by use of variable search space restriction and by the introduction of a dynamic routing space partitioning method based on the concept of regions. This concept allows for determination of nonroutable nets or parts of nets in an efficient way. The new partitioning method may be implemented in any maze runner without increasing the complexity of the maze runner algorithm. Results show an additional decrease of CPU time up to 35%     

SAT based solutions for detailed routing of island style FPGA architectures

Detailed routing solutions for island style FPGA architectures using Boolean satisfiability (SAT) based formulations have been proposed in this paper. Due to decreasing size of ICs and hence, the increasing complexity of the routing resource constraints, routing has been a big challenge in electronic design automation field. Our proposed techniques work on multi-pin net routing where all nets are considered for routing in their intact form whereas, most of the existing routing solutions decompose multi-pin nets into two-pin nets for detailed routing to ease the problem. However this approach, apart from increasing the number of nets in the circuits, may also introduce pin doglegging which, when not permitted by the architecture of FPGA, would require extra constraints to eliminate. Many detailed routers adopt sequential detailed routing approaches which are vulnerable to the net ordering problem which may cause a routable circuit to be erroneously classified as unroutable. Our proposed techniques avoid these pitfalls by keeping the multi-pin nets intact and solve all nets simultaneously using SAT. The SAT-based multi-pin net dogleg-free formulations presented here achieve significant improvement over existing SAT-based solutions with respect to the number of variables and clauses used, thereby achieving greater scalability and also display comparable and sometimes better routability results on benchmark circuits when compared with other detailed routing solutions. Detailed routing is also significantly affected by the architecture of the switching blocks. This paper proposes SAT-based formulation for three different switch box architectures i.e. Subset, Wilton, and Universal switches. Our experiments clearly demonstrate how routing solutions for a circuit can differ significantly for different types of switch boxes.     

Routing for reliable manufacturing

The impact of spot defects on the susceptibility for electrical failure of a net is analyzed. Based on this analysis, a general routing cost function is presented, in which the manufacturability of a net is taken into account in conjunction with traditional routing objectives. The new cost function, relating the process spot defects to the routing procedure has been implemented. Failure probabilities are analyzed for the benchmark layouts obtained by our routing tool using both the original cost function and the new cost function. The results show that the failure probability of a layout is significantly decreased if the spot defect mechanism is taken into account in the routing procedure, while the area of the layout is kept constant     

A new sensitivity model with blank space for layout optimization

As the technology scales advancing into the nanometer region, the concept of yield has become an increasingly important design metric. To reduce the yield loss caused by local defects, layout optimization can play a critical role. In this paper, we propose a new open sensitivity-based model with consideration of the blank space around the net, and study the corresponding net optimization. The proposed new model not only has a high practicability in the selection of nets to be optimized but also solves the issue of the increase in short critical area brought during the open optimization,which means to reduce the open critical area with no new short critical area produced, and thereby this model can ensure the decrease of total critical area and finally achieves an integrative optimization. Compared with the models available, the experimental results show that our sensitivity model not only consumes less time with concise algorithm but also can deal with irregular layout, which is out of the scope of other models. At the end of this paper, the effectiveness of the new model is verified by the experiment on the randomly selected five metal layers from the synthesized OpenSparc circuit layout.     

一种用于三层布线的分层算法

随着VLSI/LSI技术的发展,多层布线已能够实现。互连网络的分层问题就是要使得互连网络所需的通孔数最少。在通孔最小化问题中,如果布图拓扑逻辑已给出,这类问题被称为受限的通孔最小化(CVM)问题。本文针对三层布线中的CVM问题提出了一种分层算法,使得布图所需的通孔数最小化。应用此算法能获得比文献中所述更少的通孔数。     

A full-scale solution to the rectilinear obstacle-avoiding Steiner problem

Routing is one of the important steps in very/ultra large-scale integration (VLSI/ULSI) physical design. Rectilinear Steiner minimal tree (RSMT) construction is an essential part of routing. Macro cells, IP blocks, and pre-routed nets are often regarded as obstacles in the routing phase. Obstacle-avoiding RSMT (OARSMT) algorithms are useful for practical routing applications. However, OARSMT algorithms for multi-terminal net routing still cannot meet the requirements of practical applications. This paper focuses on the OARSMT problem and gives a solution to full-scale nets based on two algorithms, namely An-OARSMan and FORSTer. (1) Based on ant colony optimization (ACO), An-OARSMan can be used for common scale nets with less than 100 terminals in a circuit. An heuristic, greedy obstacle penalty distance (OP-distance), is used in the algorithm and performed on the track graph. (2) FORSTer is a three-step heuristic used for large-scale nets with more than 100 terminals in a circuit. In Step 1, it first partitions all terminals into some subsets in the presence of obstacles. In Step 2, it then connects terminals in each connected graph with one or more trees, respectively. In Step 3, it finally connects the forest consisting of trees constructed in Step 2 into a complete Steiner tree spanning all terminals while avoiding all obstacles. (3) These two graph-based algorithms have been implemented and tested on different kinds of cases. Experimental results show that An-OARSMan can handle both convex and concave polygon obstacles with short wire length. It achieves the optimal solution in the cases with no more than seven terminals. The experimental results also show that FORSTer has short running time, which is suitable for routing large-scale nets among obstacles, even for routing a net with one thousand terminals in the presence of 100 rectangular obstacles.     

LSI版图设计中的一种P／G网布线法

本文提出了一种有效的P/G网布线算法和在积木块式布图系统中实现的策略。与以往算法比较,此算法允许每条电源网具有多个馈电脚存在。其策略包括四个部分:(1)一种有效的层次式自上而下的P/G网平面性分析和拓扑路径分配算法;(2)P/G网线宽的确定;(3)总体压缩和再布线后P/G网布线信息的动态修改;(4)与信号网一起的平面性无网格电源网通道详细嵌入。实验结果表明我们的P/G网布线方法可获得令人满意的布线结果。     

双层PCB线网均匀化问题及其算法

线网分布均匀性直接影响到PCB上电路的性能。但由于布线问题的计算复杂性很高,在布线过程中很难保证布线的线网均匀性。在本文中,提出了一种双层PCB线网均匀化的方法。     

基于图像处理的版图优化方法

随着集成电路技术进入深亚微米技术节点,提高成品率成为研究热点问题。文中提出了一种基于图像处理的版图优化方法来提高成品率。该方法首先确定两个待优化线网和其可移动空间,再找出两个待优化线网的最佳移动位置,将两个待优化线网移动后所减小短路关键面积最大的线网,作为本次优化的线网,实现对版图的优化。文中提出的优化方法不但考虑了缺陷的真实轮廓特征和粒径分布特征,而且不受版图线网的形状的制约,为版图优化提供了更准确的依据。