language: en

Distributed Pipeline Scheduling: End-to-End Analysis of Heterogeneous, Multi-Resource Real-Time Systems

Saurav Chatterjee and Jay Strosnider
Department of Electrical & Computer Engineering Carnegie Mellon University
Pittsburgh, PA 15213

[This research was supported in part by a grant from the Office of Naval Research, in part by a grant from the Naval Research and Development Laboratory, and in part by a grant from Siemens Corporate Research.]

[In 15th IEEE International Conference on Distributed Computing Systems, May 1995.]

Abstract This paper presents an hierarchical end-to-end analysis technique that decomposes the very complex heterogeneous multi-resource scheduling problem into a set of single resource scheduling problems with well defined interactions. We define heterogeneity both in resource types, e.g., CPU, and in scheduling policies, e.g., rate-monotonic scheduling. This analysis technique is one phase of our systems integration framework for designing large-scale, heterogeneous, distributed real-time systems whose timing properties can be strictly controlled and analyzed. This approach, denoted the Distributed Pipelining Framework, exploits the natural pipelining execution pattern found in a large number of continuous (periodic) applications executing over heterogenous resources. A teleconference application is used in this paper to show the utility of the approach.

1. Introduction