Abstractions for aperiodic multiprocessor scheduling of real-time stream processing applications

Embedded multiprocessor systems are often used in the domain of real-time stream processing applications to keep up with increasing power and performance requirements. Examples of such real-time stream processing applications are digital radio baseband processing and WLAN transceivers. These stream processing applications often have a dynamic character. For example the execution times and execution rates of the tasks of the stream processing applications vary and can even be data dependent. To cope with this dynamic behavior, the tasks are executed on the multiprocessor system in a data-driven fashion on run-time scheduled resources. Another important aspect of real-time stream processing applications are their strict performance constraints. A periodic source or sink imposes a throughput constraint and also latency constraints are common. For stream processing applications, violating these constraints typically leads to a major reduction of the quality of service of the applications. To prevent such violations of the temporal constraints, analysis methods are used. These analysis methods ease the processes of dimensioning, programming and optimizing the multiprocessor systems within these temporal constraints. Analysis methods rely on accurate abstractions of the analyzed applications. However, current abstractions have a limited accuracy and applicability and do therefore not always suffice. In this thesis we will present abstractions for multiprocessor systems in which the tasks are executed in a data-driven fashion and in which they have aperiodic schedules. These aperiodic schedules can capture the dynamic behavior of the real-time stream processing applications. We present accurate abstractions based on dataflow analysis techniques which can be used for a large class of multiprocessor systems. Compared to state of the art, we broaden the scope of dataflow analysis techniques, improve their accuracy and provide a new higher level of abstraction.