Accession Number:

ADA276149

Title:

Scheduling Techniques for Multiple Processor Systems in Real-Time Environments

Descriptive Note:

Master's thesis

Corporate Author:

NAVAL POSTGRADUATE SCHOOL MONTEREY CA DEPT OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

1993-09-01

Pagination or Media Count:

77.0

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 Navys ANUYS-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 CylinderRC, 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 ANUYS-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. Data-flow, Digital signal processing, Real-time, Graph restructuring, Throughput.

Subject Categories:

  • Computer Systems Management and Standards

Distribution Statement:

APPROVED FOR PUBLIC RELEASE