AN ALGORITHM FOR EXACT BOUNDS ON THE TIME SEPARATION OF EVENTS IN CONCURRENT SYSTEMS

Determining the time separation of events is a fundamental problem in the analysis, synthesis, and optimization of concurrent systems. Appli cations range from logic optimization of asynchronous digital circuits to evaluation of execution times of programs for real-time systems. W e present an efficient algorithm to find exact (tight) bounds on the s eparation time of events in an arbitrary process graph without conditi onal behavior. This result is more general than the methods presented in several previously published papers as it handles cyclic graphs and yields the tightest possible bounds on event separations. The algorit hm is based on a functional decomposition technique that permits the i mplicit evaluation of an infinitely unfolded process graph. Examples a re presented that demonstrate the utility and efficiency of the soluti on, The algorithm will form a basis for exploration of timing-constrai ned synthesis techniques.