skip to main content
10.1145/1118299.1118515acmconferencesArticle/Chapter ViewAbstractPublication PagesaspdacConference Proceedingsconference-collections
Article

An exact algorithm for the statistical shortest path problem

Published: 24 January 2006 Publication History

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 LP be its length, which is the sum of all edge weights on P. Clearly LP is a random variable and we let μP and σ2P 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 μP + Φ (σ2P) where Φ is an arbitrary function. (For example, if Φ (x) = 3√x, the cost function is μ + 3σP.) To minimize uncertainty in the final result, it is meaningful to look for paths with bounded variance, i.e., σ2PB 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) general graphs (unlike previous works applicable only to directed acyclic graphs), 2) arbitrary edge-weight distributions (unlike previous algorithms designed only for specific distributions such as Gaussian), and 3) general cost function (none of the previous algorithms can even handle the cost function μP + 3σP Finally, we discuss applications of the SSP problem to maze routing, buffer insertions, and timing analysis under parameter variations.

References

[1]
Shekhar Borkar, Tanay Karnik, Siva Narendra, Jim Tschanz, Ali Keshavarzi, and Vivek De. Parameter variations and impact on circuits and microarchitecture. In Proc. of the 40th Design Automation Conference, pages 338--342. ACM Press, 2003.
[2]
H. Frank. Shortest path in probabilistic graphs. Oper. Res., 17:583--599, 1969.
[3]
C. Elliott Sigal, A. Alan B. Pritsker, and James J. Solberg. The stochastic shortest route problem. Opers. Res., 28:1122--1128, 1980.
[4]
R. P. Loui. Optimal path in graphs with stochastic or multidimensional weights. Comm. of ACM, 26:670--676, 1983.
[5]
Ishwar Murthy. Stochastic shortest path problems with piecewise-linear concave utility functions. Management Science, 44:125--136, 11 1998.
[6]
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms. The MIT Press, 2001.
[7]
Duane Boning and Sani Nassif. Design of High-Performance Microprocessor Circuits. 2002.
[8]
Kanak Agarwal, Dennis Sylvester, David Blaauw, Frank Liu, Sani Nassif, and Sarma Vrudhula. Variational delay metrics for interconnect timing analysis. In DAC 2004, pages 381--384. ACM Press, 2004.
[9]
Semiconductor Industry Association. International Technology Roadmap for Semiconductors, 2001.
[10]
Michael Orshansky and Kurt Keutzer. A general probabilistic framework for worst case timing analysis. In Proc. of the 39th Design Automation Conference, pages 556--561. ACM Press, 2002.
[11]
Hongliang Chang and S. S. Sapatnekar. Statistical timing analysis considering spatial correlations using a single pert-like traversal. In Proc. International Conference on Computer Aided Design, pages 621--625, 2003.
[12]
A. Davgan and C. Kashyap. Block-based static timing analysis with uncertainty. In Proc. of international conference on Computer Aided Design 2003, pages 607--614, 2003.
[13]
C. Visweswariah, K. Ravindran, K. Kalafala, S. G. Walker, and S. Narayan. First-order incremental block-based statistical timing analysis. In Proc. of the 41st Design Automation Conference, pages 331--336, New York, NY, USA, 2004. ACM Press.
[14]
Chirayu S. Amin, Noel Menezes, Kip Killpack, Florentin Dartu, Yehea Ismail, Umakanta Choudhury, and Nagib Hakim. Statistical static timing analysis: How simple can we get? In Proc. of the 42nd Design Automation Conference, pages 652--657, New York, NY, USA, 2005. ACM Press.
[15]
Y. Gao and D. Wong. A graph based algorithm for optimal buffer insertion under accurate delay models. In Proc. of the conference on Design, automation and test in Europe, pages 535--539. IEEE Press, 2001.

Cited By

View all
  • (2016)Efficient Multistate Route ComputationIEEE Transactions on Network Science and Engineering10.1109/TNSE.2016.25867503:3(171-182)Online publication date: 1-Jul-2016
  • (2015)Ranking paths in statistical energy analysis models with non-deterministic loss factorsMechanical Systems and Signal Processing10.1016/j.ymssp.2014.07.02352-53(741-753)Online publication date: Feb-2015
  • (2012)Algorithmic study on the routing reliability problemThirteenth International Symposium on Quality Electronic Design (ISQED)10.1109/ISQED.2012.6187537(483-488)Online publication date: Mar-2012
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
ASP-DAC '06: Proceedings of the 2006 Asia and South Pacific Design Automation Conference
January 2006
998 pages
ISBN:0780394518

Sponsors

  • IEEE Circuits and Systems Society
  • SIGDA: ACM Special Interest Group on Design Automation
  • IEICE ESS: Institute of Electronics, Information and Communication Engineers, Engineering Sciences Society
  • IPSJ SIG-SLDM: Information Processing Society of Japan, SIG System LSI Design Methodology

Publisher

IEEE Press

Publication History

Published: 24 January 2006

Permissions

Request permissions for this article.

Check for updates

Qualifiers

  • Article

Acceptance Rates

Overall Acceptance Rate 466 of 1,454 submissions, 32%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)8
  • Downloads (Last 6 weeks)0
Reflects downloads up to 09 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2016)Efficient Multistate Route ComputationIEEE Transactions on Network Science and Engineering10.1109/TNSE.2016.25867503:3(171-182)Online publication date: 1-Jul-2016
  • (2015)Ranking paths in statistical energy analysis models with non-deterministic loss factorsMechanical Systems and Signal Processing10.1016/j.ymssp.2014.07.02352-53(741-753)Online publication date: Feb-2015
  • (2012)Algorithmic study on the routing reliability problemThirteenth International Symposium on Quality Electronic Design (ISQED)10.1109/ISQED.2012.6187537(483-488)Online publication date: Mar-2012
  • (2008)Statistical Timing AnalysisIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2007.90704727:4(589-607)Online publication date: 1-Apr-2008
  • (2008)Preserving Caller Anonymity in Voice-over-IP NetworksProceedings of the 2008 IEEE Symposium on Security and Privacy10.1109/SP.2008.10(50-63)Online publication date: 18-May-2008
  • (2007)A novel criticality computation method in statistical timing analysisProceedings of the conference on Design, automation and test in Europe10.5555/1266366.1266720(1611-1616)Online publication date: 16-Apr-2007
  • (2007)A Novel Criticality Computation Method in Statistical Timing Analysis2007 Design, Automation & Test in Europe Conference & Exhibition10.1109/DATE.2007.364532(1-6)Online publication date: Apr-2007

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media