GPU Implementation of the Branch and Bound method for knapsack problems - LAAS-Réseaux et Communications Accéder directement au contenu
Communication Dans Un Congrès Année : 2012

GPU Implementation of the Branch and Bound method for knapsack problems

Résumé

In this paper, we propose an efficient implementation of the branch and bound method for knapsack problems on a CPU-GPU system via CUDA. Branch and bound computations can be carried out either on the CPU or on a GPU according to the size of the branch and bound list. A better management of GPUs memories, less GPU-CPU communications and better synchronization between GPU threads are proposed in this new implementation in order to increase efficiency. Indeed, a series of computational results is displayed and analyzed showing a substantial speedup on a Tesla C2050 GPU.
Fichier principal
Vignette du fichier
4676b763.pdf (754.07 Ko) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte
Loading...

Dates et versions

hal-01149777 , version 1 (13-05-2015)

Identifiants

Citer

Didier El Baz, Mohamed Esseghir Lalami. GPU Implementation of the Branch and Bound method for knapsack problems. 2012 IEEE 26th International Parallel and Distributed Processing Symposium Workshops & PhD Forum, May 2012, Shanghai, China. pp.1763 - 1771, ⟨10.1109/IPDPSW.2012.219⟩. ⟨hal-01149777⟩
119 Consultations
831 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More