Statistical Bellman-Ford algorithm with an application to retiming

ABSTRACT

Process variations in digital circuits make sequential circuit timing validation an extremely challenging task. In this paper, a Statistical Bellman-Ford (SBF) algorithm is proposed to compute the longest path length distribution for directed graphs with cycles. Our SBF algorithm efficiently computes the statistical longest path length distribution if there exist no positive cycles or detects one if the circuit is likely to have a positive cycle. An important application of SBF is Statistical Retiming-based Timing Analysis (SRTA), where SBF is used to check for the feasibility of a given target clock period distribution for retiming. Our gate and wire delay distribution model considers several high-impact intra-die process parameters and accurately captures the spatial and reconvergent path correlations. The Monte Carlo simulation is used to validate the accuracy of our SBF algorithm. To the best of our knowledge, this is the first paper that propose the statistic version of the longest path algorithm for sequential circuits.

REFERENCES

• 1: K. Bowman, S. Duvall, and J. Meindl, "Impact of die-to-die and within-die paraemter fluctuations on ..." in Proc. ISSCC, 2001.
• 2: 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]
• 3: Aseem Agarwal , David Blaauw , Vladimir Zolotov , Sarma Vrudhula, Statistical Timing Analysis Using Bounds, Proceedings of the conference on Design, Automation and Test in Europe, p.10062, March 03-07, 2003
• 4: 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]
• 5: Giovanni De Micheli, Synthesis and Optimization of Digital Circuits, McGraw-Hill Higher Education, 1994
• 6: T. G. Szymanski, Computing optimal clock schedules, Proceedings of the 29th ACM/IEEE conference on Design automation, p.399-404, June 08-12, 1992, Anaheim, California, United States
• 7: Y. S. F-R. Boyer, El M. Aboulhamd, "An efficient verification method for a class of multi-phase sequential circuits," in ICECS, 2000.
• 8: J. Cong and S. K. Lim, "Retiming-based timing analysis with an application to ..." IEEE TCAD, vol. 23, no. 12, 2004.
• 9: R. Durrett, Probability: Theory and Examples. Duxbury Press, 1995.
• 10: P. Billingsley, Probability and Measure. John Wiley & Sons, 1995.
• 11: Y. Z. Liao , C. K. Wong, An algorithm to compact a VLSI symbolic layout with mixed constraints, Proceedings of the 20th conference on Design automation, p.107-112, June 27-29, 1983, Miami Beach, Florida, United States
• 12: Ruiming Chen , Hai Zhou, Clock schedule verification under process variations, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.619-625, November 07-11, 2004 [doi>10.1109/ICCAD.2004.1382650]
• 13: J. Rabaey, A. Chandrakasan, and B. Nikolic, Digital Integrated Circuits. Prentice Hall Electronics, 2003.
• 14: SIA, "National Techonology Roadmap for Semiconductors," 2003.
• 15: C. Clark, "The greatest of a finite set of random variables," in Operations Research, 1961.
• 16: C. Ababei , K. Bazargan, Statistical Timing Driven Partitioning for VLSI Circuits, Proceedings of the conference on Design, automation and test in Europe, p.1109, March 04-08, 2002

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.1 Design Styles
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Simulation

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms
      G.2.3 Applications

General Terms:
Algorithms, Design, Performance