Optimal partitioning of randomly generated distributed programs

Abstract

An investigation is made of an optimal task-assignment policy for a random-graph model of a distributed program. The model of the distributed computer system assumes that communications overhead adds to total run time and that total run time decreases as the number of processors running the program is increased. When the processors are homogeneous, the optimal task-assignments are external in the sense that tasks are totally distributed among all processors as evenly as possible or not distributed at all. The point at which the policy shows a sharp change of behavior depends upon the ratio of run times to communication times. The authors derive two important properties of the optimal task-assignments for heterogeneous processors. The first property is that an optimal policy distributes the cost of processing among the processors as evenly as possible so that a processor with higher speed gets more tasks and vice versa. The second property determines the number of processors among which to distribute the tasks evenly. In the special case when there is a uniform degradation of processing speed, it is shown that the optimal policy again exhibits an extremal characteristic.