Vincent Boyer : December 17, 2009

Solving knapsack problems on GPU

Vincent Boyer, UPS/LAAS

Thursday, December 17, 10:00 a.m. in the CERFACS conference room

Abstract:

Since a few years, graphics card manufacturers have developed tools to use their products for high performance computing. Graphics Processing Units, or GPUs, are high-performance many-core processors. Using their performances for solving combinatorial optimization problems, like knapsack problems, represents a great challenge as they can accelerate the resolution of these NP-hard problems.

Many efficient exact algorithms exist for solving knapsack problems. It follows from the constraints that result from GPU architecture that dense dynamic programming is very attractive in this context. Indeed, it consists in building succesively tables that matches, in particular, the fact that memory access have to be coalesced in order to reduce the time requested for the read/write operations.

A NVIDIA GTX 260 (192 cores, 1.4GHz) was used for computational experiences and results obtained with the parallel code are compared to the sequential one on a CPU with an Intel Xeon 3.0GHz. The results show a speed up of 15 in average and permit one to solve large size problems within a reasonnable processing time.