一种带权动态调整的总体布线算法及其实现

本文对现有的总体布线方法及宏单元阵列总体布线问题进行了详细分析,提出了一种基于带权动态调整思想的适合于宏单元阵列一层半和双层版图模式的总体布线算法,其目标是合理地利用已确定的布线区域,使各线网均匀地分布在芯片上,获得尽可能高的布通率。     

通道区布线的线网分布优化问题及其算法

在ＶＬＳＩ布线设计中，线网的分布情况直接影响到ＶＬＳＩ芯片的电学性能、可靠性和制造成本。但是，由于通道区布线问题的计算复杂性很高＾［１］，布线过程中往往没有考虑到线网的分布问题，因此，布线完成后有必要对布线结果进行一次线网分布优化。本文中提出了两种工艺的双层通道区布线线网分布优化问题，并给出了相应的算法。     

通道区布线的线网分在优化问题及其算法

在ＶＬＳＩ布线设计中，线网的分布情况直接影响到ＶＬＳＩ芯片的电学性能、可靠性和制造成本。但是，由于通道区布线问题的计算复杂性很高￣［１］，布线过程中往往没有考虑到线网的分布问题，因此，布线完成后有必要对布线结果进行一次线网分布优化。本文中提出了两种工艺的双层通道区布线线网分布优化问题，并给出了相应的算法。     

一种多线程FPGA时序驱动布线算法

随着现场可编程门阵列(FPGA)器件尺寸不断增大,计算机辅助设计(CAD)工具运行时间成为突出的问题。布线是FPGA的CAD流程中最为耗时的一个阶段,一种能有效缩短布线时间的方法就是并行布线。本文提出一种减少FPGA时序驱动布线算法运行时间的多线程方法。该算法首先将信号按照线网的扇出数量进行排序,再将排序后的线网均匀分配到各个线程中,最后并发执行所有的线程。在布线质量没有受到显著影响的前提下,即线长增加2.58%,关键路径延时增加1.78%的情况下,相对于传统通用布局布线工具(VPR)时序驱动布线算法8线程下的加速比为2.46。     

射频电路PCB板的电磁兼容性设计

从PCB布局、PCB布线（电源线、地线、时钟线及信号线的最优化布线原则）和补铜箔等几个方面讨论了在PCB设计中如何抑制射频干扰及实现系统电磁兼容性的方法，实践证明，该方法在抑制电磁干扰方面是比较有效且非常经济的。     

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

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

刚-挠结合PCB设计技术

刚-挠结合PCB具有可挠曲性,能够实现三维布线,在电子设备中的应用越来越广泛。文中详细介绍了刚-挠结合PCB设计的基本原则。     

一种减小关键路径延迟的回路布线法

传统的性能驱动布线算法受限于树形或固定的布线拓扑结构．本文提出一种回路性能优化布线算法，针对树形线网布线，通过在已存在的布线树上加入回路来减小所选择关键路径的延迟时间或线网的最大延迟．我们将互连线树归结为分布传输线网络并采用Ｅｌｍｏｒｅ延迟计算方法．本文证明，通过选择适当的ＲＣ，在连接节点与关键节点之间加入连线可达到减小所选择线网中关键路径延迟或线网最大延迟的目的．实验结果表明，我们的方法有效且可以集成在现有ＣＡＤ性能优化布线系统中．本文同时给出了所加入线段长度的计算方法．     

一个基于整体优化分析的区域布线算法——DRAFT

本文提出一种新的基于整体优化分析的区域布线算法──DRAFT,它可以解决通道布线和四边布线问题。该算法分二个阶段完成区域详细布线:定向布线和最终布线。定向布线阶段给出各线网可行走线区间和最佳走线位置,其结果在最终布线阶段引导各线网的实际走线。布线在两层上进行,但不限制不同方向的走线必须走在不同层上。实验结果令人满意,对于大多数发表在文献中的通道布线和四边布线例子,DRAFT都得到了相当满意的解。     

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

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

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.     

长线网预处理的过点分配算法

提出了一个长线网预处理的过点分配算法.该算法不仅考虑了过点和物理连接端的连接费用、总体布线单元边界上不同过点之间的互斥费用,而且考虑了同一线网不同过点之间的错位费用.实验结果表明,该算法极大地提高了详细布线阶段的布线质量和速度,特别是对于长线网而言,效果更为显著.     

长线网预处理的过点分配算法

提出了一个长线网预处理的过点分配算法.该算法不仅考虑了过点和物理连接端的连接费用、总体布线单元边界上不同过点之间的互斥费用,而且考虑了同一线网不同过点之间的错位费用.实验结果表明,该算法极大地提高了详细布线阶段的布线质量和速度,特别是对于长线网而言,效果更为显著.     

VLSI版图综合中的P／G网实体优化布线

本文提出了一种在通道内将Ｐ／Ｇ网与信号网的实体布线一体化考虑的优化布线策略，目的是在保证１００％布通的前提下，完成Ｐ／Ｇ网的平面化实体嵌入和信号网的实体布线，并使Ｐ／Ｇ走线对信号网走线的影响尽可能小。算法以提高布线区利用率、减小通道高度和减少通孔数为目标，实现总体性能的优化。系统实现的结果表明，本文算法所采用的策略是可行的、有效的。     

超平面布线

本文大胆打破了传统通道模型的束缚,建立了一个能更好体现多层布线内在本质约束的新模型：超平面布图模型,在该模型下提出了超平面布线算法。该算法以全新的逆向删冗策略成功地解决了布线线序的问题,使线网布线真正达到了并行处理。算法遵循了王守觉先生关于总体分析的方法作为解决超平面布线问题的指导思想,以布线层数最少化和通孔最少化为目标,通过动态地分析线网间的相互位置关系,全局考虑去释放各线网占据的不合理布线资源     

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.     

Fast coupled noise estimation for crosstalk avoidance in the MCGmultichip module autorouter

A multilayer, multichip module (MCM) router, called MCG, is introduced for x-y routing. An efficient method has been derived to allow candidate routes for the nets to be considered simultaneously for compatibility rather than incrementally extending routes or routing one net at a time as in many other techniques. This allows incorporation of accurate models for determining the potential for crosstalk problems during the routing process. MCG incorporates a crosstalk avoidance procedure which facilitates correct-by-design routing in systems susceptible to noise problems. In comparisons with other routers on industrial benchmarks, the MCG router has shown substantial improvement in routing density, number of layers, number of vias, and total interconnect length over routers such as V4R and SLICE. Our test results show up to 18% improvement in via count and up to 33% improvement in the required number of routing layers for these examples over V4R. One of the benchmarks presented contains 37 VHSIC gate arrays, over 7000 nets, and over 14000 pins (pads). Routing at finer pitches with crosstalk avoidance shows a further improvement in interconnect density