Performance of pipelined asynchronous systems

J. Logic and Algebraic Programming 70 (2007) 201 – 221 DOI: 10.1016/j.jlap.2006.08.005

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 a pipelined process with two stages is faster than a comparable atomic processing of the two stages.

In this paper, we determine the performance of general pipelines, which is not so easy in an asynchronous setting. Pipelines are built with a chaining operator; we also study whether the adapted faster-than relation is compatible with chaining and two other parallel composition operators, and give results on the performance of the respective compositions. These studies also demonstrate how rich the request-respond setting is.