Performance of Pipelined Asynchronous Systems

Formal Modeling and Analysis of Timed Systems
Eds.: P. Pettersson, Wang Yi
Springer 2005, Lect. Notes Comput. Sci. 3829, 242 – 257
Copyright by Springer, Berlin, Heidelberg DOI: 10.1007/11603009_19

A testing-based faster-than relation has previously been developed that compares the worst-case efficiency of asynchronous systems. This approach reveals that pipelining does not improve efficiency in general; that it does so in practice depends on assumptions about the user behaviour. Accordingly, the approach was adapted to a setting where user behaviour is known to belong to a specific, but often occurring class of request-response behaviours; some quantitative results on the efficiency of the respective so-called response processes were given.

In particular, it was shown that in the adapted setting a very simple case of pipelined process with two stages is faster than a comparable atomic processing. In this paper, we determine the performance of general pipelines, study whether the adapted faster-than relation is compatible with chaining (used to build pipelines) and two other operators, and give results on the performance of the resp. compositions, demonstrating also how rich the request-respond setting is.