Parallel B&B Algorithm for Hybrid Multi-core/GPU Architectures
| dc.contributor.author | Bendjoudi, Ahcène | |
| dc.contributor.author | Mehdi, Malika | |
| dc.date.accessioned | 2013-11-19T12:51:45Z | |
| dc.date.available | 2013-11-19T12:51:45Z | |
| dc.date.issued | 2013 | |
| dc.description.abstract | B&B algorithms are well known techniques for exact solving of combinatorial optimization problems. 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.isrn | CERIST-DTISI/RR--13-000000024--dz | fr_FR |
| dc.identifier.uri | http://dl.cerist.dz/handle/CERIST/230 | |
| dc.publisher | CERIST | |
| dc.relation.ispartof | Rapports de recherche internes | |
| dc.relation.ispartofseries | Rapports de recherche internes | |
| dc.relation.place | Alger | |
| 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 for Hybrid Multi-core/GPU Architectures | fr_FR |
| dc.type | Technical Report |