Accession Number : ADA267444


Title :   Efficient Scheduling of Real-Time Compute-Intensive Periodic Graphs on Large Grain Data Flow Multiprocessor


Descriptive Note : Master's thesis May 92-Mar 93,


Corporate Author : NAVAL POSTGRADUATE SCHOOL MONTEREY CA


Personal Author(s) : Akin, Cem


Full Text : https://apps.dtic.mil/dtic/tr/fulltext/u2/a267444.pdf


Report Date : Mar 1993


Pagination or Media Count : 171


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


Descriptors :   *COMPUTERIZED SIMULATION , *REAL TIME , *GRAPHS , *MULTIPROCESSORS , SIGNAL PROCESSING , SIMULATORS , COMPUTER ARCHITECTURE , NODES , SCHEDULING , THROUGHPUT , COMPILERS , MAPPING , FLOW , RESOURCES , SIGNALS , TIME , THESES , EDGES , COMPUTERS , OUTPUT , COMPUTATIONS


Subject Categories : Numerical Mathematics
      Computer Programming and Software


Distribution Statement : APPROVED FOR PUBLIC RELEASE