Real-time execution control of task-level data-flow graphs using a compile-time approach
Shukla, Shridhar B.
Little, Brian S.
MetadataShow full item record
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 NumberNPS-EC-92-007
Showing items related by title, author, creator and subject.
Efficient scheduling of real-time compute-intensive periodic graphs on a large grain data flow multiprocessor Akin, Cem (Monterey, California: Naval Postgraduate School, 1993-03);Architectures of computer systems based on Data Flow (DF) concepts attracted great attention as an alternative to conventional sequential architectures (Von Neumann). DF architectures are capable of efficiently exploiting ...
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 ...
Graves, Thomas C. (Monterey, California. Naval Postgraduate School, 1995-03);Shipboard Naval Automated Data Processing (SNAP) is the U.S. Navy's administrative manager for surface ships. The Department of the Navy is developing a replacement system, Naval Tactical Command Support System Administrative ...