DocumentCode :
2254115
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
fYear :
2010
fDate :
8-12 March 2010
Firstpage :
813
Lastpage :
818
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;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Design, Automation & Test in Europe Conference & Exhibition (DATE), 2010
Conference_Location :
Dresden
ISSN :
1530-1591
Print_ISBN :
978-1-4244-7054-9
Type :
conf
DOI :
10.1109/DATE.2010.5456938
Filename :
5456938
Link To Document :
بازگشت