Efficient Scheduling of Real-Time Compute-Intensive Periodic Graphs on Large Grain Data Flow Multiprocessor
Abstract
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 massive amount of parallelism inherent in many types of computation. They are programmed using directed graphs whose vertices are function modules and whose edges denote data dependencies between function modules. An important subclass of DF is Large Grain Data Flow (LGDF) which is efficiently used in computation intensive applications, such as signal processing. Presently, most leadoffs incorporate nondeterministic run-time technique to allocate system resources to support the execution (One such technique could be First Come First Served). Despite of the usual simplistic nature of scheduling techniques which, results in a low run-time overhead, the system throughput and predictability could rapidly degrade under high system load. To provide uniform output and improve the resource usage even under a high load, a compile-time technique called Revolving Cylinder (RC) was introduced. In this thesis, we present a LGDF simulator and a Graph restructurer that restructures the given graph according to the RC technique. We then perform a comparative experimental study of the different implementation of RC and the FCFS scheduling techniques. Our results demonstrate that there is a high potential for the RC technique, if a satisfactory node mapping technique is developed.... Large Grain Data Flow, Data Flow, Scheduling, Graph restructuring, Runtime, Real-time, Compile-time, Resource usage, Throughput
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 01, 1993
- Accession Number
- ADA267444
Entities
People
- Cem Akin
Organizations
- Naval Postgraduate School