基于拓扑分析的多层通道布线算法

本文提出了一种基于拓扑分析的多层通道布线算法。算法把整个布线过程分成拓扑分层和物理布线两个部分。拓扑分层利用线段交叠图及模拟退火算法解决线段分层及通孔最少化问题，物理布线过程引入虚拟走线道解决交叉问题，再利用轮廓线跟踪的方法来决定最终确定各线段的布线位置。算法还解决了多层布线分层的管脚约束问题和相邻约束问题。实验结果表明，这是一种有效的方法。     

Three-step pin assignment algorithm for building block layout

A new pin assignment algorithm is proposed which can be used in floorplanning and building block layout to minimise the total wiring length and channel area while satisfying the minimum distance constraint among pin positions on the block boundary. This algorithm can be used in floorplanning in which block shapes are iteratively modified by the channel density obtained as a result of global routing. The proposed pin assignment algorithm occurs in three steps: approximate pin assignment, global routing and detailed pin assignment. Experimental results were obtained using MCNC placement and floorplanning benchmark examples.<>     

MCM routing algorithm based on a compatibility graph approach

A new algorithm for general area multichip module routing using a multi-candidate and compatibility graph approach, which maximises routing density while minimising vias and total wire length, is presented. Experimental results using standard industrial benchmarks show improved results relative to a commercial router and other previously proposed routers while offering flexibility for future incorporation of noise and delay constraints     

一个快速高效进行布线拥挤优化的总体布线器

设计实现了一个高效的线长模式下基于多处理机的并行总体布线器.通过对非时延驱动模式下串、并行算法的总运行时间和求解时间的比较,表明该并行算法能够在保证求解质量无明显变化的前提下大大加快总体布线算法的求解速度.同时,也提出了基于分布式体系结构的并行总体布线算法.     

ALGA: Automated layout generator for analog CMOS circuits

A computer-aided design (CAD) system called ALGA for an analog circuit layout is presented. The main contribution of this paper is to construct a weight graph that represents the topological connectivity of a given analog circuit. By using the weight graph, some efficient techniques can be designed to avoid devices mismatch and place all devices according to the device size constraints. Moreover, an algorithm is presented to perform the device placement step and propose an effective approach to reduce noise coupling in the routing step. A design method has been implemented in several Complementary Metal Oxide Semiconductor (CMOS) analog circuits. It is seen that the proposed system can generate good analog circuit design.     

超大规模集成电路无网格布线算法研究

本文提出一种高性能超大规模集成电路无网格布线算法，对于给定的布线平面，算法首先生成该布线平面的非均匀网格图，然后以绕障长度为布线参数，采用优化迷宫算法完成具体的布线过程。算法保证能够找到存在的最短布线路径，并能进行变线宽、变线距布线，布线速度很快，效果很好。     

Crosstalk and Wire Length Reduction in the Non-Manhattan Channel Routing

With the recent advances in VLSI fabrication technology, the device sizes have shrunk blow 0.1 μm. Due to the scaling down of device geometry in deep-submicron technologies, the crosstalk between adjacent nets has become a major concern in high performance VLSI circuit design. Increased crosstalk can cause signal delays, logic hazards, and even malfunctioning of circuits, and thus controlling the level of crosstalk in a chip has become an important task for IC designers. It’s well known …     

结合改进A*算法与拆线重布的有序逃逸布线

逃逸布线是印刷电路板设计的一个重要组成部分。针对并行逃逸布线的方法用于较大规模电路板布线时速度慢且结果不够好的问题,该文提出一种结合改进A*算法与拆线重布的有序逃逸布线方法。首先,通过代价预估函数确定引脚的布线顺序,使用改进A*算法初始化有序逃逸布线。接着,优化同长度布线路径,调整拥挤区域布线路径。最后,使用A*算法和广度优先搜索进行拆线重布。实验结果表明,该方法对给出的所有测试用例都实现了100%的逃逸,得到有序逃逸路径的可行解非常接近最优解,CPU时间比布尔可满足性问题(SAT)算法与最小费用多商品流(MMCF)算法平均减少分别约为95.6%, 97.8%,总体线长也接近最优。提出的方法能够明显减少寻找可行解的时间,提高布线质量。     

SafeResynth: A new technique for physical synthesis

Physical synthesis is a relatively young field in Electronic Design Automation. Many published optimizations for physical synthesis end up hurting the quality of the final design, often because they neglect important physical aspects of the layout, such as long wires or routing congestion. Our work defines and explores the concept of physical safeness and evaluates empirically its impact on route length, via count and timing. In addition, we propose a new physically safe and logically sound optimization, called SafeResynth, which provides immediately measurable improvements without altering the design's functionality. SafeResynth can enhance circuit timing without detrimental effects on route length and congestion. We achieve these improvements by performing a series of netlist transformations and re-placements that are individually evaluated for logical soundness (that is, they do not alter the logic functionality) and for physical safeness. When used alone, SafeResynth improves circuit delay of IWLS’05 benchmarks by 11% on average after routing, while increasing route length by less than 0.2%. Since transistors are not affected by SafeResynth, it can also be applied to post-silicon debugging, where only metal fixes are possible.     

具有单元自动生成的多元胞布图方法

本文提出一种新的多元胞自动布图方法.主要由四个部分构成,块的生成、块内一维布局、单元生成、通道布线.其中第一部分采用了分析的方法完成各个块的生成,目标为使连线最短和块之间连线和隔块连线最少.第二部分中引入了伪单元的概念以处理含有约束的一维布局问题,解决了各个块之间的相互连线关系以及隔块连线.第三部分中的单元生成,引入了类似硅编译的一些思想,在硅编译与传统的自动布局方法之间的结合方面做一些有益的尝试.第四部分的通道布线是一个比较灵活的方法,可以解决用户提出的各种工艺上的要求的布线,提高了布图的物理性能. 整个过程用C语言编成程序并已在PCS-68000机上运行.     

Wire Topology Optimization for Low Power CMOS

An increasing fraction of dynamic power consumption can be attributed to switched interconnect capacitances. Non-uniform wire spacing depending on activity had shown promising power reductions for on-chip buses. In this paper, a new and fast routing optimization methodology based on non-uniform spacing is proposed for entire circuits. No area investment is required, since whitespace remaining after detailed routing is exploited. The proposed methodology has been implemented and tapped into an industry-proven design flow. Wire power reductions of up to 9.55% for modern multiprocessor benchmarks with tight area constraints are demonstrated, twice as much as approaches that do not take switching activities into account. Timing is not adversely affected, and the yield limit is slightly improved.      

A buffer distribution algorithm for high-performance clock netoptimization

We propose a new approach for optimizing clock trees, especially for high-speed circuits. Our approach provides a useful guideline to a designer, by user-specified parameters, and three of these tradeoffs are provided in this paper. (1) First, to provide a “good” tradeoff between skew and wire length, a new clock tree routing scheme is proposed. The technique is based on a combination of hierarchical bottom-up geometric matching and minimum rectilinear Steiner tree. Our experiments complement the theoretical results. (2) For high-speed clock distribution in the transmission line mode (e.g., multichip modules) where interconnection delay dominates the clock delay, buffer congestion might exist in a layout. Using many buffers in a small wiring area results in substantial interline crosstalks as well as wirability, when the elongation of the imbalanced subtrees is necessary. Placing buffers evenly (locally or globally) over the plane at the minimum impact on wire length increase helps avoid buffer congestion and results in less crosstalk between clock wires. Thus, an effective technique for buffer distribution is proposed. Experimental results verify the effectiveness of the proposed algorithms. (3) Finally, a postprocessing step constraining on phase-delay is also proposed. The technique is based on a combination of hierarchical bottom-up geometric matching and bounded radius minimum spanning tree. The proposed algorithm has an important application in MCM clock net synthesis as well as VLSI clock net synthesis     

Timing-driven MultiChip Module routing algorithm with crosstalk consideration

This paper presents a timing-driven MultiChip Module （MCM） routing algorithm considering crosstalk, which maximizes routing density while minimizing vias and total wire length. The routing algorithm allows a more global solution as well as the incorporation of more accurate crosstalk modeling. In addition, various time domain characteristics of MCM are analyzed in this contribution. A deembedding technique for the S-parameter calculation is presented and functions for the time-domain signals are investigated in order to decrease the computation time. Routing results show that the proposed algorithm consistently produces the better results than other previously proposed routers while offering flexibility for future incorporation of noise and delay constraints.     

一个快速高效进行布线拥挤优化的总体布线器

设计实现了一个高效的线长模式下基于多处理机的并行总体布线器.通过对非时延驱动模式下串、并行算法的总运行时间和求解时间的比较,表明该并行算法能够在保证求解质量无明显变化的前提下大大加快总体布线算法的求解速度.同时,也提出了基于分布式体系结构的并行总体布线算法.     

A heuristic for constructing a rectilinear Steiner tree by reusing routing resources over obstacles

The obstacle-avoiding rectilinear Steiner minimal tree (OARSMT) problem is a hot topic in very-large-scale integration physical design. In practice, most of the obstacles occupy the device layer and certain lower metal layers. Therefore, we can place wires on top of the obstacles. To maximize routing resources over obstacles, we propose a heuristic for constructing a rectilinear Steiner tree with slew constraints. Our algorithm adopts an extended rectilinear full Steiner tree grid as the routing graph. We mark two types of Steiner point candidates, which are used for constructing Steiner trees and refining solutions. A shortest path heuristic variant is designed for constructing Steiner trees and it takes into account slew constraint by inhibiting growth. Furthermore, we use a pre-computed strategy to avoid calculating slew rate repeatedly. Experimental results show that our algorithm maximizes routing resources over obstacles and saves routing resources outside obstacles. Compared with the conventional OARSMT algorithm, our algorithm reduces the wire length outside obstacles by as much as 18.74% and total wire length by as much as 6.03%. Our algorithm improves the latest related algorithm by approximately 2% in terms of wire length within a reasonable running time. Additionally, calculating the slew rate only accounts for approximately 15% of the total runing time.     

VLSI总体布线算法研究与实现

总体布线是布图设计中一个极为重要的设计环节。本文提出了基于可分离最小生成树(SMST)的优化L形直角斯坦(Steiner)树(L_RST)和优化Z_RST的算法。该算法实现上绕开计算重合度问题，以新的角度计算代价。利用基于tile的结构，实现了伪管脚(pseudo pin)的分配，适用于现代多层布线需求。最后文章研究了同时考虑串扰和时延的综合性能驱动的总体布线算法改进。     

基于SKILL语言的按比例自动缩放版图方法

使用程序自动缩放版图设计实现硬核的快速工艺移植。版图中对象位置和形状由点的序列构成,对各点乘以相同的缩放因子可以在不改变对象形状的前提下对任意形状对象进行缩放或位置搬移。基于此原理采用建立函数库的方法构建程序,使用递归算法处理层次化的版图并给出编程修改DRC错误的实例。在给出SKILL程序实现的基础上给出了一个完整的设计流程。实践结果显示设计时间缩短、硬核性能得到提高,面积缩小48％,门延时缩短40％。     

合理偏差驱动的时钟线网构造及优化

提出了一种新的时钟布线算法 ,它综合了 top- down和 bottom- up两种时钟树拓扑产生方法 ,以最小时钟延时和总线长为目标 ,并把合理偏差应用到时钟树的构造中 .电路测试结果证明 ,与零偏差算法比较 ,该算法有效地减小了时钟树的总体线长 ,并且优化了时钟树的性能     

Physical design of testable CMOS digital integrated circuits

A methodology for physical testability assessment and enhancement, implemented with a set of test tools, is presented. The methodology, which can improve the physical design of testable CMOS digital ICs, is supported in realistic fault-list generation and classification. Two measures of physical testability, weighted class fault coverage and fault incidence, and one measure of fault hardness are introduced. The testability is evaluated prior to fault simulation; difficult-to-detect faults are located on the layout and correlated with the physical defects which originate them; and suggestions for layout reconfiguration are provided. Several design examples are described, ascertaining the usefulness of the proposed methodology. The proposed methodology demonstrated that stuck-at test sets only partially cover the realistic faults in digital CMOS designs. Moreover, it is shown that classical fault models of arbitrary faults are insufficient to describe the realistic fault set. Simulation results have shown that the fault set strongly depends on the technology and on the layout style