Solutions to Parallel and Distributed Computing Problems: Lessons from Biological Sciences

9.2 STATIC SCHEDULING OF PARALLEL PROGRAMS TO MESSAGE-PASSING ARCHITECTURES

Given a parallel program to be executed on a message-passing multiprocessor system, we would like to achieve the minimum turnaround time (or overall execution time—the time elapsed when the program starts till the program finishes). To this end, we need to properly assign the computation workload to the processors and arrange the communications among the processors. Thus, we need to tackle task allocation and scheduling problems for multiple processors in the system. Unlike the uniprocessor scheduling problem, which has been successfully tackled by many researchers, the multiprocessor counterpart is much more complicated. In the first place, we need a realistic model of a parallel program. Second, we have to use some sort of partitioning techniques to segregate the computations into tasks of a desired granularity level. Finally, we need to use an effective scheduling algorithm to do the sequencing and task allocation. This process is illustrated in Fig. 9.1.

A parallel program is composed of multiple interacting tasks. A task is a sequence of program instructions (may contain loops) that collectively serve a particular function (functional task) or work on a certain subset of the input data (data parallel task). The size of a task, in terms of the number of instructions, is determined by the desired granularity level. (We are not concerned about the granularity issue and the partitioning techniques in this ...