IVM‐based parallel branch‐and‐bound using hierarchical work stealing on multi‐GPU systems

Abstract

Summary Tree‐based exploratory methods, like Branch‐and‐Bound (B&B) algorithms, are highly irregular applications which makes their design and implementation on graphics processing unit (GPU) challenging. In this paper, we present a multi‐GPU B&B algorithm for solving large permutation‐based combinatorial optimization problems. To tackle the problem of the irregular workload, we propose a hierarchical work stealing (WS) strategy that balances the workload inside the GPU and between different GPUs and CPU cores. Our B&B is based on an Integer‐Vector‐Matrix data structure instead of a pool of permutations, and work units exchanged are intervals of factoradics instead of sets of nodes. Two variants of the algorithm, using the same hierarchical WS strategy, are proposed: one for combinatorial optimization problems where the evaluation of nodes is costly and one for fine‐grained problems. The latter variant uses a new hypercube‐based WS strategy and a trigger mechanism to balance the work load inside the GPU. The proposed approach has been extensively experimented using the flowshop scheduling, the n‐queens and the asymmetric travelling salesman problems as test‐cases. The reported results show that the proposed hierarchical WS mechanism is capable of handling fine and coarse‐grained types of workloads efficiently, reaching near‐linear speed‐up on up to four GPUs for a set of ten flowshop instances and large instances of fine‐grained problems. Copyright © 2016 John Wiley & Sons, Ltd.