Title: Efficient hybrid parallelisation of tiled algorithms on SMP clusters

Authors: Nikolaos Drosinos, Nectarios Koziris

Addresses: School of Electrical and Computer Engineering, Computing Systems Laboratory, National Technical University of Athens, Iroon Polytexneioy 9, 15780 Zografou Campus, Athens, Greece. ' School of Electrical and Computer Engineering, Computing Systems Laboratory, National Technical University of Athens, Iroon Polytexneioy 9, 15780 Zografou Campus, Athens, Greece

Abstract: This paper emphasises on load balancing issues associated with hybrid parallelisation of tiled algorithms onto SMP clusters. The intrinsic load imbalance in hybrid parallelisation derives from the fact that message passing libraries often provide limited multi-threading support, thus allowing only the master thread to perform inter-node message passing communication. In order to mitigate this effect, we propose a generic method for the application of load balancing on the coarse-grain hybrid model for the appropriate load distribution among the working threads. We investigate both static and dynamic load balancing, and experimentally evaluate three balancing variations against kernel benchmarks.

Keywords: nested loops; tiling transformation; load balancing; hybrid parallelisation; SMP clusters; MPI; OpenMP; tiled algorithms; load distribution; working threads.

DOI: 10.1504/IJCSE.2009.027003

International Journal of Computational Science and Engineering, 2009 Vol.4 No.2, pp.112 - 126

Published online: 12 Jul 2009 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article