Stochastic scheduling of data for minimizing execution time of SPMD applications

Dogan A., Ozguner F.

International Conference on Computer, Communication and Control Technologies (CCCT 03)/9th International Conference on Information Systems Analysis and Synthesis (ISAS03), Florida, Amerika Birleşik Devletleri, 31 Temmuz - 02 Ağustos 2003, ss.42-47 identifier

  • Yayın Türü: Bildiri / Tam Metin Bildiri
  • Basıldığı Şehir: Florida
  • Basıldığı Ülke: Amerika Birleşik Devletleri
  • Sayfa Sayıları: ss.42-47
  • Anahtar Kelimeler: load balancing, SPMD applications, heterogeneous computing, stochastic scheduling
  • Anadolu Üniversitesi Adresli: Hayır

Özet

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.