R. Berks,
Performance Analysis of Asynchronous Networks PhD Thesis,
Department of Computer Science,
University of Waterloo, Waterloo, Ontario, Canada N2L 3G1,
July 1998.
(Supervised by J. C. Ebergen)

Abstract

Asynchronous networks present unique problems in timing analysis. Each component of an asynchronous network may have a delay different from other components, and moreover, the delay within a component may vary from communication to communication. Because the components synchronise with each other locally, the differences in delay can lead to blocking when a component tries to communicate data to another component that is not ready for new data.

We give an analytical technique for finding bounds on the speed of asynchronous networks of components. We give results as closed-form formulae for the worst-case response time and average response time. Response time is the time between a request made to the network and an acknowledging response made by the network. We also give results for the worst-case cycle time and average cycle time. Cycle time is the time between consecutive requests made to the network. In particular, we give bounds for linear arrays of cells and for tree architectures. We give bounds on average cycle time for more general networks.

We use parameters to describe the handshaking behaviour of components, the size of the network, and the delay bounds of each component of the network. These parameters may be instantiated with numeric values to obtain specific results. Closed-form formulae give us insight into design trade-offs and optimisation of asynchronous architectures. We derive formulae by means of proofs, not simulation.