Performance Characterization on Handling Large-Scale Partitionable Workloads on Heterogeneous Networked Compute Platforms

Multi-installment scheduling (MIS) has shown great effectiveness in minimizing the processing time for large-scale partitionable workloads. To derive an optimal MIS strategy, one has to explicitly determine optimal numbers of installments and processors. Existing studies tend to solve this problem by treating the influence of number of installments (and processors) w.r.t processing time as time-continuous functions and taking the derivative of these functions to determine the optimal values, which may lead to invalid solutions. In this paper, we employ periodic multi-installment scheduling (P-MIS) models for homogeneous and heterogeneous single-level tree networks. Using these models we make the following significant contributions. First, we derive a closed-form solution for an optimal number of installments based on a given network size and a fixed load distribution sequence. Second, we propose a heuristic algorithm for determining an optimal number of processors by first proving several important intermediate lemmas and theorems. Third, for heterogeneous systems, we propose a genetic algorithm to determine an optimal load distribution sequence. Finally, we conduct various experiments to illustrate the effectiveness of the proposed algorithms and perform rigorous analysis on the influence of load distribution sequence on processing time, on the basis of which a practical advice for determining a near-optimal load distribution sequence is given.