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.
展开▼
