Scheduling techniques for multiple processor systems in real-time environments
Quigg, John Howard
MetadataShow full item record
Directed Acyclic Graph Scheduling is a technique used to implement the real-time execution of Digital Signal Processing applications on multiple- processor data-flow machines that support variable-grained parallelism. The approach used in the Navy's AN/UYS-2 Digital Signal Processor statically schedules an application graph at run-time using a First-Come-First-Served (FCFS) policy. Research by Shukla and Zaky Shukla 91 developed a new algorithm, the Revolving Cylinder(RC), to ameliorate the inherently non-deterministic output flow of the FCFS scheduling approach currently used in the system. Although the RC technique solved the problem of output-flow determinism there was no broad coverage of other current research in the very specialized field of real-time data-flow machines. This thesis reviews Revolving Cylinder analysis and then surveys, compares, and evaluates research in the field using the review as a baseline for comparison. The RC approach is best at improving the throughput and output flow determinism of a narrow range of applications on a particular architecture. Each of the other approaches offer improvements over RC scheduling in either performance as measured by throughput or through flexibility in applications handled. For each of these improvements, however, significant trade-offs are made and so improvements become relative when they affect system robustness and an ability to handle repeated execution of application graphs. The AN/UYS-2 can implement RC scheduling with a minimum of cost and no hardware reconfiguration and this makes it the best approach for short-term system
Approved for public release; distribution is unlimited
Showing items related by title, author, creator and subject.
Fu Chen-Hua (Monterey, California: Naval Postgraduate School, 1993-03);Efficient performance and high throughput are the major goals of the network performance management. How can we achieve these goal? First, it is necessary to know the network traffic situations. This thesis research ...
Shukla, Shridhar B.; Little, Brian S.; Zaky, Amr (Monterey, California. Naval Postgraduate School, 1992-04); NPS-EC-92-007Efficient 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 ...
A periodic scheduling heuristic for mapping iterative task graphs onto distributed memory multiprocessors Kasinger, Charles D. (Monterey, California. Naval Postgraduate School, 1994-09);This thesis investigates the problem of statically assigning the tasks of applications represented by repetitive task graphs (such as sonar or radar signal processing) to the processors of a distributed memory multiprocessor ...