loading...
A Delay Composition Theorem for Real-Time Pipelines
Pisa, Italy July 04-July 06
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ECRTS.2007.8019th Euromicro Conference on Real-Tim ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Praveen Jayachandran, University of Illinois, USA
Tarek Abdelzaher, University of Illinois, USA
Uniprocessor schedulability theory made great strides, in part, due to the simplicity of composing the delay of a job from the execution times of higher-priority jobs that preempt it. In this paper, we bound the end-to-end delay of a job in a multistage pipeline as a function of higher-priority job execution times on different stages. We show that the end-to-end delay is bounded by that of a single virtual "bottleneck" stage plus a small additive component. This contribution effectively transforms the pipeline into a single stage system. The wealth of schedulability analysis techniques derived for uniprocessors can then be applied to decide the schedulability of the pipeline. The transformation does not require imposing artitifical per-stage deadlines, but rather models the pipeline as a whole and uses the end-to-end deadlines directly in the single-stage analysis. It also does not make assumptions on job arrival patterns or periodicity and thus can be applied to periodic and aperiodic tasks alike. We show through simulations that this approach outperforms previous pipeline schedulability tests except for very short pipelines or when deadlines are sufficiently large. The reason lies in the way we account for execution overlap among stages. We discuss how previous approaches account for overlap and point out interesting differences that lead to different performance advantages in different cases. We hope that the pipeline delay composition rule, derived in this paper, may be a step towards a general schedulability analysis foundation for large distributed systems.
Citation:
Praveen Jayachandran, Tarek Abdelzaher, "A Delay Composition Theorem for Real-Time Pipelines," ecrts, pp.29-38, 19th Euromicro Conference on Real-Time Systems (ECRTS'07), 2007
Usage of this product signifies your acceptance of the Terms of Use.