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

9.1 INTRODUCTION

Parallel processing is a promising approach to meet the computational requirements of a large number of current and emerging applications. However, it poses a number of problems that are not encountered in sequential processing, such as designing a parallel algorithm for the application, partitioning of the application into tasks, coordinating communication and synchronization, and scheduling the tasks onto the machine. If these problems are not properly handled, parallelization of an application may not be beneficial. A large body of research efforts addressing these problems have been reported in the literature [24, 26]. Among these problems, task scheduling is one of the central issues because an inappropriate scheduling of tasks can fail to exploit the true potential of the system and can easily offset the gain from parallelization due to, for example, excessive communication overhead. In this chapter, we focus on the scheduling problem for message-passing parallel architectures.

The objective of scheduling is to minimize the completion time of a parallel program. In a broad sense, the scheduling problem exists in two forms: static and dynamic. In static scheduling, which is done at compile time, the characteristics of the parallel program, such as task processing times, communication, data dependencies, and synchronization requirements, are known before program execution. This is true for many scientific computational applications. In dynamic scheduling, only ...