Practical applications of an efficient time separation of events algorithm

Abstract

Determining the time separation of events is a fundamental problem in the analysis, synthesis, and optimization of concurrent systems. We present results of applying an efficient algorithm to solve this problem of three different application domains. These are: analysis of instruction execution times of an asynchronous multiprocessor, analysis of a high-performance mixed asynchronous/synchronous communication interface, and isochronic fork analysis in asynchronous circuit synthesis. The algorithm we use yields exact (tight) bounds on the separation time of events in an arbitrary process graph without conditional behavior. This class of graphs is quite large and includes graphs that are not strongly connected. The algorithm is based on a functional decomposition technique that permits the implicit evaluation of an infinitely unfolded process graph.