An algorithm for exact bounds on the time separation of events in concurrent systems
- 1 November 1995
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. 44 (11) , 1306-1317
- https://doi.org/10.1109/12.475126
Abstract
Determining the time separation of events is a fundamental problem in the analysis, synthesis, and optimization of concurrent systems. Applications range from logic optimization of asynchronous digital circuits to evaluation of execution times of programs for real-time systems. We present an efficient algorithm to find exact (tight) bounds on the separation time of events in an arbitrary process graph without conditional 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 algorithm is based on a functional decomposition technique that permits the implicit evaluation of an infinitely unfolded process graph. Examples are presented that demonstrate the utility and efficiency of the solution. The algorithm will form a basis for exploration of timing-constrained synthesis techniques.<>Keywords
This publication has 21 references indexed in Scilit:
- Algorithms for interface timing verificationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Specification and analysis of timing constraints in signal transition graphsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Practical applications of an efficient time separation of events algorithmPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- An algorithm for exact bounds on the time separation of events in concurrent systemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Timing analysis of timed event graphs with bounded delays using algebraic techniquesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- An algorithm for exact bounds on the time separation of events in concurrent systemsIEEE Transactions on Computers, 1995
- Synthesis of timed asynchronous circuitsIEEE Transactions on Very Large Scale Integration (VLSI) Systems, 1993
- Static analysis of real-time distributed systemsIEEE Transactions on Software Engineering, 1990
- Safety analysis of timing properties in real-time systemsIEEE Transactions on Software Engineering, 1986
- Automatic verification of finite-state concurrent systems using temporal logic specificationsACM Transactions on Programming Languages and Systems, 1986