An exact algorithm for the statistical shortest path problem

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 σ²P 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 + Φ (σ²P) 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., σ²P ≤ 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) 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 , Vivek De, Parameter variations and impact on circuits and microarchitecture, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775920]
• 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: Ronald Prescott Loui, Optimal paths in graphs with stochastic or multidimensional weights, Communications of the ACM, v.26 n.9, p.670-676, Sept. 1983 [doi>10.1145/358172.358406]
• 5: Ishwar Murthy , Sumit Sarkar, Stochastic shortest path problems with piecewise-linear concave utility functions, Management Science, v.44 n.11 Pt.2, p.125-136, Nov. 1998 [doi>10.1287/mnsc.44.11.S125]
• 6: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 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 , Sarma Vrudhula, Variational delay metrics for interconnect timing analysis, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996675]
• 9: Semiconductor Industry Association. International Technology Roadmap for Semiconductors, 2001.
• 10: Michael Orshansky , Kurt Keutzer, A general probabilistic framework for worst case timing analysis, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA [doi>10.1145/513918.514059]
• 11: Hongliang Chang , Sachin S. Sapatnekar, Statistical Timing Analysis Considering Spatial Correlations using a Single Pert-Like Traversal, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.621, November 09-13, 2003 [doi>10.1109/ICCAD.2003.129]
• 12: Anirudh Devgan , Chandramouli Kashyap, Block-based Static Timing Analysis with Uncertainty, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.607, November 09-13, 2003 [doi>10.1109/ICCAD.2003.41]
• 13: C. Visweswariah , K. Ravindran , K. Kalafala , S. G. Walker , S. Narayan, First-order incremental block-based statistical timing analysis, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996663]
• 14: Chirayu S. Amin , Noel Menezes , Kip Killpack , Florentin Dartu , Umakanta Choudhury , Nagib Hakim , Yehea I. Ismail, Statistical static timing analysis: how simple can we get?, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, San Diego, California, USA [doi>10.1145/1065579.1065751]
• 15: Y. Gao , D. Wong, A graph based algorithm for optimal buffer insertion under accurate delay models, Proceedings of the conference on Design, automation and test in Europe, p.535-539, March 2001, Munich, Germany

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Placement and routing

Additional Classification:
  B. Hardware
  B.8 Performance and Reliability
      B.8.2 Performance Analysis and Design Aids
  B.m MISCELLANEOUS
      Subjects: Design management

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems
      G.2.3 Applications

General Terms:
Algorithms, Design, Performance