Dynamic workload balancing deques for branch and bound algorithms in the message passing interface. (1st January 2011)

• Record Type: Journal Article
• Authors: Mór, Stéfano; Maillard, Nicolas
• Is Part Of: International journal of high performance systems architecture. Volume 3:Number 2/3(2011)
• Page Start: 77
• Page End: 86
• Publication Date: 2011-01-01
• Subjects: message passing interface -- MPI -- scheduling -- work-stealing -- WS -- branch and bound -- B&B -- parallel task -- workload -- processes -- dynamic -- online -- unbalance; Computer architecture -- Periodicals; Computer systems -- Periodicals; High performance computing -- Periodicals; 004.205
• DOI: 10.1504/IJHPSA.2011.040461
• Languages: English
• ISSNs: 1751-6528

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.