Title :
Statistical static timing analysis using Markov chain Monte Carlo
Author :
Kanoria, Yashodhan ; Mitra, Subhasish ; Montanari, Andrea
Author_Institution :
Dept. of Electr. Eng., Stanford Univ., Stanford, CA, USA
Abstract :
We present a new technique for statistical static timing analysis (SSTA) based on Markov chain Monte Carlo (MCMC), that allows fast and accurate estimation of the right-hand tail of the delay distribution. A ??naive?? MCMC approach is inadequate for SSTA. Several modifications and enhancements, presented in this paper, enable application of MCMC to SSTA. Moreover, such an approach overcomes inherent limitations of techniques such as importance sampling and Quasi-Monte Carlo. Our results on open source designs, with an independent delay variation model, demonstrate that our technique can obtain more than an order of magnitude improvement in computation time over simple Monte Carlo, given an estimation accuracy target at a point in the tail. Our approach works by providing a large number of samples in the region of interest. Open problems include extension of algorithm applicability to a broader class of synthesis conditions, and handling of correlated delay variations. In a broader context, this work aims to show that MCMC and associated techniques can be useful in rare event analyses related to circuits, particularly for high-dimensional problems.
Keywords :
Markov processes; Monte Carlo methods; logic gates; public domain software; statistical analysis; Markov chain Monte Carlo; SSTA; delay distribution; open source designs; quasi-Monte Carlo; statistical static timing analysis; Circuits; Computer science; Delay estimation; Monte Carlo methods; Performance analysis; Probability distribution; Statistical analysis; Statistical distributions; Testing; Timing;
Conference_Titel :
Design, Automation & Test in Europe Conference & Exhibition (DATE), 2010
Conference_Location :
Dresden
Print_ISBN :
978-1-4244-7054-9
DOI :
10.1109/DATE.2010.5456938