Accurate delay analysis with distributed RC delay can be computationally expensive, and can contribute the majority of the total runtime for gate sizers. Recent works have shown that Lagrangian relaxation (LR)-based gate sizers have produced designs with the lowest power on average. But they are also very slow due to a large number of expensive timing updates spread across several tens of iterations. In this paper, we develop an LR-based discrete gate sizer for fast timing and power reduction. Our gate sizer is multithreaded and is equipped with parallelization enabling techniques, namely mutual exclusion edge (MEE) assignment and directed acyclic graph (DAG)-based netlist traversal (DNT). MEEs are dummy edges assigned to improve load sharing among different threads. DNT facilitates simultaneous resizing of gates belonging to different topological levels. Our Lagrange multiplier update strategy enables rapid convergence of our timing and power recovery algorithms. To reduce the runtime of timing updates, we propose a simple and fast-to-compute effective capacitance model. We further propose mechanisms to calibrate timing models to improve their accuracy. By calibrating the internal timing models only twice, our proposed gate sizing flow facilitates extremely fast design optimization. We benchmark our gate sizer using the ISPD 2012 and 2013 gate sizing contest benchmark suites. Compared to the state-of-the-art gate sizer, our proposed gate sizer is on average 15× faster and the optimized designs have 2.5% higher leakage power. Since we tradeoff timing accuracy for larger runtime speedup, our optimized designs have small timing violations.

We propose techniques to achieve very fast multi-threaded gate-sizing and threshold-voltage swap for leakage power minimization. We focus on multi-threading Lagrangian Relaxation (LR) based gate sizing which has shown both better power savings and better runtime compared to other gate sizing approaches. Our techniques, mutual exclusion edge assignment and directed graph-based netlist traversal, maximize thread execution efficiency to take full advantage of the inherent parallelism when solving the LR subproblem, without compromising the leakage power savings. With 8 threads, our multi-threading techniques achieve on average 5.23x speedup versus our single-threaded (sequential) implementation. This compares well to the maximum achievable speedup of 5.93x by Amdahl's law due to 5% of the execution not being parallelizable. To highlight the problems with load imbalance and poor scheduling, we also propose a simpler approach based on clustering and topological levelby-level netlist traversal, which can achieve only 3.55x speedup. We also propose three simple yet effective enhancements - fast optimal local resizing, early exit policy, and fast greedy timing recovery - to speed up single-threaded LR-based gate-sizing without degrading the leakage power. We test our gate sizer using the ISPD 2012 gate sizing contest benchmarks and guidelines. Compared to other researchers' state-of-the-art LR-based gate sizer, our approach is 1.03x (with 1-thread) and 5.40x (with 8-threads) faster and only 2.2% worse in leakage power.

Timing closure, which is to meet the design's timing constraints, is a key problem in the physical design flow. During the timing optimization process, buffers can be used to speedup the circuit or serve as delay elements. In this paper, we study the hold-violation removal problem for today's industrial designs. Discrete buffers, accurate timing models/analysis, and complex timing constraints make the problem difficult and time-consuming to solve. In this paper, we first present a linear programming-based methodology to model the setup and hold-time constraints. Then based on the solution to the linear programming, buffers are inserted as delay elements to solve hold violations. In the experiment, our approach is tested on industrial designs, then runs with the industrial optimization flow, and better results in terms of hold violations and runtime are reported.

Energy reduction of functional units (FUs) is a very important concern for high-end superscalar processors, not only because FUs consume a significant portion of processor energy, but also because they are one of the most important hotspots in the processor. In addition, the high sensitivity of leakage on temperature and process variation result in very high variation in the FU power consumption in different processor dies. Such high process variation reduces the parametric yield of processors. Consequently, reducing the FU power consumption and its variation is an important problem. However, existing FU power reduction techniques assumes all the FUs are similar, and do not consider the sensitivity of leakage on temperature. Consequently, they are not very effective in reducing the variation of FU power consumption. The advent of extremely small, yet accurate leakage sensors allow us to develop leakage-aware microarchitectural techniques to reduce both the power consumption and its variation among processor dies. Our leakage-aware operation-to-FU binding mechanism (LAOFBM) and leakage-aware power gating (LA-PG) mechanisms reduce the mean and standard deviation of the total arithmetic logic unit (ALU) power consumption of the ALPHA 21364 by 34% and 59%, respectively. At the processor level, this translates to a 13% reduction in the total processor energy consumption, with a 24°C reduction in the maximum ALU temperature.

Negative-bias-temperature instability (NBTI) has become the primary limiting factor of circuit life time. In this paper, we develop a hierarchical framework for analyzing the impact of NBTI on the performance of logic circuits under various operation conditions, such as the supply voltage, temperature, and node switching activity. Given a circuit topology and input switching activity, we propose an efficient method to predict the degradation of circuit speed over a long period of time. The effectiveness of our method is comprehensively demonstrated with the International Symposium on Circuits and Systems (ISCAS) benchmarks and a 65-nm industrial design. Furthermore, we extract the following key design insights for reliable circuit design under NBTI effect, including: 1) During dynamic operation, NBTI-induced degradation is relatively insensitive to supply voltage, but strongly dependent on temperature; 2) There is an optimum supply voltage that leads to the minimum of circuit performance degradation; circuit degradation rate actually goes up if supply voltage is lower than the optimum value; 3) Circuit performance degradation due to NBTI is highly sensitive to input vectors. The difference in delay degradation is up to 5× for various static and dynamic operations. Finally, we examine the interaction between NBTI effect, and process and design uncertainty in realistic conditions.

This paper presents a novel gate-sizing methodology to minimize the leakage power in the presence of process variations. The method is based on modeling the statistics of leakage and delay as posynomials functions to formulate a geometric-programming problem. The existing statistical leakage model is extended to include the variations in gate sizes, as well as systematic variations. Using a simplified delay model, we propose an efficient method to evaluate the alpha-percentile of path delays without enumerating the paths in a circuit. The complexity of evaluating the objective function of the optimization problem is O(|N|2) and that of evaluating the delay constraints is O(|N| + |E|) for a circuit with |N| gates and |E| wires. The optimization problem is then solved using a convex optimization algorithm that gives an exact solution. The statistical optimization methodology is shown to provide as much as 15% reduction in the mean leakage power as compared to traditional worst case gate sizing with the same delay constraints.

In this paper, we present a unified approach for the statistical timing and leakage analysis of circuits in the presence of intradie variations. The intradie variations in device parameters are modeled as a spatial stochastic process with a given covariance function. The covariance function is used to construct a Karhunen-Loeve expansion of the spatial process. This leads to representing the various parameters of all components on the chip in terms of a common set of abstract random variables. The leakage and propagation delay of each gate are represented as quadratic polynomials (QPs), which are elements of a vector space whose bases are multivariate quadratic orthogonal polynomials of the device parameters. In the case of signal arrival times, we describe an efficient method to propagate the QPs through the circuit to obtain a QP representation of the signal arrival times at the primary outputs. The analysis is extended to include sequential components so that flip-flop parameters and clock arrival times can be treated as random variables. This allows efficient estimation of the timing yield of the circuit. We show how a similar representation of QP can be used to model leakage of gates and develop an efficient method to compute a QP representation of the total chip leakage. The proposed techniques and quadratic models were exercised on ISCAS89 benchmark circuits and compared with Monte Carlo (MC) simulations. The results show that the techniques are very accurate and several orders of magnitude faster than MC simulation.

Negative-bias-temperature-instability (NBTI) has become the primary limiting factor of circuit lifetime. In this work, we develop a general framework for analyzing the impact of NBTI on the performance of a circuit, based on various circuit parameters such as the supply voltage, temperature, and node switching activity of the signals etc. We propose an efficient method to predict the degradation of circuit performance based on circuit topology and the switching activity of the signals over long periods of time. We demonstrate our results on ISCAS benchmarks and a 65nm industrial design. The framework is used to provide key design insights for designing reliable circuits. The key design insights that we obtain are: (1) degradation due to NBTI is most sensitive on the input patterns and the duty cycle; the difference in the delay degradation can be up to 5X for various static and dynamic conditions, (2) during dynamic operation, NBTI-induced degradation is relatively insensitive to supply voltage, but strongly dependent on temperature; (3) NBTI has marginal impact on the clock signal.

This paper proposes a novel methodology for statistical leakage minimization of digital circuits. A function of mean and variance of the circuit leakage is minimized with constraint on a-percentile of the delay using physical delay models. Since the leakage is a strong function of the threshold voltage and gate length, considering them as design variables can provide significant amount of power savings. The leakage minimization problem is formulated as a multivariable convex optimization problem. We demonstrate that statistical optimization can lead to more than 37% savings in nominal leakage compared to worst-case techniques that perform only gate sizing.

This paper proposes the use of Karhunen-Loève Expansion (KLE) for accurate and efficient modeling of intra-die correlations in the semiconductor manufacturing process. We demonstrate that the KLE provides a significantly more accurate representation of the underlying stochastic process compared to the traditional approach of dividing the layout into grids and applying Principal Component Analysis (PCA). By comparing the results of leakage analysis using both KLE and the existing approaches, we show that using KLE can provide up to 4-5x reduction in the variability space (number of random variables) while maintaining the same accuracy. We also propose an efficient leakage minimization algorithm that maximizes the leakage yield while satisfying probabilistic constraints on the delay.

For statistical timing and power analysis that are very importantproblems in the sub-100nm technologies, stochastic analysis of power grids that characterizes the voltage fluctuations due to process variations is inevitable. In this paper, we propose an efficient algorithm for the variational analysis of large power grids in the presence of a significant number of Gaussian intra-die process variables that are correlated. We consider variations in the power grid's electrical parameters as spatial stochastic processes and express them as linear expansions in an orthonormal series of random variables using the Karhunen-Loéve(KLE) method. The voltage response is then represented as an orthonormal polynomial series and the coefficients are obtained optimally using the Galerkin method. We propose a novel method to separate the stochastic analysis for the random variables that effect only the inputs (e.g, drain currents) and for those that effect the system parameters as well (e.g., conductance, capacitance). We show that this parallelism can result in significant speed-ups in addition to the speed-ups inherent to Galerkin-based methods. Our analysis has been applied to several industrial power grids and the results show speed-ups of up to two orders of magnitude over Monte Carlo simulations for comparable accuracy.

In this paper we propose a framework for Statistical Static Timing Analysis (SSTA) considering intra-die process variations. Given a cell library, we propose an accurate method to characterize the gate and interconnect delay as well as slew as a function of underlying parameter variations. Using these accurate delay models, we propose a method to perform SSTA based on a quadratic delay and slew model. The method is based on efficient dimensionality reduction technique used for accurate computation of the max of two delay expansions. Our results indicate less than 4% error in the variance of the delay models compared to SPICE Monte Carlo and less than 1% error in the variance of the circuit delay compared to Monte Carlo simulations.

It has been recently pointed out that cyclic circuits are not necessarily sequential, and cyclic topologies that are combinational generally have lower literal counts than their acyclic counterparts. However, the synthesis of cyclic combinational circuits is potentially expensive due to the need to explore a wide range of cyclic topologies and check each of them for combinationality. We first obtain the acyclic implementation of the given set of boolean functions. Then using a branch-and-bound heuristic, we generate cyclic circuits that are to be checked for combinationality. Unlike earlier complex methods for combinationality check, our approach is to check whether this cyclic circuit is functionally equivalent to the acyclic circuit obtained earlier. While synthesizing cyclic circuits with the proposed method, we observed up to 45%. improvements in the literal count (for Espresso and LGsynth93 benchmarks) over the acyclic circuit synthesized by the Berkeley sis package.

This paper presents a novel gate sizing methodology to mini-mize the leakage power in the presence of process variations. The leakage and delay are modeled as posynomials functions to formulate a geometric programming problem. The exist-ing statistical leakage model of [18] is extended to include the variations in gate sizes as well as systematic variations. We propose techniques to efficiently evaluate constraints on the α-percentile of the path delays without enumerating the paths in the circuit. The complexity of evaluating the ob-jective function is O(|N |2) and that of evaluating the delay constraints is O(|N | + |E|) for a circuit with |N | gates and |E | wires. The optimization problem is then solved using a convex optimization algorithm that gives an exact solution.

Traditional single-attribute optimization problems force a designer to choose either power or delay as the objective function and minimize it with constraints on other attributes. However this approach does not provide the designer with enough freedom to incorporate tradeoffs between various attributes such as leakage and delay. In this paper we present a utility theoretic approach for the joint optimization of leakage and delay. This provides a general framework for quantifying a designer's preferences for tradeoffs between leakage and delay. We show that energy-delay product (EDP) is an element of a larger class of such utility functions. The resulting multi-attribute optimization problem is modeled as a convex gate sizing problem that is solved using Geometric Programming. The resulting solution is a design point that is optimal with respect to the designer's preferences.

This paper presents a new method based on Bayesian networks (BNs) for computing the exact probability distribution of the delay of a circuit. The method is based on BNs, which allows an efficient means to factor the joint probability distributions over variables in a circuit graph. The space complexity of the method presented here is O(m/sup |C|/), where m is the number of distinct values taken by each delay variable and |C| is the number of variables in the largest clique. The maximum clique size present in a BN is shown to be much smaller than the circuit size. For large circuits, where it is not practically feasible to compute the exact distribution, methods to reduce the problem size and get a lower bound on the exact distribution are presented. Comparison of the results with Monte Carlo simulations shows that we can reduce the size of the circuit by as much as 89% while maintaining the maximum difference between the predicted and simulated 3/spl sigma/ values to be less than 3%.

Delay due to capacitive coupling of interconnects has become an important reliability issue in the design of nanometer circuits. In this paper we present a probabilistic approach towards analyzing the impact of capacitive coupling noise on signal delay. The variation in the delay is due to the variation in the relative arrival times of the aggressors and the victim. We derive expressions for the moments of the victim voltage in the presence of noise. From these we compute estimates of the earliest and latest possible arrival times of the victim. We compare the analytical results with Monte Carlo simulations using SPICE. Even though the analytical calculations are 200 times faster than the Monte Carlo simulations, the differences in the estimates of the mean and standard deviation of the arrival time is no more than 2.8%. In addition, the width of the timing intervals using the proposed approach is reduced by as much as 48% with a confidence level of 0.984. That is 98.4% of the Monte Carlo simulations result in an arrival time that falls within the derived interval which is 48% shorter.