University of California Los Angeles
EDA 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 worst­case skew by exhaustive search of time­variant 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­cache), 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 SRC’07 [C105].

 

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.

 

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.

 

 


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