Scheduling and mapping of computations onto processors is one of the crucial components of a parallel processing environment. Since the scheduling and mapping problems are known to be NP-complete in many variants, most of the previous solutions are based on heuristics. However, these approaches make simplifying assumptions about the parallel program and the target machine architecture, and, therefore, can be useful in very limited environments. In this thesis, we propose efficient algorithms for compile-time scheduling and mapping of parallel programs onto parallel processing systems, under more realistic assumptions. Our first algorithm, called the Dynamic Critical Path (DCP) algorithm, which is designed for scheduling arbitrary task graphs on unlimited and fully connected processors,...[ Read more ]

Scheduling and mapping of computations onto processors is one of the crucial components of a parallel processing environment. Since the scheduling and mapping problems are known to be NP-complete in many variants, most of the previous solutions are based on heuristics. However, these approaches make simplifying assumptions about the parallel program and the target machine architecture, and, therefore, can be useful in very limited environments. In this thesis, we propose efficient algorithms for compile-time scheduling and mapping of parallel programs onto parallel processing systems, under more realistic assumptions. Our first algorithm, called the Dynamic Critical Path (DCP) algorithm, which is designed for scheduling arbitrary task graphs on unlimited and fully connected processors, is based on new principles. The DCP algorithm outperforms all of the contemporary scheduling algorithms known to us. The second algorithm, called the Critical Path Fast Duplication (CPFD) algorithm, is designed to exploit task duplication in scheduling. Using task duplication can drastically reduce the communication overhead. The CPFD algorithm outperforms two previous algorithms which are recently reported. We have developed a number of versions of this algorithm which can be used in limited or unlimited homogeneous as well as heterogeneous processors such as a cluster of workstations. The most attractive feature of these algorithms is that they can automatically adjust the degree of duplication depending upon the speed of the communication network and the number of processors available in the target system. The third algorithm, named the Bubble Scheduling and Allocation (BSA) algorithm, is a based on a novel technique which is different from the classical methods. It works by injecting all of the tasks of a parallel program to one processor in a serial fashion first. The tasks are then "bubbled up" to other processors depending upon the network topology The BSA algorithm not only schedules tasks but also schedules communication edges on the communication channels. The algorithm can be used with any routing strategy and can optimize itself on any network topology. Our five proposed algorithms, as well as a number of algorithms proposed by others, have been implemented into an interactive software tool called CASCH (Computer-Aided SCHeduling).