Post-Silicon Tunable (PST) buffers are widely adopted in high-performance integrated circuits to fix timing violations introduced by process variations. In typical optimization procedures, the statistical timing analysis of the circuits with PST clock buffers will be executed more than 2000 times for large scale circuits. Therefore, the efficiency of the statistical timing analysis is crucial to the PST clock buffer optimization algorithms. In this paper, we propose a stochastic collocation based efficient statistical timing analysis method for circuits with PST buffers. In the proposed method, we employ the Howard algorithm to calculate the clock periods of the circuits on less than 100 deterministic sparse-grid collocation points. Afterwards, we use these obtained clock periods to derive the yield of the circuits according to the stochastic collocation theory. Compared with the state-of-the-art statistical timing analysis method for the circuits with PST clock buffers, the proposed method achieves up to 22X speedup with comparable accuracy.

In this paper, a complete SSTA scheme is proposed to calculate the output waveform of a logic cell on any random selected point in the process variational space, or the mean value and variance of the output signal with very high accuracy and acceptable CPU cost. At first, Miller capacitances between the input nodes and internal nodes of a logic cell are introduced to construct the improved MCSM model so as to improve the modeling accuracy. Secondly, the stochastic collocation method jointed with the Modified Nested Sparse Grid technique is adopted for SSTA procedure to avoid the exponential increase of the collocation points number caused by tensor product. Thirdly, a Nominal waveform based Fast Simulation Method is developed to speedup the simulation on each collocation point. At last, Automatic Waveform Construction Technique is developed to construct the output waveform with the approximation points as little as possible to decrease the computational cost while guaranteeing high accuracy. Numerical results are also given to demonstrate the efficiency of the proposed algorithm.

In this paper, a Stochastic Collocation Algorithm combined with Sparse Grid technique (SSCA) is proposed to deal with the periodic steady-state analysis for nonlinear systems with process variations. Compared to the existing approaches, SSCA has several considerable merits. Firstly, compared with the moment-matching parameterized model order reduction (PMOR) which equally treats the circuit response on process variables and frequency parameter by Taylor approximation, SSCA employs Homogeneous Chaos to capture the impact of process variations with exponential convergence rate and adopts Fourier series or Wavelet Bases to model the steady-state behavior in time domain. Secondly, contrary to Stochastic Galerkin Algorithm (SGA), which is efficient for stochastic linear system analysis, the complexity of SSCA is much smaller than that of SGA for nonlinear case. Thirdly, different from Efficient Collocation Method, the heuristic approach which may result in "Rank deficient problem" and "Runge phenomenon," Sparse Grid technique is developed to select the collocation points needed in SSCA in order to reduce the complexity while guaranteing the approximation accuracy. Furthermore, though SSCA is proposed for the stochastic nonlinear steady-state analysis, it can be applied to any other kind of nonlinear system simulation with process variations, such as transient analysis, etc.

In this paper, we propose a Modified nested sparse grid based Adaptive Stochastic Collocation Method (MASCM) for block-based Statistical Static Timing Analysis (SSTA). The proposed MASCM employs an improved adaptive strategy derived from the existing Adaptive Stochastic Collocation Method (ASCM) to approximate the key operator MAX during timing analysis. In contrast to ASCM which uses non-nested sparse grid and tensor product quadratures to approximate the MAX operator for weakly and strongly nonlinear conditions respectively, MASCM proposes a modified nested sparse grid quadrature to approximate the MAX operator for both weakly and strongly nonlinear conditions. In the modified nested sparse grid quadrature, we firstly construct the second order quadrature points based on extended Gauss-Hermite quadrature and nested sparse grid technique, and then discard those quadrature points that do not contribute significantly to the computation accuracy to enhance the efficiency of the MAX approximation. Compared with the non-nested sparse grid quadrature, the proposed modified nested sparse grid quadrature not only employs much fewer collocation points, but also offers much higher accuracy. Compared with the tensor product quadrature, the modified nested sparse grid quadrature greatly reduced the computational cost, while still maintains sufficient accuracy for the MAX operator approximation. As a result, the proposed MASCM provides comparable accuracy while remarkably reduces the computational cost compared with ASCM. The numerical results show that with comparable accuracy MASCM has 50% reduction in run time compared with ASCM.

In this paper, we propose an Adaptive Stochastic Collocation Method for block-based Statistical Static Timing Analysis (SSTA). A novel adaptive method is proposed to perform SSTA with delays of gates and interconnects modeled by quadratic polynomials based on Homogeneous Chaos expansion. In order to approximate the key atomic operator MAX in the full random space during timing analysis, the proposed method adaptively chooses the optimal algorithm from a set of stochastic collocation methods by considering different input conditions. Compared with the existing stochastic collocation methods, including the one using dimension reduction technique and the one using Sparse Grid technique, the proposed method has 10x improvements in the accuracy while using the same order of computation time. The proposed algorithm also shows great improvement in accuracy compared with a moment matching method. Compared with the 10,000 Monte Carlo simulations on ISCAS85 benchmark circuits, the results of the proposed method show less than 1% error in the mean and variance, and nearly 100x speeds up.