Reducing Thread Divergence in GPU-Based B&B Applied to the Flow-Shop Problem
| dc.contributor.author | Chakroun, Imen | |
| dc.contributor.author | Bendjoudi, Ahcène | |
| dc.contributor.author | Melab, Nouredine | |
| dc.date.accessioned | 2013-11-28T08:57:30Z | |
| dc.date.available | 2013-11-28T08:57:30Z | |
| dc.date.issued | 2012 | |
| dc.description.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. | fr_FR |
| dc.identifier.doi | 10.1007/978-3-642-31464-3_57 | |
| dc.identifier.e-isbn | 978-3-642-31464-3 | |
| dc.identifier.isbn | 978-3-642-31463-6 | |
| dc.identifier.uri | http://dl.cerist.dz/handle/CERIST/390 | |
| dc.publisher | Springer Berlin Heidelberg | fr_FR |
| dc.relation.ispartof | Parallel Processing and Applied Mathematics : 9th International Conference, PPAM 2011, Torun, Poland, September 11-14, 2011. Revised Selected Papers, Part I | |
| dc.relation.ispartofseries | Parallel Processing and Applied Mathematics : 9th International Conference, PPAM 2011, Torun, Poland, September 11-14, 2011. Revised Selected Papers, Part I | fr_FR |
| dc.relation.place | Berlin | fr_FR |
| dc.rights.holder | Springer-Verlag Berlin Heidelberg | fr_FR |
| dc.subject | Branch and Bound | fr_FR |
| dc.subject | Data Parallelism | fr_FR |
| dc.subject | GPU Computing | fr_FR |
| dc.subject | Thread Divergence | fr_FR |
| dc.subject | Flow-shop Scheduling | fr_FR |
| dc.title | Reducing Thread Divergence in GPU-Based B&B Applied to the Flow-Shop Problem | fr_FR |
| dc.type | Book Chapter |