Title: Dynamic workload balancing deques for branch and bound algorithms in the message passing interface

Authors: Stefano Mor, Nicolas Maillard

Addresses: Informatics Institute, Federal University of Rio Grande do Sul, Av. Bento Goncalves 9500, Porto Alegre, RS, Brazil. ' Informatics Institute, Federal University of Rio Grande do Sul, Av. Bento Goncalves 9500, Porto Alegre, RS, Brazil

Abstract: The message passing interface (MPI) is the standard in message passing parallel computation. MPI does not provide a canonical way to dynamically distribute run-time generated workload evenly across all the participating computer nodes. This paper proposes a MPI library to provide near-optimal dynamical workload balancing over branch and bound (B&B) algorithms; B&B potentially produces huge workload unbalance during a parallel execution. The library, named RaWSDM, provides a double ended queue (deque) data structure on which the programmer may pop, process, and later, pull back some parallel tasks; an underlying efficient system scheduler is responsible for keeping the workload balanced by exchanging elements among all deques. Theoretical bounds are traced and practical experiments are performed with the unlimited knapsack problem. Results show a performance gain up to 80% (best-case scenario) against a pure MPI implementation using round-robin scheduling, with near linear speedup and memory consumption.

Keywords: message passing interface; MPI; scheduling; work stealing; branch and bound; parallel tasks; dynamic workload balancing; workload unbalance; parallel computing; double ended queue; deque data structure.

DOI: 10.1504/IJHPSA.2011.040461

International Journal of High Performance Systems Architecture, 2011 Vol.3 No.2/3, pp.77 - 86

Received: 07 Jul 2010
Accepted: 29 Nov 2010
Published online: 21 Mar 2015 *

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