The statistical longest path problem and its application to delay analysis of logical circuits

ABSTRACT

This paper presents an algorithm for estimating, in the sense below, the length of a longest path of a given directed acyclic graph (DAG) whose edge lengths are given as random variables with normal distributions. Let F(x) be the distribution function of the length of a longest path of a given DAG. The algorithm computes a normal distribution function &Ftilde;(x) such that ˜F(x) 〈 F(x) if F(x) 〉 a, given a constant a (0.5 〈 a 〈 1.0). We conduct two experiments to demonstrate the accuracy of &Ftilde;(x).

REFERENCES

• 1: M.Berkelaar, "Statistical delay calculation, a linear time method", Proc. the International Workshop on Timing Analysis TAU '97, 15--24, 1997.
• 2: M.Hashimoto, H.Onodera, "A performance optimization method by gate sizing using statistical static timing analysis", IEICE Trans. Fundamentals, vol.E83-A, No.12, 2558--2568, December 2000.
• 3: E. L. Lawler, "Combinatorial Optimization: Networks and Matroids," Holt, Rinehart and Winston, U.S.A., 1976.
• 4: Shuji Tsukiyama, Masakazu Tanaka, Masahiro Fukui, "Estimation method for probabilistic delay of critical path on combinational logical circuits" IEICE Proc. 13th Workshop on Circuits and Systems, 131--135, 2000 (in Japanese).
• 5: C.E.Clark, "The greatest of a finite set of random variables", Operations Research Vol.9, No.2 , 145--152, 1961.
• 6: Hiroshi Imahayashi, "The distribution of the longest path on graphs with probabilistic weights", Master's thesis, Kyushu University, Fukuoka, Japan, 2001 (in Japanese).

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Distribution functions

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

General Terms:
Algorithms