MULTIPROCESSOR SCHEDULING PROBLEM FOR GENERALIZED PARALLEL COMPUTATIONS: A HEURISTIC APPROACH

Abstract

One measure of usefulness of a general-purpose multiprocessor computing system, is the system's ability to provide a level of performance commensurate to the degree of multiplicity of processors present In the system. In such systems a modular source program must have Its modules (processes) assigned among the processors so as to avoid excessive Interprocessor communication while taking advantage of' specific efficiencies of some processors in executing some program modules. Also for the given set of processes and the dependency relationships between them, the tasks must be assigned to processors such that the total execution time is minimized, and minimum number of processors are used. Hence the assignment of processes. to processors (the scheduling problem) is one of the major factors affecting the performance of a parallel system. The scheduling problem becomes more severe when the dependency structure of a parallel algorithm differs from the processor interconnection of the parallel computer or when the number of processes generated by the source program exceeds the number of processors available. In this thesis work a new generalized scheduling strategy has been studied that uses a combination of graph theory, mathemati.cal programming, and heuristics. 1 h approach consists of preparing graphical representation of the parallel algorithm (problem graph) and the parallel computer (host graph). Using these representations, a set of pseudo processors and their graphical representation (extended ,host graph) on which the problem graph is mapped has been generated. This scheduling scheme uses an accurate characterization of the communication overhead. An objective function is formulated to evaluate the optimallty of mapping a problem -graph onto a system graph. This objective function is different from the conventional objective function in that the edges in the problem graph are weighted and the actual distance rather than the nominal distance for the edges in the system graph Is employed. This facilitates a more accurate quantification of the communication overhead. This model includes interference costs which reflect the nature of (I/O or CPU bound) task. The inclusion of Interference costs in the model yields assignments with greater concurrency, thus overcoming the tendency to assign all tasks to one or a few processors. Also load unbalance among processors is limited with in specified limits. Hence the given scheduling algorithm seeks to assign tasks to processors in order to achieve goals such as minimization of interprocessor communication and waiting times, good load balancing among the processors, quick turnaround time and a high degree of parallelism, in general. Hence the objective function includes minimizing the communication overhead and minimizing the total execution time (computation time plus communication time). An efficient mapping scheme has been developed for the objective functions, where two levels of assignment optimization procedures are employed: initial assignment and pair wise exchange based on some heuristics.