Reducing Thread Divergence in GPU-based B&B Applied to the Flow-shop problem

Imen Chakroun, Ahcene Bendjoudi, Nouredine Melab
Universite Lille 1 CNRS/LIFL, INRIA Lille Nord Europe, Cite scientifique – 59655, Villeneuve d’Ascq cedex – France
HAL preprint hal-00640805, 2011


   title={Reducing Thread Divergence in GPU-based B&B Applied to the Flow-shop problem},

   author={Chakroun, I. and Bendjoudi, A. and Melab, N. and others},



Download Download (PDF)   View View   Source Source   



In this paper, we propose a pioneering work on designing and programming B&B algorithms on GPU. To the best of our knowledge, no contribution has been proposed to raise such challenge. We focus on the parallel evaluation of the bounds for the Flow-shop scheduling problem. To deal with thread divergence caused by the bounding operation, we investigate two software based approaches called thread data reordering and branch refactoring. Experiments reported that parallel evaluation of bounds speeds up execution up to 54.5 times compared to a CPU version.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: