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

Download
Author
Shukla, Shridhar B.
Little, Brian S.
Zaky, Amr
Date
1992-04Metadata
Show full item recordAbstract
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
NPS Report Number
NPS-EC-92-007Related items
Showing items related by title, author, creator and subject.
-
Diesel Submarine Support to SOF
Ferrer, Geraldo; Veronneau, Simon (Monterey, California: Naval Postgraduate SchoolMonterey, California. Naval Postgraduate School, 2019-12); NPS-19-N062-AGiven the limited availability of submarines to support SOF and the potential to save billions of dollars, as well as improve a capability through quiet, shallow-water capable submarines, a review of potential diesel-electric ... -
Diesel Submarine Support to SOF
Ferrer, Geraldo; Veronneau, Simon (Monterey, California: Naval Postgraduate SchoolMonterey, California. Naval Postgraduate School, 2019-12); NPS-19-N062-AGiven the limited availability of submarines to support SOF and the potential to save billions of dollars, as well as improve a capability through quiet, shallow-water capable submarines, a review of potential diesel-electric ... -
A compile-time approach for chaining and execution control in the AN/UYS-2 parallel signal processor
Bell, Harold A. (Monterey, California. Naval Postgraduate School, 1992-06);The AN/UYS-2 represents the U. S. Navy's effort to meet the signal processing demands of the 21st century. It is programmed using the Processing Graph Methodology (PGM), where signal processiog applications are reproented ...