Stochastic scheduling of data for minimizing execution time of SPMD applications

Abstract

This paper introduces a static load balancing algorithm for SPMD type of applications executing on a shared heterogeneous computing system. This novel algorithm is motivated from the fact that the mean values of the computing system parameters are used to split the data domain of SPMD applications by previous load balancing algorithms, and these values might be quite different from the runtime values. To achieve good load balance during the execution of the application, the proposed algorithm, the stochastic time balancing algorithm (STBA), accounts for the fluctuations in the loads of the machines and the communication network by representing the system parameters as random variables. The estimation of the probability density functions of these random variables which are needed for the STBA is avoided by approximating them using the method of exponential stages. Simulation results are provided to validate the positive impact of the STBA on the performance of an example SPMD applications.