Practical applications of an efficient time separation of events algorithm

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 eficient algorithm to solve this problem to three different application domains. These are: analysis of instruction execution times of an asynchronous microprocessor, 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.