Timing analysis of asynchronous systems using time separation of events

This paper describes a pseudo-polynomial time algorithm for timing analysis of a class of choice-free asynchronous systems, called tightly coupled sys tems, with both min and max-type timing constraints and bounded component d elays. The algorithm consists of two phases: I) long-term behavior analysis , that computes bounds on the time separation of events after the system ha s run for a sufficiently long period of time, and 2) startup behavior analy sis, that computes time separations between events during an initial startu p period after the system is powered up. The results of the analysis are co nservative in the worst case; nevertheless, they are found to be exact in o ur experiments. To demonstrate the practical utility of the approach, an as ynchronous differential equation solver chip has been modeled and analyzed using the proposed algorithm. We report results of datapath timing verifica tion, intercontroller protocol timing verification and performance analysis of the chip using the proposed technique.