World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

DYNAMIC LOAD BALANCING OF PARALLEL COMPUTATIONAL ITERATIVE ROUTINES ON HIGHLY HETEROGENEOUS HPC PLATFORMS

    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

    • V. Bharadwaj, D. Ghose and T. G. Robertazzi, Cluster Comput. 6, 7 (2003), DOI: 10.1023/A:1020958815308. CrossrefGoogle Scholar
    • M. Cierniak, M. J. Zaki and W. Li, Computer J. 40, 356 (1997), DOI: 10.1093/comjnl/40.6.356. Crossref, ISIGoogle 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
    • A. Lastovetsky and R. Reddy, Int. J. High Perform. Comput. Appl. 21, 76 (2007), DOI: 10.1177/1094342006074864. Crossref, ISIGoogle 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 Scholar
    • S. Ichikawa and S. Yamashita, Static Load Balancing of Parallel PDE Solver for Distributed Computing Environment, PDCS-2000 (2000) pp. 399–405. Google Scholar
    • A. Legrandet al., IEEE T. Parall. Distr. 15, 546 (2004), DOI: 10.1109/TPDS.2004.10. Crossref, ISIGoogle Scholar
    • J. A. Martínezet al., 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 Scholar
    • I. 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 Scholar
    • S. F. Hummelet al., Load-sharing in heterogeneous systems via weighted factoring, SPAA'96 (ACM, 1996) pp. 318–328. Google Scholar
    • R. L. Cariño and I. Banicescu, J. Supercomput. 44, 41 (2008). Crossref, ISIGoogle Scholar
    • G. Cybenko, J. Parallel Distr. Com. 7, 279 (1989), DOI: 10.1016/0743-7315(89)90021-X. Crossref, ISIGoogle Scholar
    • J. M. Bahi, S. Contassot-Vivier and R. Couturier, IEEE T. Parall. Distr. 16, 289 (2005), DOI: 10.1109/TPDS.2005.45. Crossref, ISIGoogle 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
    • M. J. D. Powell, Numerical Methods for Nonlinear Algebraic Equations, eds.  Gordon and  Breach (1970) pp. 87–114. Google Scholar
    • H. Akima, J. ACM 17, 589 (1970), DOI: 10.1145/321607.321609. Crossref, ISIGoogle Scholar
    • M. J. D. Powell, Numerical Methods for Nonlinear Algebraic Equations, eds.  Gordon and  Breach (1970) pp. 115–161. Google Scholar