Performance of pipelined asynchronous systems

Abstract

Abstract 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.

Original document

The different versions of the original document can be found in:

• http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.609.2039

• http://dx.doi.org/10.1016/j.jlap.2006.08.005 under the license http://www.elsevier.com/open-access/userlicense/1.0/

• https://doi.org/10.1016/j.jlap.2006.08.005

• http://www.springerlink.com/index/pdf/10.1007/11603009_19,

http://dx.doi.org/10.1007/11603009_19

• https://api.elsevier.com/content/article/PII:S1567832606000476?httpAccept=text/xml,

https://api.elsevier.com/content/article/PII:S1567832606000476?httpAccept=text/plain,

http://dx.doi.org/10.1016/j.jlap.2006.08.005 under the license https://www.elsevier.com/tdm/userlicense/1.0/

• https://dblp.uni-trier.de/db/journals/jlp/jlp70.html#CorradiniV07,

https://core.ac.uk/display/54642816,

https://www.sciencedirect.com/science/article/pii/S1567832606000476,

https://academic.microsoft.com/#/detail/2039671145

• https://link.springer.com/chapter/10.1007/11603009_19,

https://pubblicazioni.unicam.it/handle/11581/115564,

https://core.ac.uk/display/54642583,

https://dblp.uni-trier.de/db/conf/formats/formats2005.html#CorradiniV05,

https://rd.springer.com/chapter/10.1007/11603009_19,

https://academic.microsoft.com/#/detail/1552367755

• https://opus.bibliothek.uni-augsburg.de/opus4/frontdoor/index/index/docId/35734,

https://doi.org/10.1007/11603009_19

• https://opus.bibliothek.uni-augsburg.de/opus4/frontdoor/index/index/docId/39119,

https://doi.org/10.1016/j.jlap.2006.08.005

DOIS: 10.1016/j.jlap.2006.08.005 10.1007/11603009_19