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.
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: 30 May 2011 *