Allocating Independent Subtasks on Parallel Processors.

When using MIMD (multiple instruction, multiple data) parallel computers, one is often confronted with solving a task composed of many independent subtasks where it is necessary to synchronize the processors after all the subtasks have been completed. This paper studies how the subtasks should be allocated to the processors in order to minimize the expected time it takes to finish all the subtasks (sometimes called the makespan). We assume that the running times of the subtasks are independent, identically distributed, increasing fail- ure rate random variables, and that assigning one or more subtasks to a processor entails some overhead, or communication time, that is in- dependent of the number of subtasks allocated. Our analyses, which use ideas from renewal theory, reliability theory, order statistics, and the theory of large deviations, are valid for a wide class of distributions. We show that allocating an equal number of subtasks to each processor all at once has good efficiency. This appears as a consequence of a rather general theorem which shows how some consequences of the central limit theorem hold even when we cannot prove that the central limit theorem applies. Our methods of analysis permit the determination of an optimal strategy subject to the constraint that each processor must take a fixed number of subtasks at any given time. We show that this strategy can give results remarkably close to an unrestrictedly optimal one. Our analysis is asymptotic as the number of subtasks and processors become large. [ABSTRACT FROM AUTHOR]