Quantized load distribution for tree and bus-connected processors

Abstract

Divisible load analysis is a valuable tool for generating solutions to data-partitioning and distribution/scheduling problems for data-parallel applications. This paper addresses an essential step required for applying these solutions to real-life problems where computing loads are multiples of some fundamental problem-specific non-divisible load unit. The algorithms that are proposed to this end, are suitable for both single and multi-installment strategies. The worst-case performances of the algorithms are derived for two cases: single installment on a single-level tree and multiple installments on a bus network. Finally, an estimation on the expected performance of the algorithms is obtained from rigorous simulation tests. The extensive analysis that accompanies these tests, depicts many aspects of the parallel computation associated with parallel machine architectures and the load distribution strategies (single- or multi-installment) used. © 2004 Elsevier B.V. All rights reserved.