University of California Los Angeles
Design Automation Laboratory

 

 

 

  1. Primary investigator (PI)
  2. Attended students
  3. Funding sources
  4. Related Project
  5. Research outcomes
  6. Publications

 

 

Variation Aware Modeling and Design

Primary Investigator (PI)

1.            Prof. Lei He

Attended Students

1.            Lerong Cheng

2.            Yan Lin

3.            Yiyu Shi

4.            King Ho Tam

5.            Phoebe Wong

6.            Jinjun Xiong

7.            Hao Yu

Research Outcomes

 

1.       Interconnect modeling and design with process variations - we demonstrated how much systematic CMP variation and random device variation can impact interconnect performance in [C55] (an invited talk) and [C63]. We further presented buffered interconnect synthesis with simultaneous fill insertion considering the above two types of variations at ISPD'05 [C67] and submitted the completed result to TCAD, which is currently under review. Recently, Jinjun Xiong and Prof. He revealed a few properties of comparing random variables and then developed an efficient pruning algorithm for random variables. The algorithm has a linear time complexity same as pruning deterministic variables, in constrast to the earlier work which aimed at accurate pruning using surface integrals at the expense of super-linear complexity [C64]. We further solved the buffer insertion problem considering device variations with spatial correlation, capable of handling 100x bigger designs compared to the existing non-deterministic methods.

 

2.       FPGA device and architecture evaluation considering process variation. Considering both die-to-die and within-die variations in effective channel length, threshold voltage, and gate oxide thickness, we developed closed-form models of leakage and timing variations at the FPGA chip level at ICCAD05[C71]. Experiments show that our models are within 3% from Monte Carlo simulation, and the leakage and delay variations can be up to 3X and 1.9X, respectively. We then derive analytical yield models considering both leakage and timing variations, and use such models to evaluate FPGA device and architecture similar to a commercial FPGA and device setting from ITRS roadmap, device tuning alone improves leakage yield by 39% and architecture and device co-optimization increases leakage yield by 73%.

 

3.       Place and Timing for FPGAs Considering Variations . Process variation affecting timing and power is an important issue for modern integrated circuits in nanometer technologies. FPGAs are similar to ASICs in their susceptibility to these issues, but face unique challenges in that critical paths are unknown at test time. This paper presents the first in-depth study on applying statistical timing analysis with cross-chip and on-chip variations to speed-binning and guard-banding in FPGAs. Considering the uniqueness of re-programmability in FPGAs, we quantify the effects of timing-model with guard-banding and speed-binning on statistical performance and timing yield. We also develop a new variation aware placement, which is the first statistical algorithm for FPGA layout and reduces yield loss by 3.4X with guard-banding and 25X with speed-binning for MCNC and QUIP designs. This paper was presented in FPL'06[C89].

 

4.       FPGA performance Optimization Via Chipwise Placement Considering Process Variations. Both custom IC and FPGA designs in the nanometer regime suffer from process variations. But different from custom ICs, FPGAs' programmability offers a unique design freedom to leverage process variation and improve circuit performance. We propose the following variation aware chipwise placement Low in this paper. First, we obtain the variation map for each chip by synthesizing the test circuits for each chip as a preprocessing step before detailed placement. Then we use the trace-based method to estimate the performance gain achievable by chipwise placement. Such estimation provides a lower bound of the performance gain without detailed placement. Finally, if the gain is significant, a variation aware chipwise placement is used to place the circuits according to the variation map for each chip. Our experimental results show that, compared to the existing FPGA placement, variation aware chipwise placement improves circuit performance by up to 19.3% for the tested variation maps. This paper was presented in FPL'06 [C88].

 

5.       Robust Extraction of Spatial Correlated Process Variation Model (Best Paper Award in ISPD'06 [C81]) Increased variability of process parameters and recent progress in statistical static timing analysis make extraction of statistical characteristics of process variation and spatial correlation an important yet challenging problem in modern chip designs. Unfortunately, existing approaches either focus on extraction of only a deterministic component of spatial variation or do not consider actual difficulties in computing a valid spatial correlation function and matrix, simply ignoring the fact that not every function and matrix can be used to describe the spatial correlation. Based upon the mathematical theory of random fields and convex analysis, in this paper, we develop (1) a robust technique to extract a valid spatial correlation function by solving a constrained nonlinear optimization problem; and (2) a robust technique to extract a valid spatial correlation matrix by employing a modified alternative projection algorithm. Our novel techniques guarantee to extract a valid spatial correlation function and matrix that are closest to measurement data, even if those measurements are affected by unavoidable random noises. Experiment results based upon a Monte-Carlo model confirm the accuracy and robustness of our techniques, and show that we are able to recover the correlation function and matrix with very high accuracy even in the presence of significant random noises.

 

6.       Statistical static timing analysis (SSTA) We develop a time efficient SSTA framework for non-Gaussian variation sources with non-linear delay model. We develop two approaches to handle max operation for block based SSTA: 1) we use Fourier Series to approximate the PDF of two random variables and then compute the max of them [C105]. 2) we use the second order polynomial to fit the max operation [C114]. Experimental result shows that compared to Monte-Carlo simulation, our approach predicts the mean, standard deviation, skewness, and 95% percentile point within 1%, 1%, 6%, and 1% error, respectively.

 

7.       Minimal Skew Clock Synthesis Considering Time Variant Temperature Gradient It is expensive, if not impossible to find the skew by exhaustive search of temperature maps on the scale of thermal time constant. On the other hand, different instructions or applications usually share some common resources (such as L2), and therefore temperature are temporally correlated. The temperature correlation information enables us to cluster temperature maps and to calculate the worst case skew more efficiently based on the clustered temperature maps. The second contribution of this paper is to develop an efficient algorithm,PErturbation based Clock Optimization (PECO) 1 leveraging the clustering idea to find a clock embedding with the minimal worst case skew. The experimental results show that our PECO algorithm reduces the worst case skew by up to 10X compared to DME within 1% wire length overhead. By combining PECO and cross link insertion, the worst case skew is reduced by up to 20X compared to DME and up to 7X compared to the original cross link insertion algorithm considering time invariant variations. This paper is presented in SRC07

8.       Decoupling Capacitance Budgeting Considering Current Correlation Including Process Variation [C108]. In this paper, we develop a novel stochastic model for current loads, taking into account operation variation such as temporal and logic-induced correlations and process variations such as systematic and random Leff variation. We propose a formal method to extract operation variation and formulate a new decap budgeting problem using the stochastic current model. We develop an effective yet efficient iterative alternative programming algorithm and conduct experiments using industrial designs. We show that under the same decap area and compared with the baseline model assuming maximum currents at all ports, the model considering temporal correlation reduces the noise by up to 5X, and the model considering both temporal and logic-induced correlations reduces the noise by up to 17X. Compared with using deterministic process parameters, considering Leff variation reduces the mean noise by up to 4X and the 3X noise by up to 13X when both applying the current model with temporal and logic-induced correlations. Therefore, we convincingly demonstrate the significance of considering both operation and process variations and open a new research direction for optimizing signal, power and thermal integrity with consideration of operation variation.

 

9.       PiCAP [C130]. It is unknown how to include stochastic process variation into fast-multipole-method (FMM) for a full chip capacitance extraction. This paper presents a parallel FMM extraction using stochastic polynomial expanded geometrical moments. It utilizes multiprocessors to evaluate in parallel for the stochastic potential interaction and its matrix-vector product (MVP) with charge. Moreover, a generalized minimal residual (GMRES) method with deflation is modified to incrementally consider the nominal value and the variance. The overall extraction flow is called piCAP. Experiments show that the parallel MVP in piCAP is up to 3X faster than the serial MVP, and the incremental GMRES in pi- CAP is up to 15X faster than non-incremental GMRES methods.

 

10.       QuickYield [C137]. With technology scaling down to 90nm and below, many yield-driven design and optimization methodologies have been proposed to com- bat the prominent process variation and to increase the yield. A critical issue that impacts the efficiency of all those methods is to estimate the yield given the design parameters under variation. Ex- isting methods either use Monte Carlo approach in performance do- main where thousands of simulations are required, or uses iterative search in parameter domain where a number of simulations are re- quired to characterize each point on the parameter boundary defined by the performance constraints. To improve the efficiency, in this pa- per we propose QuickYield, a direct non-iterative method where each point on the boundary can be obtained by a "one-shot" simulation. Experiments on different circuit instances show that for the same ac- curacy, QuickYield is up to 519X faster compared with the Monte Carlo approach, and up to 4.7X faster compared with YENSS, the fastest approach reported in literature.

 

11.       Stochastic Analog Circuit Behavior Modeling [C142]. Stochastic device parameter variations have dramatically increased beyond the scale of 65nm and can significantly lead to large mismatch for analog circuits. To estimate unknown analog circuit behavior in performance space under the given stochastic variations in parameter space, many state-of-art approaches have been developed recently. However, either Gaussian distribution or response surface model (RSM) with analytical formulae has to be assumed when connecting performance space and parameter space. A novel point-estimation based approach has been proposed in this paper to capture arbitrary stochastic distributions for analog circuit behaviors in performance space. First, to evaluate high-order moments of circuit behavior in an accurate fashion, the point-estimation method has been applied with only a few number of simulations. Then, probability density function (PDF) of circuit behavior can be efficiently extracted by the obtained high-order moments. This method is further extended for multiple parameters under linear complexity. Extensive numerical experiments on a number of different circuits have demonstrated that the proposed point-estimation method can provide up to 181X runtime speedup with the same accuracy, when compared with Monte Carlo method. Moreover, it can further achieve up to 15X speedup over the RSM-based method such as APEX with the similar accuracy. This work was presented at ISPD'11.

 

12.       Non-Monte-Carlo Transient Noise Analysis [C143]. Stochastic device noise has become a significant challenge for high-precision analog/RF circuits, and it is particularly difficult to correctly include both white noise and flicker noise into the traditional transient verification flow with efficient numerical solution. In this paper, a Non-Monte-Carlo transient noise analysis is developed. Both white noise and flicker noise are considered in the Ito integral based stochastic differential algebraic equation (SDAE), which is further solved with one-time calculation of variance using the stochastic orthogonal polynomials (SoPs). This work is the first to provide SoP based SDAE solution with application in transient noise analysis. Experiments on a number of different analog circuits demonstrate that the proposed method is up to 488X faster than Monte Carlo method with a similar accuracy, and achieves on average 6.8X speedup over existing non-Monte-Carlo approaches. This work was presented at DAC'11.

 

References

[C55]L. He, A. B. Kahng., K. Tam and J. Xiong, "Variability-Driven Considerations in the Design of Integrated-Circuit Global Interconnects", IEEE VLSI Multilevel Interconnection Conference, pp. 214-221, Oct 2004. (pdf) (ppt) (Invited paper).

[C63] L. He, A. B. Kahng, K. Tam and J. Xiong, "Design of IC Interconnects with Accurate Modeling of CMP", International Society for Optical Engineering (SPIE) Symposium on Microlithograhpy, pp. 109-119, March 2005. (pdf) (ppt).

[C64] J. Xiong, K. Tam and L. He, "Buffer insertion considering process variation", Design Automation and Test in Europe, pp. 970-975, Munich, Germany, March 2005. (pdf).

[C67] L. He, A. B. Kahng, K. Tam and J. Xiong, "Simultaneous Buffer Insertion and Wire Sizing Considering Systematic CMP Variation and Random Leff Variation", International Symposium on Physical Design, San Francisco, CA, pp.78-85, April 2005. (pdf) (ppt).

[C71] L. Cheng, P. Wong, F. Li, Y. Lin and L. He, "Device and Architecture Co-Optimization for FPGA Power Reduction", Design Automation Conference, Anaheim, CA, pp. 915-920, June 2005. (pdf) (ppt).

[C81] Jinjun Xiong, Vladimir Zolotov, Lei He, "Robust Extraction of Spatial Correlation," IEEE/ACM International Symposium on Physical Design, San Jose, CA, pp. 2-9, April 2006. (Best Paper Award ).  (pdf) (ppt).

[C88] Yan Lin, Mike Hutton and Lei He, "Placement and Timing for FPGAs Considering Variations", International Conference on Field Programmable Logic and Applications, August 2006 (pdf) (ppt)

[C89] Lerong Cheng, Jinjun Xiong, Lei He, "FPGA Performance Optimization via Chipwise Placement Considering Process Variations", International Conference on Field Programmable Logic and Applications, August 2006 (pdf).

[C105] Lerong Cheng, Jinjun Xiong and Lei He "Non-Linear Statistical Static Timing Analysis for Non-Gaussian Variation Sources", in Proceedings of IEEE/ACM Design Automation Conference, San Diego, California, 250-255, June 2007.

[C107] Hao Yu, Yu Hu, Chun-Chen Liu and Lei He, Minimal Skew Clock Synthesis Considering Time Variant Temperature Gradient. SRC Techcon Conference, 2007. (pdf) (ppt).

[C108] Yiyu Shi, Jinjun Xiong, Chunchen Liu and Lei He, "Efficient Decoupling Capacitance Budgeting Considering Current Correlation Including Process Variation", IEEE/ACM International Conf. on Computer-Aided Design (ICCAD), San Jose, CA, Nov. 2007. (nomination for Best Paper Award) (pdf) (ppt)

[C114] Lerong Cheng, Jinjun Xiong, and Lei He, "Non-Gaussian Statistical Timing Analysis Using Second-Order Polynomial Fitting", Proc. Asia South Pacific Design Automation Conf., 2008.

[C130] Fang Gong, Hao Yu, and Lei He, "PiCAP: A Parallel and Incrementel Capacitance Extraction Considering Stochastic Process Variation "DAC 2009,

[C137] Fang Gong, Hao Yu, Yiyu Shi, Daesoo Kim, Junyan Ren, Lei He, " An Efficient Non-Iterative Parametric Yield Estimation with Performance Constraints "47th IEEE Design Automation Conference (DAC'10), Anaheim, CA, June 13-18, 2010,

[C142] Fang Gong, Hao Yu, Lei He, "Stochastic Analog Circuit Behavior Modeling by Point Estimation Method",International Symposium on Physical Design 2011 (ISPD'11), Santa Barbara, California, March 27-30, 2011.,

[C143] Fang Gong, Hao Yu, Lei He, "Fast Non-Monte-Carlo Transient Noise Analysis for High-Precision Analog/RF Circuits by Stochastic Orthogonal Polynomials", 48th IEEE Design Automation Conference (DAC'11), San Diego, CA, June5-10, 2011.,

 

 


Send your comments to our webmaster.
Last update: 01-31-2008.