Solving knapsack problems on GPU

Vincent Boyer (1) , Didier El Baz (1) , Moussa Elkihel (1)

1 LAAS-CDA - Équipe Calcul Distribué et Asynchronisme

In this article, we propose a parallel implementation of the dynamic programming method for the knapsack problem on NVIDIA GPU. A GTX 260 (192 cores, 1.4GHz) was used for computational tests and processing times obtained with the parallel code are compared to the sequential one on a CPU with an Intel Xeon 3.0GHz. The results show a speedup up to 26 and permit one to solve large size problems within a reasonable processing time. Furthermore, in order to limit the communication between the CPU and the GPU, a compression technique is presented which decreases significantly the memory occupancy.

Mots clés: Knapsack problems; Dense dynamic programming; Parallel computing; GPU computing

Domaines: Informatique [cs]; Calcul parallèle, distribué et partagé [cs.DC]

Vincent Boyer, Didier El Baz, Moussa Elkihel. Solving knapsack problems on GPU. Computers and Operations Research, 2012, 39 (1), pp.42-47. ⟨10.1016/j.cor.2011.03.014⟩. ⟨hal-01152223⟩