Search

Divisible loads are parallel applications with fine granularity and negligible data dependencies. Such computations can be divided into parts of arbitrary sizes and processed independently in parallel. The load distribution process incurs considerable communication delays. To reduce processor waiting time during the computation initialization phase, the load is distributed in multiple small installments rather than in one big chunk. In this paper we analyze multi-installment divisible load processing in heterogeneous distributed systems. Scheduling divisible loads in heterogeneous systems is hard because the sizes of the installments should be adjusted to the communication and computation capabilities of the system. We show that ignoring heterogeneity of the distributed system may result in arbitrarily bad solutions. Two algorithms are proposed to gear the load chunk sizes to different communication and computation speeds: an optimization branch-and-bound algorithm and a heuristic based on a genetic search method. The running times of both methods and the quality of the solutions are compared. Then, we use these algorithms to study the features of the multi-installment divisible load scheduling problem. We demonstrate that it has both combinatorial and algebraic nature, and that optimum solutions are harder to find with the growing heterogeneity of the system. Copyright © 2007 John Wiley & Sons, Ltd.

In this paper we study multi-installment divisible load processing in a heterogeneous distributed system with limited memory. Divisible load model applies to computations which can be arbitrarily divided into parts and performed independently in parallel. The initial waiting for the load may be shortened by sending many small chunks of load instead of one huge. The load chunk sizes must be adjusted to the speeds of communication, computation, and memory sizes, such that the whole processing time is as short as possible. We propose a new realistic model of memory management, and formulate it as mixed quadratic programming problem which is solved by branch and bound algorithm. Since this problem is computationally hard we propose heuristics, and analyze their performance in a series of computational experiments.

In this paper we study multi-installment divisible load processing in heterogeneous distributed systems. Divisible loads are computations which can be divided into parts of arbitrary sizes, and these parts can be processed independently in parallel. In order to reduce the waiting time during the parallel computation initialization phase, load is sent to the processors in multiple small installments. In a heterogeneous system the sizes of the installments should be adjusted to the communication, and computation capabilities of the processors. We propose two algorithms that gear the load chunk sizes to different communication and computation speeds. The first one is an optimization branch and bound algorithm. The second algorithm is based on genetic search. The running times of both methods and the quality of the genetic algorithm solutions are compared. Then, we use these algorithms to analyze features of the scheduling problem solutions.