Scheduling divisible tasks under production or utilization constraints

Abstract

Several problems in science and engineering admit algorithmic solutions that demand a large amount of computing time. Among these applications are genotype sequencing, gene sequence comparison, protein folding, quantum chemistry, computational uid dynamics, and Earth simulation. In most of these cases, a single computer does not provide enough computing power to satisfy these needs, and therefore, the design of parallel methods is of crucial importance. It has been observe in practice that many of these algorithmic solutions acquire the form of a master-worker algorithm. Due to their availability and low cost, heterogeneous networks of computers are becoming a popular alternative for these implementations. One problem, frequently faced by implementers is how to divide and distribute the parallel segments of computing tasks among the computers. This is the essence of the so-called task scheduling problem. Efficiently managing the computations is a difficult and challenging problem. This efficiency depends on the number of rounds of computation, the sizes of the data chunks sent in a round, and the number and the activation sequence of the participating workers. In this dissertation variants and extensions of ideas related to the scheduling of master-worker tasks on heterogeneous star networks are introduced. Some of these ideas were previously discussed in the form of theoretical frameworks for steadystate scheduling or as a divisible load theory. This dissertation combines some elements of these previous works to construct a new framework, and from it, an efficient algorithm (SCOW) for identifying a deterministic scheduler for clusters of workers. SCOW produces the parameters of a periodic user-level scheduler for a single-program multiple-data implementation of a master-worker parallel solution. SCOW minimizes the job make-span under either maximal production per period, or perfect worker utilization. The eficiency of the scheduler identified by SCOW is demonstrated through comparison with other schedulers, including those derived from the above mentioned theoretical frameworks. As shown in the simulation an actual computer runs, the scheduler identified by SCOW outperform in most cases those produced by the previous frameworks.