A tool for efficient execution and development of repetitive task graphs on a distributed memory multiprocessor
Koman, Charles Brian
MetadataShow full item record
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.
RightsThis 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.
Showing items related by title, author, creator and subject.
Keys, Richard Toney (Monterey, California. Naval Postgraduate School, 1994-09);The U.S. Navy's new multiprocessor, the AN/UYS-2 Enhanced Modular Signal Processor (EMSP) utilizes a First-Come-First-Serve (FCFS) algorithm to transfer data. This algorithm is simple to implement but provides no mechanism ...
A periodic scheduling heuristic for mapping iterative task graphs onto distributed memory multiprocessors Kasinger, Charles D. (Monterey, California. Naval Postgraduate School, 1994-09);This thesis investigates the problem of statically assigning the tasks of applications represented by repetitive task graphs (such as sonar or radar signal processing) to the processors of a distributed memory multiprocessor ...
Christianson, Brian K.; Kimsey, Andrew J. (Monterey, California. Naval Postgraduate School, 2000-03);Large enclosures offer a myriad of possibilities for virtual environments and can dramatically improve presence for a number of applications. Scene graphs are accepted as the logical and optimized way to generate and render ...