| This thesis explores a fundamental issue in large-scale parallel computing: how to schedule tasks on a multiprocessor system.; In Chapter 1, we introduce and motivate the task scheduling problems that we study in this thesis.; In Chapter 2, we devise efficient static scheduling algorithms for tree computations. We first present a linear-time algorithm that yields exactly optimal schedules for coarse-grain tree computations. We then develop scheduling algorithms that yield exactly optimal schedules for fine-grain complete-binary-tree computations. For the case in which the interprocessor communication delay is a multiple of the task computation time, we present a linear-time algorithm that produces exactly optimal schedules for complete-binary-tree computations. For all other cases, we develop an {dollar}O(Nlog N){dollar}-time algorithm that yields an exactly optimal schedule for an N-node complete-binary-tree computation. Hence, our scheduling algorithms expand the known class of efficiently schedulable families of computations. Furthermore, we show experimentally that the makespans of the schedules produced by our scheduling algorithm are close to half of that of the best schedules previously known.; In Chapter 3, we present a low-cost scheduling algorithm for a dynamically evolving computation on a ring of processors. We show that the schedule produced by our scheduling algorithm is within an additive low-order term of the optimal, for any dynamically evolving bushy binary-tree computation.; In Chapter 4, we study online scheduling problems for hierarchically decomposable multiprocessors. Unlike the scheduling problems in Chapter 2 and 3, the problem considered in this chapter is aimed at scheduling independent parallel tasks that arrive over time and require unpredictable service time. The main contribution of this chapter is to present a predictable tradeoff between the performance of the scheduling algorithm and the frequency of the task reallocation of the algorithm. |
