Abstract
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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Fung, W., Sham, I., Yuan, G., Aamodt, T.: Dynamic warp formation and scheduling for efficient gpu control flow. In: MICRO 2007: Proceedings of the 40th Annual IEEE/ACM International Symposium on Microarchitecture, Washington, DC, USA, pp. 407–420 (2007)
Gendron, B., Crainic, T.G.: Parallel Branch and Bound Algorithms: Survey and Synthesis. Operations Research 42, 1042–1066 (1994)
Han, T., Abdelrahman, T.S.: Reducing branch divergence in GPU programs. In: Proceedings of the Fourth Workshop on General Purpose Processing on Graphics Processing Units (GPGPU-4), Article 3, 8 pages. ACM, New York (2011)
Jang, B., et al.: Exploiting memory access patterns to improve memory performance in data-parallel architectures. IEEE Trans. on Parallel and Distributed Systems 22(1), 105–118 (2011)
Johnson, S.M.: Optimal two and three-stage production schedules with setup times included. Naval Research Logistis Quarterly 1, 61–68 (1954)
Lenstra, J.K., Lageweg, B.J., Rinnooy Kan, A.H.G.: A General bounding scheme for the permutation Flow-shop problem. Operations Research 26(1), 53–67 (1978)
Melab, N.: Contributions à la résolution de problèmes d’optimisation combinatoire sur grilles de calcul. HDR thesis, LIFL, USTL (Novembre 2005)
NVIDIA CUDA C Programming Best Practices Guide, http://developer.download.nvidia.com/compute/cuda/2_3/toolkit/docs/NVIDIA_CUDA_BestPracticesGuide_2.3.pdf
Ryoo, S., Rodrigues, C.I., Stone, S.S., Stratton, J.A., Ueng, S.-Z., Baghsorkhi, S.S., Hwu, W.W.: Program optimization carving for gpu computing. J. Parallel Distributed Computing 68(10), 1389–1401 (2008)
Taillard, E.: Benchmarks for basic scheduling problems. European Journal of European Research 23, 661–673 (1993)
Zhang, E.Z., Jiang, Y., Guo, Z., Shen, X.: Streamlining GPU applications on the fly: thread divergence elimination through runtime thread-data remapping. In: Proceedings of the 24th ACM International Conference on Supercomputing (ICS 2010), pp. 115–126. ACM, New York (2010)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chakroun, I., Bendjoudi, A., Melab, N. (2012). Reducing Thread Divergence in GPU-Based B&B Applied to the Flow-Shop Problem. In: Wyrzykowski, R., Dongarra, J., Karczewski, K., Waśniewski, J. (eds) Parallel Processing and Applied Mathematics. PPAM 2011. Lecture Notes in Computer Science, vol 7203. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-31464-3_57
Download citation
DOI: https://doi.org/10.1007/978-3-642-31464-3_57
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-31463-6
Online ISBN: 978-3-642-31464-3
eBook Packages: Computer ScienceComputer Science (R0)