Approximate timing analysis of combinational circuits under the XBD0 model

ABSTRACT

This paper is concerned with approximate delay computation algorithms for combinational circuits. As a result of intensive research in the early 90's efficient tools exist which can analyze circuits of thousands of gates in a few minutes or even in seconds for many cases. However, the computation time of these tools is not so predictable since the internal engine of the analysis is either a SAT solver or a modified ATPG algorithm, both of which are just heuristic algorithms for an NP-complete problem. Although they are highly tuned for CAD applications, there exists a class of problem instances which exhibits the worst-case exponential CPU time behavior. In the context of timing analysis, circuits with a high amount of reconvergence, e.g. C6288 of the ISCAS benchmark suite, are known to be difficult to analyze under sophisticated delay models even with state-of-the-art techniques. For example [McGeer93] could not complete the analysis of C6288 under the mapped delay model. To make timing analysis of such corner case circuits feasible we propose an approximate computation scheme to the timing analysis problem as an extension to the exact analysis method proposed in [McGeer93]. Sensitization conditions are conservatively approximated in a selective fashion so that the size of SAT problems solved during analysis is controlled. Experimental results show that the approximation technique is effective in reducing the total analysis time without losing accuracy for the case where the exact approach takes much time or cannot complete.

REFERENCES

• 1: H.-C. Chen and D. H.-C. Du. Path sensitization in critical path problem. IEEE Transactions on Computer-AidedDesign, 12(2):196-207, February 1993.
• 2: S. Devadas, K. Keutzer, and S. Malik. Computation of floating mode delay in combinational circuits: Theory and algorithms. IEEE Transactions on Computer-AidedDesign, 12(12):1913- 1923, December 1993.
• 3: S. Devadas, K. Keutzer, S. Malik, and A. Wang. Computation of floating mode delay in combinational circuits: Practice and implementation. IEEE Transactions on Computer-Aided Design, 12(12):1924-1936, December 1993.
• 4: S.-T. Huang, T.-M. Parng, and J.-M. Shyu. A new approach to solving false path problem in timing analysis. In Proceedings of lEEE International Conference on Computer-Aided Design, pages 216-219, November 1991.
• 5: Shiang-Tang Huang , Tai Ming Parng , Jyuo Min Shyu, A polynomial-time heuristic approach to approximate a solution to the false path problem, Proceedings of the 30th international conference on Design automation, p.118-122, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164622]
• 6: S.-T. Huang, T.-M. Parng, and J.-M. Shyu. Timed boolean calculus and its applications in timing analysis. IEEE Transactions on Computer-Aided Design, 13(3):318-337, March 1994.
• 7: Patrick C. McGeer , Robert K. Brayton, Integrating Functional and Temporal Domains in Logic Design: The False Path Problem and Its Implications, Kluwer Academic Publishers, Norwell, MA, 1991
• 8: E C. McGeer, A. Saldanha, R. K. Brayton, and A. Sangiovanni-Vincentelli. Delay models and exact timing analysis. In T. Sasao, editor, Logic Synthesis and Optimization, pages 167-189. Kluwer Academic Publishers, 1993.
• 9: H. Yalcin. Private communication, March 1997.
• 10: Hakan Yalcin , John P. Hayes, Hierarchical timing analysis using conditional delays, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.371-377, November 05-09, 1995, San Jose, California, United States
• 11: Hakan Yalcin , John P. Hayes , Karem A. Sakallah, An approximate timing analysis method for datapath circuits, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.114-118, November 10-14, 1996, San Jose, California, United States

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.1 Design Styles
          Subjects: Combinational logic

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN

  C. Computer Systems Organization

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

  J. Computer Applications

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance, Theory

Keywords:
False path, timing analysis, delay computation