DYNAMIC LOAD BALANCING OF PARALLEL COMPUTATIONAL ITERATIVE ROUTINES ON HIGHLY HETEROGENEOUS HPC PLATFORMS
Abstract
Traditional load balancing algorithms for data-intensive iterative routines can successfully load balance relatively small problems. We demonstrate that they may fail on highly heterogeneous HPC platforms. Traditional algorithms use models of processors' performance which are too simplistic to reflect the many aspects of heterogeneity. This paper presents a new class of dynamic load balancing algorithms based on the advanced functional performance models. The models are functions of problem size and are built adaptively by measuring the execution time of each iteration. Two particular load balancing algorithms of this class are presented in the paper. The low execution cost of distribution of computations between heterogeneous processors in these algorithms make them suitable for employment in self-adaptable applications. Experimental results demonstrate that our algorithms can successfully balance data-intensive iterative routines on parallel platforms with high heterogeneity for the whole range of problem sizes.
References
- Cluster Comput. 6, 7 (2003), DOI: 10.1023/A:1020958815308. Crossref, Google Scholar
- Computer J. 40, 356 (1997), DOI: 10.1093/comjnl/40.6.356. Crossref, ISI, Google Scholar
- Higgins, R., Modelling the Performance of Processors in Heterogeneous Computing Environments. PhD Thesis, School of Computer Science and Informatics, University College Dublin, 2011 . Google Scholar
- Int. J. High Perform. Comput. Appl. 21, 76 (2007), DOI: 10.1177/1094342006074864. Crossref, ISI, Google Scholar
A. Lastovetsky and R. Reddy , Distributed Data Partitioning for Heterogeneous Processors Based on Partial Estimation of their Functional Performance Models, HeteroPar'20096043,LNCS (Springer, 2010) pp. 91–101. Google ScholarS. Ichikawa and S. Yamashita , Static Load Balancing of Parallel PDE Solver for Distributed Computing Environment, PDCS-2000 (2000) pp. 399–405. Google Scholar- IEEE T. Parall. Distr. 15, 546 (2004), DOI: 10.1109/TPDS.2004.10. Crossref, ISI, Google Scholar
- J. Supercomput. (2009). Google Scholar
X.-Y. Li and S.-H. Teng , Dynamic Load Balancing for Parallel Adaptive Mesh Refinement, IRREGULAR'98 (Springer, 1998) pp. 144–155. Google ScholarI. Galindo , F. Almeida and J. M. Badía-Contelles , Dynamic Load Balancing on Dedicated Heterogeneous Systems, EuroPVM/MPI 2008 (Springer, 2008) pp. 64–74. Google ScholarS. F. Hummel , Load-sharing in heterogeneous systems via weighted factoring, SPAA'96 (ACM, 1996) pp. 318–328. Google Scholar- J. Supercomput. 44, 41 (2008). Crossref, ISI, Google Scholar
- J. Parallel Distr. Com. 7, 279 (1989), DOI: 10.1016/0743-7315(89)90021-X. Crossref, ISI, Google Scholar
- IEEE T. Parall. Distr. 16, 289 (2005), DOI: 10.1109/TPDS.2005.45. Crossref, ISI, Google Scholar
A. Lastovetsky , R. Reddy and R. Higgins , Building the Functional Performance Model of a Processor, SAC 2006 (ACM, 2006) pp. 746–753. Google Scholar- , Numerical Methods for Nonlinear Algebraic Equations, eds.
Gordon and Breach (1970) pp. 87–114. Google Scholar - J. ACM 17, 589 (1970), DOI: 10.1145/321607.321609. Crossref, ISI, Google Scholar
- , Numerical Methods for Nonlinear Algebraic Equations, eds.
Gordon and Breach (1970) pp. 115–161. Google Scholar


