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.
Showing items related by title, author, creator and subject.
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 ...
Loomis, Herschel H., Jr.; Dinolt, George W.; Kragh, Frank E. (Monterey, California. Naval Postgraduate School, 2014-03); NPS-EC-14-002This report provides results of a study of the application to software-defined radios (SDR) of the Maestro 49-tile Radiation-Hard-by-Design multi-processor chip developed by Boeing Corporation for the U.S. Government using ...
The Naval Postgraduate School secure archival storage system, Part II : Segment and process management implementation Schell, Roger R.; Perdue, Sonja L.; Cox, Lyle Ashton (Monterey, California. Naval Postgraduate School, 1981-03); NPS-52-81-001The security kernel technology has provided the technical foundation for highly reliable protection of computerized information. However, the operating system implementations face two significant challenges: providing (1) ...