Process variation in nanometer technology is becoming an important issue for cutting-edge FPGAs with a multimillion gate capacity. Considering both die-to-die and within-die variations in effective channel length, threshold voltage, and gate oxide thickness, we first develop closed-form models of chip-level FPGA leakage and timing variations. Experiments show that the mean and standard deviation computed by our models are within 3% from those computed by Monte Carlo simulation. We also observe that the leakage and timing 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 the performance of FPGA device and architecture considering process variations. Compared to the baseline, which uses the VPR architecture and device setup based on the ITRS roadmap, device and architecture tuning improves leakage yield by 10.4%, timing yield by 5.7%, and leakage and timing combined yield by 9.4%. We also observe that LUT size of 4 gives the highest leakage yield, LUT size of 7 gives the highest timing yield, but LUT size of 5 achieves the maximum leakage and timing combined yield. To the best of our knowledge, this is the first in-depth study on FPGA architecture and device coevaluation considering process variation.

The most challenging problem in the current block-based statistical static timing analysis (SSTA) is how to handle the max operation efficiently and accurately. Existing SSTA techniques suffer from limited modeling capability by using a linear delay model with Gaussian distribution, or have scalability problems due to expensive operations involved to handle non-Gaussian variation sources or nonlinear delays. To overcome these limitations, we propose efficient algorithms to handle the max operation in SSTA with both quadratic delay dependency and non-Gaussian variation sources simultaneously. Based on such algorithms, we develop an SSTA flow with quadratic delay model and non-Gaussian variation sources. All the atomic operations, max and add, are calculated efficiently via either closed-form formulas or low dimension (at most 2-D) lookup tables. We prove that the complexity of our algorithm is linear in both variation sources and circuit sizes, hence our algorithm scales well for large designs. Compared to Monte Carlo simulation for non-Gaussian variation sources and nonlinear delay models, our approach predicts the mean, standard deviation and 95% percentile point with less than 2% error, and the skewness with less than 10% error.

Modeling spatial variation is important for statistical analysis. Most existing works model spatial variation as spatially correlated random variables. We discuss process origins of spatial variability, all of which indicate that spatial variation comes from deterministic across-wafer variation, and purely random spatial variation is not significant. We analytically study the impact of across-wafer variation and show how it gives an appearance of correlation. We have developed a new die-level variation model considering deterministic across-wafer variation and derived the range of conditions under which ignoring spatial variation altogether may be acceptable. Experimental results show that for statistical timing and leakage analysis, our model is within 2% and 5% error from exact simulation result, respectively, while the error of the existing distance-based spatial variation model is up to 6.5% and 17%, respectively. Moreover, our new model is also faster than the spatial variation model for statistical timing analysis and faster for statistical leakage analysis.

In this paper we study statistics of statistics. Statistical modeling and analysis have become the mainstay of modern design-manufacturing flows. Most analysis techniques assume that the statistical variation models are reliable. However, due to limited number of samples (especially in the case of lot-to-lot variation), calibrated models have low degree of confidence. The problem is further exacerbated when production volumes are low (¿ 65 lots) causing additional loss of confidence in the statistical analysis (since production only sees a small snapshot of the entire distribution). The problem of confidence in statistical analysis is going to be further worsened with advent of 450mm wafers. We mathematically derive the confidence intervals for commonly used statistical measures (mean, variance, percentile corner) and analysis (SPICE corner extraction, statistical timing). Our estimates are within 2% of simulated confidence values. Our experiments (with variability assumptions derived from test silicon data from a 45nm industrial process) indicate that for moderate characterization volumes (10 lots) and low-to-medium production volumes (15 lots), a significant guardband (e.g., 34.7% of standard deviation for single parameter corner, 38.7% of standard deviation for SPICE corner, and 52% of standard deviation for 95%-tile point of circuit delay) is needed to ensure 95% confidence in the results. The guardbands are non-negligible for all cases when either production or characterization volume is not large. We also study the interesting one production lot case which may be common for prototyping as well as for academic designs. The proposed methods require are not runtime-intensive (always within 10s) as they require Monte-Carlo simulations on closed form expressions.

Short-loop process monitoring structures (usually simple device I - V, C - V measurements made after M1 fabrication) are commonly put in wafer scribe-lines. These test structures are almost always design independent and measured/monitored by the foundry to keep track of process deviations. We propose a design-dependent process monitoring strategy which can accurately predict design performance based on simple Ieff-based delay and Ioff-based leakage power estimates. We show that our strategy works much better (0.99 correlation vs. 0.87) compared to conventional design-independent monitors. Further, we use the predicted delay and leakage power for early yield estimation for pruning bad wafers to save test and back-end manufacturing costs We show that wafer pruning based on our approach can achieve upto 98% of the maximum achievable benefit/profit. We design the measurement and prediction schemes so as to minimize data as well as computation that needs to be kept track of during wafer fabrication. Such design-dependent process monitoring can help target process control/optimization effort, enable quicker yield ramp besides saving test and manufacturing costs.

Majority of practical multivariate statistical analyses and optimizations model interdependence among random variables in terms of the linear correlation among them. Though linear correlation is simple to use and evaluate, in several cases non-linear dependence between random variables may be too strong to ignore. In this paper, We propose polynomial correlation coefficients as simple measure of multivariable non-linear dependence and show that need for modeling non-linear dependence strongly depends on the end function that is to be evaluated from the random variables. Then, we calculate the errors in estimation which result from assuming independence of components generated by linear de-correlation techniques such as PCA and ICA. The experimental result shows that the error predicted by our method is within 1% error compared to the real simulation. In order to deal with non-linear dependence, we further develop a target function driven component analysis algorithm (FCA) to minimize the error caused by ignoring high order dependence and apply such technique to statistical leakage power analysis and SRAM cell noise margin variation analysis. Experimental results show that the proposed FCA method is more accurate compared to the traditional PCA or ICA.

Modeling spatial variation is important for statistical analysis. Most existing works model spatial variation as spatially correlated random variables. We discuss process origins of spatial variability, all of which indicate that spatial variation comes from deterministic across-wafer variation, and purely random spatial variation is not significant. We analytically study the impact of across-wafer variation and show how it gives an appearance of correlation. We have developed a new dielevel variation model considering deterministic across-wafer variation and derived the range of conditions under which ignoring spatial variation altogether may be acceptable. Experimental results show that our model is within 1% error from exact simulation result while the error of the existing distance-based spatial variation model is up to 8%. Moreover, our new model is also 10X faster than the spatial variation model for Monte-Carlo analysis.

Nominal power estimation is quick but gives minimal information. Statistical power analysis can provide information on yield, chip robustness, etc., but current methods are unnecessarily slow and complex. This is primarily because existing leakage-power models, which model leakage power as lognormal distribution and calculate chip leakage power based on Wilkinson's approach, are not directly additive. Hence, for each incremental change of the circuit, the covariances between each pair of circuit elements need to be recalculated, which is inefficient. In this paper, we proposed a simple additive polynomial leakage-variation model. With additivity, we can calculate chip leakage power and leakage power after incremental change very efficiently. Experimental results show that our method is five times faster than the existing Wilkinson's approach while having no accuracy loss in mean estimation and about 1% accuracy loss in standard-deviation and 99%-percentile-point estimations.

For nanometer manufacturing, process variation causes significant uncertainty for circuit performance verification. Statistical static timing analysis (SSTA) is thus developed to estimate timing distribution under process variation. Most existing SSTA techniques have difficulty in handling the non-Gaussian variation distribution and nonlinear dependence of delay on variation sources. To address this problem, we first propose a new method to approximate the max operation of two non-Gaussian random variables through second-order polynomial fitting. With such approximation, we then present new non-Gaussian SSTA algorithms for three delay models: quadratic model, quadratic model without crossing terms (semiquadratic model), and linear model. All the atomic operations (max and sum) of our algorithms are performed by closed-form formulas; hence, they scale well for large designs. Experimental results show that compared to the Monte Carlo simulation, our approach predicts the mean, standard deviation, skewness, and 95% percentile point within 1%, 1%, 6%, and 1% error, respectively.

In the nanometer manufacturing region, process variation causes significant uncertainty for circuit performance verification. Statistical static timing analysis (SSTA) is thus developed to estimate timing distribution under process variation. However, most of the existing SSTA techniques have difficulty in handling the non-Gaussian variation distribution and non-linear dependency of delay on variation sources. To solve such a problem, in this paper, we first propose a new method to approximate the max operation of two non-Gaussian random variables through second-order polynomial fitting. We then present new non-Gaussian SSTA algorithms under two types of variational delay models: quadratic model and semi-quadratic model (i.e., quadratic model without crossing terms). All atomic operations (such as max and sum) of our algorithms are performed by closed-form formulas, hence they scale well for large designs. Experimental results show that compared to the Monte-Carlo simulation, our approach predicts the mean, standard deviation, and skewness within 1%, 1%, and 5% error, respectively. Our approach is more accurate and also 20x faster than the most recent method for non-Gaussian and nonlinear SSTA.

This paper develops a trace-based framework to enable concurrent process and FPGA architecture co-development. Based on process parameters and traces for FPGA applications, the framework calculates the chip level performance and power distribution and soft error rate (SER) with consideration of process variations and device aging. As examples to utilize the framework, the paper further applies heterogeneous gate lengths to logic and interconnects for energy reduction, and studies the interaction between device aging, process variation and SER

Existing statistical static timing analysis (SSTA) techniques suffer from limited modeling capability by using a linear delay model with Gaussian distribution, or have scalability problems due to expensive operations involved to handle non-Gaussian variation sources or non-linear delays. To overcome these limitations, we propose a novel SSTA technique to handle both nonlinear delay dependency and non-Gaussian variation sources simultaneously. We develop efficient algorithms to perform all statistical atomic operations (such as max and add) efficiently via either closed-form formulas or one-dimensional lookup tables. The resulting timing quantity provably preserves the correlation with variation sources to the third-order. We prove that the complexity of our algorithm is linear in both variation sources and circuit sizes, hence our algorithm scales well for large designs. Compared to Monte Carlo simulation for non-Gaussian variation sources and nonlinear delay models, our approach predicts all timing characteristics of circuit delay with less than 2% error.

Device optimization considering supply voltage Vdd and threshold voltage Vt has little chip-area increase but a great impact on power and performance in the nanometer technology. This paper studies simultaneous evaluation of device and architecture optimization for field-programmable gate arrays (FPGAs). We first develop an efficient yet accurate timing and power evaluation method called a trace-based model. By collecting trace information from a cycle-accurate simulation of placed and routed FPGA benchmark circuits and reusing the trace for different Vdds and Vts, we enable device and architecture cooptimization considering hundreds of device and architecture combinations. Compared to the baseline FPGA architecture, which uses the Versatile Place and Route architecture model and the same lookup table and cluster sizes as those used by the Xilinx Virtex-II, Vdd suggested by the International Technology Roadmap for Semiconductor, Vt optimized with respect to the preceding architecture, and Vdd architecture and device cooptimization can reduce the energy-delay product (ED) by 20.5% and the chip area by 23.3%. Furthermore, considering the power gating of unused logic blocks and interconnect switches (in this case, sleep transistor size is a parameter of device tuning), our co-optimization reduces ED by 55.0% and the chip area by 8.2% compared to the baseline FPGA architecture. To the best of our knowledge, this is the first in-depth study in the literature on architecture and device cooptimization for FPGAs.

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 chip-wise placement flow 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.

Device optimization considering supply voltage Vdd and threshold voltage Vt tuning does not increase chip area but has a great impact on power and performance in the nanometer technology. This paper studies the simultaneous evaluation of device and architecture optimization for FPGA. We first develop an efficient yet accurate timing and power evaluation method, called trace-based model. By collecting trace information from cycle-accurate simulation of placed and routed FPGA benchmark circuits and re-using the trace for different Vdd and Vt, we enable the device and architecture co-optimization for hundreds of combinations. Compared to the baseline FPGA which has the architecture same as the commercial FPGA used by Xilinx, and has Vdd suggested by ITRS but Vt optimized by our device optimization, architecture and device co-optimization can reduce energy-delay product by 20.5% without any chip area increase compared to the conventional FPGA architecture. Furthermore, considering power-gating of unused logic blocks and interconnect switches, our co-optimization method reduces energy-delay product by 54.7% and chip area by 8.3%. To the best of our knowledge, this is the first in-depth study on architecture and device co-optimization for FPGAs.

Process variations in nanometer technologies are becoming an important issue for cutting-edge FPGAs with a multi-million gate capacity. Considering both die-to-die and within-die variations in effective channel length, threshold voltage, and gate oxide thickness, we first develop closed-form models of leakage and timing variations at the FPGA chip level. Experiments show that our models are within 3% from Monte Carlo simulation, and the leakage and delay variations can be up to 3/spl times/ and 1.9/spl times/, respectively. We then derive analytical yield models considering both leakage and timing variations, and use such models to evaluate FPGA device and architecture under process variations. Compared to the 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%. We also show that LUT size 4 gives the highest leakage yield, LUT size 7 gives the highest timing yield, but LUT size 5 achieves the maximum combined leakage and timing yield. To the best of our knowledge, this is the first in-depth study on FPGA device and architecture co-evaluation considering process variations.

Interconnect congestion estimation plays an important role in design automation of VLSI designs. This paper presents a novel probabilistic approach to predict the wiring space in two-dimensional arrays. We propose a hierarchical estimation method to derive approximated upper bounds for the wiring space, and we use the net density distribution to predict the routing congestion. Experimental results demonstrate the promising performance of the approach.

We present a novel symbolic routability checking approach for three-dimensional interconnect layout. The model considered is a general architecture that can fit into different applications, such as ASIC, multichip modules, field-programmable gate arrays, and reconfigurable computing architectures. The method can incrementally incorporate additional constraints driven by timing, performance, and design. We used the latest satisfiability solver to validate the effectiveness of our approach. The experimental results demonstrate the encouraging performance on difficult routing benchmarks.