TASK-SCHEDULING IN MULTIPROCESSING SYSTEMS

A scheduling problem arises when concurrent parts of a parallel progra m must be arranged in time and space so that the program's overall exe cution time is minimized. A program can be viewed as a collection of t asks that may run serially or in parallel. The goal of scheduling is t o determine an assignment of tasks to processing elements and to prior itize task execution to optimize certain performance measures. The aut hors look at different forms of the scheduling problem and survey rele vant models, optimal algorithms, heuristic algorithms, and useful soft ware tools. They provide models for representing parallel programs, pa rallel systems, and communication cost. Examples and algorithms illust rate various approaches to scheduling. The scheduling problem, which i s NP-complete, has led to the development of numerous heuristics for a pproximating an optimal solution; each may work under differ ent circu mstances. The effectiveness of these heuristics depends on factors suc h as grain size, interconnection topology, communication bandwidth, an d program structure. Scheduling software tools represent another promi sing approach. Working with such tools can help a programmer find answ ers to numerous questions that arise in developing a parallel applicat ion. The authors describe three of these scheduling tools.