A tool for efficient execution and development of repetitive task graphs on a distributed memory multiprocessor
Loading...
Authors
Koman, Charles Brian
Subjects
Advisors
Zaky, Amr
Date of Issue
1995-09
Date
September 1995
Publisher
Monterey, California. Naval Postgraduate School
Language
en_US
Abstract
The major problem addressed by this research is the development of one or more scheduling heuristics suitable for applications which involve repetitive execution of task graphs on a distributed memory multiprocessor, and to test the performance of these heuristics on a multiprocessor. The approach taken was to create more than one modified version of the PS heuristic previously introduced. The modifications aim to provide a more realistic characterization of the computation-communication mechanism for the machine used in the experiments. In order to identify these characteristics, the performance of the system was comprehensively tested using different kinds of experiments. In addition, tools were developed to facilitate the development of acyclic applications. The programming tools developed require the programmer to write the program such that each node of the graph is a separate function. These functions are then packaged and converted to compilable source code in a high level programming language. The heuristic were tested using two actual applications, the correlator and Gaussian elimination, and a set of randomly created acyclic task graphs whose structure resembles realistic applications. These task graphs were created, scheduled, and packaged using RPS. Task graphs scheduled using RPS are shown to produce, on the average, efficiencies of 67 percent on four processors and 59 percent with eight processors for graphs with a 10 to 1 computation-communication ratio. The other extreme, graphs with a 1 to 1 computation-communication ratio, produced no appreciable speedup.
Type
Thesis
Description
Series/Report No
Department
Computer Science
Organization
Identifiers
NPS Report Number
Sponsors
Funding
NA
Format
146 p.
Citation
Distribution Statement
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.