Distributed pipeline scheduling: A framework for design of large-scale, distributed, heterogeneous real-time systems

An increasing number of real-time applications execute over distributed, heterogeneous system resources, i.e., CPUs, networks, buses and disks, have specific end-to-end timing requirements and have non-linear flow specifications due to forks, feedback and synchronization. These applications increasingly execute over a common, integrated computer system infrastructure shared among many real-time and non-real time application streams to amortize the design costs. Because multiplexing the execution of a diverse set of end-to-end application streams over shared resources can lead to unpredictability, and therefore missed timing guarantees, designing highly efficient and predictable distributed real-time systems is a challenge. Current design approaches frequently make assumptions that render the theory impractical for real system design. Further, the solutions proposed do not scale well to large system design. Recent work in the real-time network domain has addressed some of these problems. However, the solutions provided only address the network/communications components of real-time system design and not the more general heterogeneous system design problem.;This research aims to provide a general design solution that bridges the gap between recent work in network design and the more general heterogeneous system design problem. We propose a framework, denoted the Distributed Pipeline Scheduling Framework, that provides a systematic approach towards designing distributed, heterogeneous real-time systems. Distributed Pipelining Scheduling includes a set of abstractions and transformations to map applications to system resources, distributed pipeline scheduling policies for efficient and predictable resource usage by applications, and timing analysis algorithms for analyzing heterogeneous, distributed systems to ascertain that application timing requirements are met. Distributed pipeline scheduling policies extend previous work in the network domain to provide predictable system execution for the multi-rate, heterogeneous resource, non-linear application flow system domain. Timing analysis algorithms extend previous work by allowing analysis of application streams executing on heterogeneous system resources with non-linear flow specifications such as synchronization and feedback. The mapping algorithm determines the optimal path for a linear application stream that meets all application processing and timing requirements and optimizes system design objectives. The novel contribution of the least cost path mapping algorithm is in its simultaneous allocation and routing of application streams over system resources to escape local minimas.