Reducing thread divergence in a GPU-accelerated branch-and-bound algorithm

Simple item page
dc.citation.epage1136
dc.citation.issue8
dc.citation.spage1121
dc.citation.volume25
dc.contributor.authorChakroun, Imen
dc.contributor.authorMezmaz, Mohand
dc.contributor.authorMelab, Nouredine
dc.contributor.authorBendjoudi, Ahcène
dc.date.accessioned2013-06-12T10:13:52Z
dc.date.available2013-06-12T10:13:52Z
dc.date.issued2013
dc.description.abstractIn this paper, we address the design and implementation of GPU-accelerated Branch-and-Bound algorithms (B&B) for solving Flow-shop scheduling optimization problems (FSP). Such applications are CPU-time consuming and highly irregular. On the other hand, GPUs are massively multi-threaded accelerators using the SIMD model at execution. A major issue which raises when executing on GPU a B&B applied to FSP is thread or branch divergence. Such divergence is caused by the lower bound function of FSP which contains many irregular loops and conditional instructions. Our challenge is therefore to revisit the design and implementation of B&B applied to FSP dealing with thread divergence. Extensive experiments of the proposed approach have been carried out on well-known FSP benchmarks using an Nvidia Tesla C2050 GPU card. Compared to a CPU-based execution, accelerations up to ×77.46 are achieved for large problem instances.fr_FR
dc.identifier.urihttp://dl.cerist.dz/handle/CERIST/188
dc.relation.ispartofConcurrency and Computation: Practice and Experience
dc.relation.ispartofseriesConcurrency and Computation: Practice and Experience;25(8)
dc.relation.pages1121-1136fr_FR
dc.rights.holderWileyfr_FR
dc.structureCalcul Pervasif et Mobilefr_FR
dc.subjectGPU computing; Branch-and-bound algorithms; Data parallelism; Thread divergence.fr_FR
dc.titleReducing thread divergence in a GPU-accelerated branch-and-bound algorithmfr_FR
dc.typeArticle
Files
Collections
International Journal Papers