Parallel B&B Algorithm on Hybrid Multicore/GPU Architecture
| dc.citation.volume | 15 | |
| dc.contributor.author | Bendjoudi, Ahcène | |
| dc.contributor.author | Chekini, Mehdi | |
| dc.contributor.author | Gharbi, Makhlouf | |
| dc.contributor.author | Mehdi, Malika | |
| dc.contributor.author | Benatchba, Karima | |
| dc.contributor.author | Sitayeb-Benbouzid, Fatima | |
| dc.contributor.author | Melab, Nouredine | |
| dc.date.accessioned | 2013-09-21T12:25:00Z | |
| dc.date.available | 2013-09-21T12:25:00Z | |
| dc.date.issued | 2013-11-15 | |
| dc.description.abstract | B&B algorithms are well known techniques for exact solving of combinatorial optimization problems (COP). They perform an implicit enumeration of the search space instead of exhaustive one. Based on a pruning technique, they reduce considerably the computation time required to explore the whole search space. Nevertheless, these algorithms remain inefficient when dealing with large combinatorial optimization instances. They are time-intensive and they require a huge computing power to be solved optimally. Nowadays, multi-core-based processors and GPU accelerators are often coupled together to achieve impressive performances. However, classical B&B algorithms must be rethought to deal with their two divergent architectures. In this paper, we propose a new B&B approach exploiting both the multi-core aspect of actual processors and GPU accelerators. The proposed approaches have been executed to solve FSP instances that are well-known combinatorial optimization benchmarks. Real experiments have been carried out on an Intel Xeon 64-bit quad-core processor E5520 coupled to an Nvidia Tesla C2075 GPU device. The results show that our hybrid B&B approach speeds up the execution time up to x123 over the sequential mono-core B&B algorithm. | fr_FR |
| dc.identifier.uri | http://dl.cerist.dz/handle/CERIST/211 | |
| dc.publisher | IEEE | fr_FR |
| dc.relation.ispartof | IEEE International Conference on High Performance Computing and Communications | |
| dc.relation.ispartofseries | IEEE International Conference on High Performance Computing and Communications;15 | |
| dc.relation.place | Zhangjiajie, China | fr_FR |
| dc.rights.holder | IEEE | fr_FR |
| dc.structure | Calcul Pervasif et Mobile | fr_FR |
| dc.subject | Parallel B&B Algorithms | fr_FR |
| dc.subject | GPU computing | fr_FR |
| dc.subject | Multicore architectures | fr_FR |
| dc.subject | Flowshop problem | fr_FR |
| dc.title | Parallel B&B Algorithm on Hybrid Multicore/GPU Architecture | fr_FR |
| dc.type | Conference paper |