The Algorithm Study On Signal-Integrity Main Problems In Deep Submicron VLSI Power Grids

With the great progress of modern deep submicron VLSI, there is an increased demand for high performance and low power supply IC designs. High performance is achieved by shrinking feature size, increased functionality, lower supply voltage and improved technology. This results in more complex power distribution networks. A robust power grids design is essential to ensure that the circuits on a chip operate reliably at the guaranteed level of performance. So the signal-integrity in power grids has now become the key problem and an attractive research topic in the IC Physical design.Signal-integrity problem in power grids consists of IR-drop and Ldi/dt-drop on the multilevel metal connections in which may include tens of millions nodes, and this leads to variation of supply voltage, reduced noise margins, higher logic gate delays and overall slower circuits. Efficient analysis of power grids is necessary for predicting the performance and improving the performance if necessary. But the difficulty in power grids analysis stems mainly from three sources:1. Network is very large, typically 1 million to 100 million nodes;2. Network is nonlinear as it contains switching devices;3. Voltage and current distribution in the network is dependent on the instruction executed on the processor.But now current commercial simulation tools are not able to deal with this kind huge power grid system. So there is an intense requirement for new efficient techniques, in terms of both execution time and memory, for the analysis of power grids to make tradeoff between simulation accuracy and cost of CPU. Several problems are studied on the signal-integrity in power grids. The main contributions are as follows:1. Based on the physical structure of VLSI power grid, signal-integrity problems in power grids and the key issues in design and analysis of power grids are studied. Also the model of VLSI power grids is made in-depth analysis.2. Based on the comparisons of current different power grids analysis methods in the world, their advantages and disadvantages are summaried according to their capability and computational speed. The partition and compact techniques to reduce the scale of original power grids are researched in detail. And effective methods for compressing network are proposed to accelarate numerical simulation.3. An efficient storage strategy used to save the memory is proposed in this dissertation. One dimensional row-indexed compact sparase matrix storage structured approach is proposed to compress the coefficient matrix. Only non-zero elements are stored and the zero elements are ignored in each line of the coefficient matrix. In this way, the matrix is substituted by a real array to store the non-zero elements and an integer array to store the corresponding column coordinate. So the matrix can be compressed in two sets of array. The storage cells are dramatically reduced and the computation has been sped up. This makes tradeoff between simulation accuracy and cost of CPU.4. Based on the compressed technique and the analysis of power grids, an improved krylov-subspace iterative algorithm is proposed to perform static and transient simulations for large-scale power grids, in which BCG and BiCGStab algorithms are adopted. Extensive experimental results on large-scale power grids show that proposed method is over two orders faster than Hspice simulation speed, and which has more powerful capability to deal with the increasing size of power grids in modern microprocessors than general-purpose circuit simulators with significant memory and run-time saving.5. With in-depth research of random walk algorithm, an improved algorithm is proposed to perform efficient transient simulations for large-scale VLSI power grid circuits and an excellent result is obtained. Based on the local characteristic of random walk in transient analysis, only partial walk, region separated and booking method are used in this new method, which has avoided the full network computing and accelerated the compute speed. Compared with traditional methods, the analysis speed of the presented method is much faster. Extensive experimental results on large-scale power grid circuits show that the improved method not only achieve speedups over than the existing approaches, but also are more robust in solving various types of industrial circuits and has an acceptable error margin.