Real-time execution control of task-level data-flow graphs using a compile-time approach

Abstract

Efficient data-flow implementation requires fast run-time mechanisms to detect and dispatch schedulable tasks. However, the inherent non-determinism in data-flow executions and the requirement of fast, and therefore, simple run- time mechanisms necessitate compile-time support to improve performance. In particular, for data-flow execution of applications, such as signal processing which are characterized by periodically received data, compile-time support can be used to control the run-time behavior to improve the predictability and efficiency. In this report, a compile-time technique that supports a simple run- time mechanism to improve throughput and predictability for a task-level data- flow programming model is described. This technique, called the revolving cylinder analysis, restructures the application, described by a task-level data- flow graph. The restructuring is based on wrapping the projected data-flow execution trace on the curved surface of a cylinder whose area depends upon the number of processors and the sum of the task execution times. The behavior of the restructured graph is shown to be more predictable under the same run-time mechanism than that of the old graph. Results on the performance improvement for two typical signal processing applications, viz., a correlator and a fast Fourier Transform, are presented. The potential of this approach in determining the optimal granularity for an application is also described. Compile-time, Data-flow, Graph Restructuring, Real-time, Run-time, Scheduling, Signal Processing, Throughput, Task-level