Real-time execution control of task-level data-flow graphs using a compile-time approach
By: Shridhar B. Shukla, Brian Little, Amr Zaky
Contributors: Little, Brian S.; Zaky, Amr; Naval Postgraduate School (U.S.). Dept. of Electrical and Computer Engineering
Publisher: Naval Postgraduate School; Available from National Technical Information Service
Published: 1992
Place of publication: Monterey, Calif; Springfield, Va
Language: eng
Number of pages: 27
Subjects: GRAPHS; REAL TIME; SYSTEMS APPROACH; COMPILERS
Other titles: NPS-EC-92-007.
Description: 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.
Notes: Title from cover.

"NPS-EC-92-007."

"April 1992."

AD A256 086.

Includes bibliographical references (p. 26-27).

aq/aq cc:9116 06/08/98