This thesis is concerned with the computation of buffer capacities that guarantee satisfaction of timing and resource constraints for task graphs with aperiodic task execution rates that are executed on run-time scheduled resources. Stream processing applications such as digital radio baseband processing and audio or video decoders are often firm real-time embedded systems. For a real-time embedded system, guarantees on the satisfaction of timing constraints are based on a model. This model forms a load hypothesis. In contrast to hard real-time embedded systems, firm real-time embedded systems have no safety requirements. However, firm real-time embedded systems have to be designed to tolerate the situation that the load hypothesis is inadequate. For stream processing applications, a deadline miss can lead to a drastic reduction in the perceived quality, for instance the loss of synchronisation with the radio stream in case of a digital radio can result in a loss of audio for seconds. For power and performance reasons, stream processing applications typically require a multiprocessor system, on which these applications are implemented as task graphs, with tasks communicating data values over buffers. The established time-triggered and event-triggered design paradigms for real-time embedded systems are not applicable. This is because time-triggered systems are not tolerant to an inadequate load hypothesis, for example non-conservative worst-case execution times, and event-triggered systems have no temporal isolation from their environment. Therefore, we introduce our data-driven approach. In our data-driven approach, the interfaces with the environment are time-triggered, while the tasks that implement the functionality are data-driven. This results in a system where guarantees on the satisfaction of the timing constraints can be provided given that the load hypothesis is adequate. If the load hypothesis is inadequate, then for instance non-conservative worst-case execution times do not immediately result in corrupted data values and undefined functional behaviour. Stream processing applications are increasingly adaptive to their environment, for example digital radios that adapt to the channel condition. This adaptivity results in increasingly intricate sequential control in stream processing applications. The implementations of stream processing applications as task graphs, consequently, have inter-task synchronisation behaviour that is dependent on the processed data stream. Currently, cyclo-static dataflow is the most expressive model that is applicable in our data-driven approach and that can provide guarantees on the satisfaction of timing constraints. However, cyclo-static dataflow cannot express inter-task synchronisation behaviour that is dependent on the processed data stream. Boolean dataflow can express inter-task synchronisation behaviour that is dependent on the processed data stream. However, for boolean dataflow, and models with similar expressiveness, deadlock-freedom is an undecidable property, and there is no known approach to conservatively decide on deadlock-freedom. Since deadlock-freedom guarantees progress, the ability to (conservatively) decide on deadlock-freedom is necessary to guarantee satisfaction of timing constraints. A second trend is that stream processing applications increasingly process more independent streams. Typically, timing constraints are specified per stream. We apply on every shared resource a run-time scheduler that by construction guarantees every task a resource budget. These schedulers allow to provide timing guarantees per stream that are only dependent on the load hypothesis for the processing of this stream. However, currently, there is only limited support for the inclusion of the effects of run-time scheduling in dataflow graphs in order to provide guarantees on the satisfaction of the timing constraints for this stream. The programming of stream processing applications on embedded multiprocessor systems involves the partitioning of the application in a task graph, binding tasks to processors and buffers to memories, selection of scheduler settings, and determination of buffer capacities. All these decisions together should result in a configuration for which we can guarantee that the timing constraints of the application are satisfied. The determination of buffer capacities that are sufficient to guarantee satisfaction of the timing constraints is an essential kernel of automated programming flows for stream processing applications. However, currently, buffer capacities are determined with dataflow analysis by iterating through the possible buffer capacities and for every selection of buffer capacities analyse whether the timing constraints are satisfied. Both the iteration as well as the analysis have an exponential complexity in terms of the graph size. This thesis presents an algorithm that uses a new dataflow model, variable-rate phased dataflow, to compute buffer capacities that guarantee satisfaction of timing and resource constraints for run-time scheduled task graphs that have inter-task synchronisation behaviour that is dependent on the processed data stream. Variable-rate phased dataflow allows to model task graphs with inter-task synchronisation behaviour that is dependent on the processed stream, examples include DRM and DAB digital radio, MP3 decoding and H.263 video decoding. Previously, no techniques were available to guarantee the satisfaction of timing constraints for this class of applications. Furthermore, we show that the effects of run-time schedulers can be conservatively included in variable-rate phased dataflow, given that by construction these run-time schedulers provide every task a resource budget. These two essential extensions together with the low run-time and low computational complexity of our algorithm enable automated programming flows for a significantly broader class of applications and architectures.
|Award date||19 Jun 2009|
|Place of Publication||Enschede|
|Publication status||Published - 19 Jun 2009|
- data flow analysis