| Friday January 27, 2006 |
| Title | Convergence-Provable Statistical Timing Analysis with Level-Sensitive Latches and Feedback Loops |
| Author | Lizheng Zhang, Jengliang Tsai, Weijen Chen, Yuhen Hu, *Charlie Chungping Chen (University of Wisconsin-Madison, United States) |
| Page | pp. 941 - 946 |
| Keyword | statistical timing analysis, level sensitive latch, feedback loop, convergence |
| Abstract | Statistical timing analysis has been widely applied to predict the timing yield of VLSI circuits when process variations become significant. Existing statistical latch timing methods are either having exponential complexity or unable to treat the random variable's self-dependence caused by the coexistence of level-sensitive latches and feedback loops. In this paper, an efficient iterative statistical timing algorithm with provable convergence is proposed for latch-based circuits with feedback loops. Based on a new notion of iteration mean, we prove that the algorithm converges unconditionally. Moreover, we show that the converged value of iteration mean can be used to predict the circuit yield during design time. Tested by ISCAS'89 benchmark circuits, the proposed algorithm shows an error of 1.1% and speedup of 303x on average when compared with the Monte Carlo simulation. |
| Title | Parameterized Block-Based Non-Gaussian Statistical Gate Timing Analysis |
| Author | Soroush Abbaspour, Hanif Fatemi, *Massoud Pedram (University of Southern California, United States) |
| Page | pp. 947 - 952 |
| Keyword | statistical timing analysis, process variation |
| Abstract | As technology scales down, timing verification of digital integrated circuits becomes an extremely difficult task due to the gate and wire variability. Therefore, statistical timing analysis (denoted by ¦åTA) is becoming unavoidable .In this paper, we propose a new framework to handle the statistical gate timing analysis for non-Gaussian sources of variation in block-based ¦åTA. First, we present an approach to approximate variational RC-¦â load by using a canonical first-order model. Next, an accurate variation-aware gate timing analysis based on statistical input transition, statistical gate timing library, and statistical RC-pi load is presented. To perform the aforementioned objective, we present a statistical effective capacitance calculation which is the key contribution of this paper. Experimental results show an average error of 6% for gate delay and output transition time with respect to the HSPICE Monte Carlo simulation while the runtime is about 95 times faster. |
| Title | Statistical Leakage Minimization through Joint Selection of Gate Sizes, Gate Lengths and Threshold Voltage |
| Author | *Sarvesh Bhardwaj, Yu Cao, Sarma Vrudhula (Arizona State University, United States) |
| Page | pp. 953 - 958 |
| Keyword | Statistical, Leakage, Convex, Optimization |
| Abstract | This paper proposes a novel methodology for statistical Leakage minimization of digital circuits. A function of mean and variance of the leakage is minimized with constraint on alpha-percentile of the delay using statistical 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. Also, gate length biasing is shown to cause significant reduction in the leakage variability due to its inverse relation with Vth. |
| Title | Statistical Bellman-Ford Algorithm With An Application to Retiming |
| Author | *Mongkol Ekpanyapong (Georgia Institute of Technology, United States), Thaisiri Watewai (University of California, Berkeley, United States), Sung Kyu Lim (Georgia Institute of Technology, United States) |
| Page | pp. 959 - 964 |
| Keyword | retiming, statistical timing analysis |
| Abstract | Process variations in digital circuits make sequential circuit timing validation an extremely challenging task. In this paper, a Statistical Bellman-Ford (SBF) algorithm is proposed to compute the longest path length distribution for directed graphs with cycles. Our SBF algorithm efficiently computes the statistical longest path length distribution if there exist no positive cycles or detects one if the circuit is likely to have a positive cycle. An important application of SBF is Statistical Retiming-based Timing Analysis (SRTA), where SBF is used to check for the feasibility of a given target clock period distribution for retiming. Our gate and wire delay distribution model considers several high-impact intra-die process parameters and accurately captures the spatial and reconvergent path correlations. The Monte Carlo simulation is used to validate the accuracy of our SRTA algorithm. |
| Title | An Exact Algorithm for the Statistical Shortest Path Problem |
| Author | Liang Deng, *Martin D. F. Wong (University of Illinois at Urbana-Champaign, United States) |
| Page | pp. 965 - 970 |
| Keyword | Algorithm, Process Variations, Statistical Shortest Path |
| Abstract | Graph algorithms are widely used in VLSI CAD. Traditional graph algorithms can handle graphs with deterministic edge weights. As VLSI technology continues to scale into nanometer designs, we need to use probability distributions for edge weights in order to model uncertainty due to parameter variations. In this paper, we consider the statistical shortest path (SSP) problem. Given a graph $G$, the edge weights of $G$ are random variables. For each path $P$ in $G$, let $L_{P}$ be its length, which is the sum of all edge weights on $P$. Clearly $L_{P}$ is a random variable and we let $\mu_{P}$ and $\sigma_{P}^2$ be its mean and variance, respectively. In the SSP problem, our goal is to find a path $P$ connecting two given vertices to minimize the cost function $\mu_{P}+\Phi(\sigma_{P}^2)$ where $\Phi$ is an arbitrary function. (For example, if $\Phi(x) = 3\sqrt{x}$, the cost function is $\mu_{P} + 3\sigma_{P}$.) To minimize uncertainty in the final result, it is meaningful to look for paths with bounded variance, i.e., $\sigma_{P}^2 \le B$ for a given fixed bound $B$. In this paper, we present an exact algorithm to solve the SSP problem in $O(B(V+E))$ time where $V$ and $E$ are the numbers of vertices and edges, respectively, in $G$. Our algorithm is superior to previous algorithms for SSP problem because we can handle: 1) \emph{general graphs} (unlike previous works applicable only to directed acyclic graphs), 2) \emph{arbitrary edge-weight distributions} (unlike previous algorithms designed only for specific distributions such as Gaussian), and 3) \emph{general cost function} (none of the previous algorithms can even handle the cost function $\mu_{P} + 3\sigma_{P}$. Finally, we discuss applications of the SSP problem to maze routing, buffer insertions, and timing analysis under parameter variations. |