Practical applications of an efficient time separation of events algorithm
Henrik Hulgaard, Steven M. Burns, Tod Tracy Amon, Gaetano Borriello · 1993
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 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. 1 Introduction Event based specifications naturally model communication and concurrency and are thus a popular model for a wide range of co...