A Delay Composition Theorem for Real-Time Pipelines

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 ef-fectively transforms the pipeline into a single stage system. The wealth of schedulability analysis techniques derived for uniprocessors can then be applied to decide the schedula-bility of the pipeline. The transformation does not require imposing artitical per-stage deadlines, but rather models the pipeline as a whole and uses the end-to-end deadlines di-rectly in the single-stage analysis. It also does not make as-sumptions 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 sufciently large. The reason lies in the way we account for execution overlap among stages. We dis-cuss 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 de-lay composition rule, derived in this paper, may be a step to-wards a general schedulability analysis foundation for large distributed systems. 1