Approximate algorithms for time separation of events

ABSTRACT

We describe a polynomial-time approximate algorithm for computing minimum and maximum time separations between all pairs of events in systems specified by acyclic timing constraint graphs. Even for acyclic graphs, the problem is NP-complete. We propose finding an approximate solution by first approximating the non-convex feasible space with a suitable convex ``envelope'', and then solving the problem efficiently in the approximate convex space. Unlike previous works, our algorithm can handle both min and max-type timing constraints in the same system, and has a computational complexity that is polynomial in the number of events. Although the computed separations are conservative in the worst-case, experiments indicate that our results are highly accurate in practice.

REFERENCES

• 1: T. Amon , G. Borriello, An approach to symbolic timing verification, Proceedings of the 29th ACM/IEEE conference on Design automation, p.410-413, June 08-12, 1992, Anaheim, California, United States
• 2: Timothy M. Burks , Karem A. Sakallah, Min-max linear programming and the timing analysis of digital circuits, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.152-155, November 07-11, 1993, Santa Clara, California, United States
• 3: Steven Morgan Burns, Performance analysis and optimization of asynchronous circuits, California Institute of Technology, Pasadena, CA, 1992
• 4: H. Hulgaard and S. M. Burns. Bounded delay timing analysis of a class of CSP programs with choice. In Proceedings of the 1 st ASYNC, Nov. 1994.
• 5: H. Hulgaard, S. M. Burns, T. Amon, and G. Borriello. An algorithm for exact bounds on time separation of events in concurrent systems. Technical report, Department of Computer Science and Engineering, University of Washington, Feb. 1994. Tech. Report No. UW-CSE-94-02-02.
• 6: L. Lavagno , N. Shenoy , A. Sangiovanni-Vincentelli, Linear programming for hazard elimination in asynchronous circuits, Journal of VLSI Signal Processing Systems, v.7 n.1-2, p.137-160, Feb. 1994 [doi>10.1007/BF02108194]
• 7: Kenneth L. McMillan , David L. Dill, Algorithms for Interface Timing Verification, Proceedings of the 1991 IEEE International Conference on Computer Design on VLSI in Computer & Processors, p.48-51, October 11-14, 1992
• 8: C. J. Myers and T. H.-Y. Meng. Synthesis of timed asynchronous circuits. IEEE Transactions on VLSI Systems, 1(2):106-119, June 1993.
• 9: K.A. Sakallah, T. N. Mudge, and O. A. Olukotun. checkTc and minTc: Timing verification and optimal clocking of digital circuits. In Proceedings of the ICCAD, Nov. 1990.
• 10: E Vanbekbergen, G. Goossens, and H. D. Man. Specification and analysis of timing constraints in signal transition graphs. In Proceedings of the Eu~vpean DAC, Mar. 1992.
• 11: Kenneth Y. Yun , Ayoob E. Dooply , Julio Arceo , Peter A. Beerel , Vida Vakilotojar, The Design and Verification of A High-Performance Low-Control-Overhead Asynchronous Differential Equation Solver, Proceedings of the 3rd International Symposium on Advanced Research in Asynchronous Circuits and Systems, p.140, April 07-10, 1997

INDEX TERMS

Primary Classification:
  J. Computer Applications

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Algorithms implemented in hardware

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

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

Keywords:
Time separation of events, timing constraint graph, min/max constraints, polynomial-time algorithm, conservative approximation, non-convex feasible space, convex approximation.