考虑布线资源松弛的X结构Steiner最小树算法

为了进一步考虑X结构,并充分利用障碍内可用布线资源,文中提出考虑布线资源松弛的X结构Steiner最小树算法.为了能够求解离散问题,在粒子的更新操作中引入交叉算子和变异算子.通过构建查找表,为整个算法流程提供快速的信息查询.提出角点选取策略,通过引入一些障碍角点,使粒子满足约束.最后构建精炼策略,进一步提高最终布线树的质量.实验表明,文中算法充分利用障碍内可用布线资源,有效缩短总布线长度,取得较佳的总布线长度.     

X结构下VLSI多层绕障Steiner最小树算法

Steiner最小树作为VLSI布线的基础模型,应进一步考虑到X结构、障碍物、多层等条件,文中基于粒子群优化提出了多层绕障X结构Steiner最小树算法.首先引入边变换操作以改变布线树的拓扑,使其具有较强的绕障能力;为了避免边变换操作带来的布线树环路问题,结合并查集策略设计新的操作算子;为了保证布线边不违反约束,提出一个与绕障情况及通孔数相关的惩罚函数策略,从而优化了多层布线中布线总代价这一最重要的目标.实验结果表明,相对于同类算法,该算法在布线总代价的优化能力上是最强的.     

Zero skew clock routing in X-architecture based on an improved greedy matching algorithm

As technology advances into nanometer territory, clock network layout plays an increasingly important role in determining circuit quality indicated by timing, power consumption, cost, power supply noise and tolerance to process variation. To alleviate the challenges to the existing routing algorithms due to the continuous increase of the problem size and the high-performance requirement, X-architecture has been proposed and applied to routing in that it can reduce wirelength and via counts, and thus improves the performance and routability compared with the conventional Manhattan routing. In this paper, we investigate zero skew clock routing using X-architecture based on an improved greedy matching algorithm (GMZSTX). The fitted Elmore delay model is employed to improve the accuracy over the Elmore delay model. The interactions among distance, delay balance and load balance are analyzed. Based on this analysis, an effective and efficient greedy matching scheme is suggested to reduce wire snaking and to get a more balanced clock tree. The proposed algorithm is simple and fast for practical applications. Experimental results on benchmark circuits show that our algorithm (GMZSTX) achieves a reduction of 8.15% in total wirelength, 30.19% in delay and 55.31% in CPU time on average compared with zero skew clock routing in the Manhattan plane (BB+DME-2, which means using the top-down balanced bipartition (BB) method [T.H. Chao, Y.C. Hsu, J.M. Ho, et al., Zero skew routing with minimum wirelength, IEEE Trans. Circuits Syst. II—Analog & Digital Signal Process 39 (11) (1992) 799–814] to generate the tree topology and using the Deferred-Merge Embedding (DME) algorithm [T.H. Chao, Y.C. Hsu, J.M. Ho, et al., Zero skew routing with minimum wirelength, IEEE Trans. Circuits Syst. II—Analog & Digital Signal Process 39 (11) (1992) 799–814] to embed the internal nodes), and reduces delay and CPU time by 17.44% and 62.21% on average over the BB+DME-4 method (which is similar to BB+DME-2, but routing in X-architecture). Our SPICE simulation further verifies the correctness of the resulting clock tree.     

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

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

PIXAR: A performance-driven X-architecture router based on a novel multilevel framework

As technology advances into the nanometer territory, the interconnect delay has become a first-order effect on chip performance. To handle this effect, the X-architecture has been proposed for high-performance integrated circuits. In this paper, we present a performance-driven X-architecture router based on a novel multilevel framework, called PIXAR. To fully consider performance-driven routing and take advantage of the X-architecture, PIXAR applies a novel multilevel routing framework, which adopts a two-stage technique of top-down uncoarsening followed by bottom-up coarsening, with a trapezoid-shaped track routing embedded between the two stages to assign long, straight diagonal segments for wirelength reduction. We also propose a performance-driven X-Steiner tree algorithm based on the delaunay triangulations to construct routing tree for performance optimization. Compared with the state-of-the-art work, PIXAR achieves 100% routing completion for all circuits while reduced the net delay.     

XGRouter: high-quality global router in X-architecture with particle swarm optimization

This paper presents a high-quality very large scale integration (VLSI) global router in X-architecture, called XGRouter, that heavily relies on integer linear programming (ILP) techniques, partition strategy and particle swarm optimization (PSO). A new ILP formulation, which can achieve more uniform routing solution than other formulations and can be effectively solved by the proposed PSO is proposed. To effectively use the new ILP formulation, a partition strategy that decomposes a large-sized problem into some small-sized sub-problems is adopted and the routing region is extended progressively from the most congested region. In the post-processing stage of XGRouter, maze routing based on new routing edge cost is designed to further optimize the total wire length and mantain the congestion uniformity. To our best knowledge, XGRouter is the first work to use a concurrent algorithm to solve the global routing problem in X-architecture. Experimental results show that XGRouter can produce solutions of higher quality than other global routers. And, like several state-of-the-art global routers, XGRouter has no overflow.     

Discharge-path-based antenna effect detection and fixing for X-architecture clock tree

Antenna effect is a phenomenon in the plasma-based nanometer process and directly influences the manufacturing yield of VLSI circuits. Because antenna-critical metal wires have sufficient charges to damage the thin gate oxides of the clock input ports connected by a clock tree, the standard cells or IPs cannot be driven by the clock source synchronously. For a given X-architecture clock tree that connects n clock sinks, we consider the antenna effect in the clock tree and propose a discharge-path-based antenna effect detection method. To fix the antenna violations, we use the jumper insertion technique recommended by foundries. Furthermore, we integrate the layer assignment technique to reduce the inserted jumper and via counts. Differing from the existing works, the delay of vias is considered in delay calculation, and a wire sizing technique is applied for clock skew compensation after fixing the antenna violations. Experimental results on benchmarks show that our algorithm runs in O(n²) to averagely insert 48.21% less jumpers and reduce 20.35% in vias compared with other previous algorithms. Moreover, the SPICE simulation further verifies the correctness of the resulting clock tree.     

Pattern-matching-based X-architecture zero-skew clock tree construction with X-Flip technique and via delay consideration

As IC fabrication technologies get into nanometer era, clock routing gradually dominates chip performance indicated by delay, cost, and power consumption. X-architecture can be applied for routing metal wires in diagonal and rectilinear directions to overcome the above challenges due to wirelength reduction. In this paper, we present a clock routing algorithm, called PMXF, to construct an X-architecture zero-skew clock tree with minimum delay. An X-pattern library is defined for simplifying the merging procedure of the DME approach, an X-Flip technique is proposed for reducing the wirelength between the paired points, and a wire sizing technique is applied for achieving zero skew. In terms of clock delay, wirelength, power consumption, and via count listed in the experimental results on benchmarks, the proposed PMXF algorithm can respectively achieve more reductions compared with other previous X-architecture clock routing algorithms.