Design And Optimization Of Interconnection For Giant Large Scale Integration

With technology scaling, on-chip interconnects become an increasingly critical determinant of performance, manufacturability and reliability in high-end GLSI designs. The increasing of circuits scale as well as the more prominent parasitic effects of the on-chip interconnects bring huge challenge to the design of integrated circuit. IC design automation is a rapid development, changing, interdisciplinary and algorithm-intensive fields, where exists lots of large-scale numerical problems and combinational optimization problems. Therefore, it draws great concern of both academic and industrial partners. Recently, interconnect design and optimization is becoming a hot research area and will be the forefront of IC design automation in the near future. Under this situation, this thesis investigates on-chip interconnect network analysis and design optimization algorithms which covers clock network, power/ground network and the signal network. It is hoped that these discussions presented in this thesis can push forward the research work on the design and optimization methodology of interconnect-centric design.This thesis is proposed after investigating and summarizing interconnect optimization algorithms extensively. It analyzes the optimization problems of clock network, power/ground network as well as the signal network, which covers all global interconnect networks. Also, it discusses the basic mathematical theory behind these optimization problems and introduces some practical design and optimization algorithms. This thesis consists of three parts, corresponding to various aspects of global interconnect design issues under Ultra Deep Sub-Micron (UDSM) and Nanometer technology. The first part analyzes the design reliability problem of clock network. To consider the performance degradation of the clock network caused by process variation, this thesis discusses process variation resistance design methodology based on a tree topology. The second part closely investigates the transient analysis and optimization problems of large scale on chip power/ground network. A fast time domain analysis algorithm and related optimization algorithm based on the special chain structure on the power/ground mesh is introduced to improve the solving accuracy and to accelerate the analysis speed. The third part research works considering the crosstalk noise problem in the signal network, especially under the USDM and Nanometer process are presented. Which design stage is more favorable to resolve the issue of crosstalk noise is discussed in this thesis. An efficient crosstalk reduction algorithm by synthesizing the allocation of resources in three successive design stages, layer assignment, via assignment and track assignment, is also introduced in this thesis. The main contributions of this thesis are as follows:A new buffered clock tree routing algorithm which prevents the influence of process variations to clock skew is proposed. A novel branch sensitivity factor (BSF) model is given to measure the effect of process variation. An efficient algorithm which can construct special tree topology by applying a remerging operation to the clock tree node is introduced. Because the operation is guided by the proposed branch sensitivity factor model, this algorithm can reduce the performance degradation of clock tree caused by process variation effectively. Also, the buffer insertion process is integrated into the presented optimization process. Due to the optimization of the buffer location and buffer number, the impact of process variation can be further reduced and the interconnect delay is improved simultaneously. The experimental results show that this algorithm can reduce the 60%-80% screw variation and only induces less than 14% incensement of the clock network wire length as penalty.A fast power/ground network transient analysis algorithm is given and the behind basic principles are discussed in this thesis. In order to improve the analysis speed and accuracy, the chain structures in the power supply network is carefully considered when standard cell layout mode is used in the design flow. By compacting the middle node using the circuit equivalent model, the size of the system simulation matrix is reduced obviously. After solving the reduced system, all the original nodes in the power network can be recalculated in an error-free model. That is why this process can accelerate the simulation speed. For mesh structures of power supply networks, a relaxing strategy is used to perform the circuit partition. Different from the existing multi-grid based methods, this method not only avoids constructing dense analysis matrix, but also avoids inversing the matrix explicitly. Also, the partition error can be compensated by related refinement algorithm. Finally, the result got by this method is even more accurate than traditional method. Compared with the result given by commercial simulation tool SPICE, by using this algorithm, the analysis speed is accelerated by two magnitudes while the simulation accuracy is within 0.035% error bond.A heuristic power/ground network optimization algorithm using partition strategy and considering the leakage current of decoupling capacitors is given in this thesis. This research work aims at reducing the computation complexity of large scale power/ground network optimization problem. The random walk method here is integrated with a relaxing strategy to perform the circuit partition operation, which greatly reduce the problem size. On the other hand, base on the leakage model of decoupling capacitor, a two-stage optimization algorithm, which optimizes the wire width first then considers the placement of the decoupling capacitors is presented. This method can fully exploit the advantages of each stage in noise elimination, and that is why this integrated algorithm can get better result than the traditional algorithm. The experimental results show that compared with the published similar algorithms, which can only handle 1K node network, our algorithm can handle 11M node network with more optimal efficiency.A heuristic crosstalk reduction algorithm by resource assignment is considered. The algorithm combines layer assignment, cross-point assignment and track assignment, the intermediate steps as a whole to solve a series of problems raised in the UDSM era. To reduce complexity, the slice based divide and conquer strategy is used in two resource allocation stages, the shielding planning stage and the detail allocation stage. The experimental results show that the slice based strategy can greatly reduce the searching space of this optimization problem and improve the algorithm efficiency. On the other hand, in the detail allocation stage, due to the use of dynamic priority queue, the priority of each routing segment is updated according to the overall resource usage and diffident difficulties in placing each routing segment. This technique can reduce the assignment sensitivity caused by the resource allocation order and can reduce the interconnect noise in a more efficient way. The experimental results show that under the same successful ratio of resource allocation process, the interconnect crosstalk noise is reduced by 6-32 times compared with the similar published algorithms.In this thesis, issues of interconnect design and optimization in modern IC design are investigated. It covers the related design reliability, large scale circuit modeling and simulation as well as the signal integrity caused by crosstalk noise. This work is a typical research work in IC design automation field considering the interconnect-centric design. It is also a good reference for other researchers and designers working in this field.