Scheduling techniques for multiple processor systems in real-time environments

Abstract

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