HP Labs Technical Reports

A Dynamic Approach to Timed Behavior

Gunawardena, Jeremy

HPL-94-41

Keyword(s):

Abstract: In classical applied mathematics time is treated as an independent variable. The equations which govern the behavior of a system enable one to determine, in principle what happens at a given time. This approach has led to powerful techniques for calculating numerical quantities of interest in engineering. The temporal behavior of reactive systems, however, is difficult to treat from this viewpoint: time is usually a dependent variable - packets are timestamped in a distributed system - and it has been customary to rely on logical rather than dynamic methods. In this paper we describe the theory of min-max functions which permits a dynamic approach to the time behavior of a restricted class of reactive systems. These systems arise in practice in the timing analysis of asynchronous circuits, where, in the absence of a clock, it is important to find some measure of the of the speed of a circuit. The cycle time vector of a mini-max function provides the appropriate measure. In this paper we study a fundamental question, the Duality Conjecture, whose affirmative answer would yield a formula for calculating the cycle time vector. Our main result is a proof of the Conjecture for min-max functions of dimension 2. The work described here was done as part of project STETSON, a joint project between HP Labs and Stanford University on asynchronous hardware design.

Back to Index