Title :
An algorithm for exact bounds on the time separation of events in concurrent systems
Author :
Amon, Tod ; Hulgaard, Henrik ; Burns, Steven M. ; Borriello, Gaetano
Author_Institution :
Dept. of Comput. Sci. & Eng., Washington Univ., Seattle, WA, USA
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. The algorithm is based on a functional decomposition technique that permits the implicit evaluation of an infinitely unfolded process graph
Keywords :
computational complexity; graph theory; multiprocessing systems; optimisation; real-time systems; analysis; arbitrary process graph; asynchronous digital circuits; concurrent systems; conditional behavior; exact bounds; execution times; functional decomposition technique; infinitely unfolded process graph; logic optimization; optimization; real-time systems; synthesis; time separation; Circuit synthesis; Computer science; Data mining; Delay; Hazards; Logic circuits; Real time systems; Timing; Topology;
Conference_Titel :
Computer Design: VLSI in Computers and Processors, 1993. ICCD '93. Proceedings., 1993 IEEE International Conference on
Conference_Location :
Cambridge, MA
Print_ISBN :
0-8186-4230-0
DOI :
10.1109/ICCD.1993.393387
