×

zbMATH — the first resource for mathematics

Solving knapsack problems on GPU. (English) Zbl 1251.90014
Summary: A parallel implementation via CUDA of the dynamic programming method for the knapsack problem on NVIDIA GPU is presented. A GTX 260 card with 192 cores (1.4 GHz) is 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.0 GHz. The results show a speedup factor of 26 for large size problems. Furthermore, in order to limit the communication between the CPU and the GPU, a compression technique is presented which decreases significantly the memory occupancy.

MSC:
90-08 Computational methods for problems pertaining to operations research and mathematical programming
90C90 Applications of mathematical programming
90C39 Dynamic programming
90C27 Combinatorial optimization
Software:
CUDA; Knapsack
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] NVIDIA, Cuda 2.0 programming guide, \(\langle\)http://developer.download.nvidia.com/compute/cuda/2_0/docs/NVIDIA_CUDA_Programming_Guide_2.0.pdf〉; 2009.
[2] Boyer, V.; El Baz, D.; Elkihel, M., Heuristics for the 0-1 multidimensional knapsack problem, European journal of operational research, 199, 3, 658-664, (2009) · Zbl 1176.90657
[3] Boyer, V.; El Baz, D.; Elkihel, M., Solution of multidimensional knapsack problems via cooperation of dynamic programming and branch and bound, European journal of industrial engineering, 4, 4, 434-449, (2010)
[4] Lalami M, Elkihel M, El Baz D, Boyer V. A procedure-based heuristic for 0-1 multiple knapsack problems, LAAS report 10035, to appear. · Zbl 1254.90194
[5] Boyer V, El Baz D, Elkihel M. A dynamic programming method with lists for the knapsack sharing problem. Computers & Industrial Engineering, in press, doi:10.1016/j.cie.2010.10.015 · Zbl 1176.90657
[6] El Baz D, et al. Parallélisation de méthodes de programmation entière sur GPU, Congrès de la Société Française de Recherche Opérationnelle et d’Aide à la Décision, ROADEF’2010, Toulouse, France; 2010.
[7] Lalami M, Boyer V, El Baz D. Efficient implementation of the simplex method on a CPU-GPU system. In: 25th symposium IEEE IPDPSW, Anchorage, USA; 2011.
[8] Boyer V, El Baz D, Elkihel M. Programmation dynamique dense sur GPU, Congrès de la Société Française de Recherche Opérationnelle et d’Aide à la Décision, ROADEF’2010, LAAS report 09740, Toulouse, France; 2009.
[9] Lou, D.C.; Chang, C.C., A parallel two-List algorithm for the knapsack problem, Parallel computing, 22, 1985-1996, (1997) · Zbl 0906.68079
[10] Gerash, T.E.; Wang, P.Y., A survey of parallel algorithms for one-dimensional integer knapsack problems, Infor, 32, 3, 163-186, (1993)
[11] Kindervater, G.A.P.; Trienekens, H.W.J.M., An introduction to parallelism in combinatorial optimization, Parallel computers and computations, 33, 65-81, (1988) · Zbl 0631.90052
[12] Lin, J.; Storer, J.A., Processor-efficient algorithms for the knapsack problem, Journal of parallel and distributed computing, 13, 3, 332-337, (1991)
[13] Ulm D. Dynamic programming implementations on SIMD machines—0/1 knapsack problem. M.S. Project, George Mason University; 1991.
[14] El Baz, D.; Elkihel, M., Load balancing methods and parallel dynamic programming algorithm using dominance technique applied to the 0-1 knapsack problem, Journal of parallel and distributed computing, 65, 74-84, (2005) · Zbl 1080.68739
[15] Elkihel M, El Baz D. Load balancing in a parallel dynamic programming multi-method applied to the 0-1 knapsack problem. In: 14th international conference on parallel, distributed and networked-based processing, PDP 2006, Montbéliard, France; 2006.
[16] Cosnard, M.; Ferreira, A.G.; Herbelin, H., The two List algorithm for the knapsack problem on a FPS T20, Parallel computing, 9, 385-388, (1989) · Zbl 0669.65051
[17] Kellerer, H.; Pferschy, U.; Pisinger, D., Knapsack problems, (2004), Springer · Zbl 1103.90003
[18] Martello, S.; Pisinger, D.; Toth, P., New trends in exact algorithms for the 0-1 knapsack problem, European journal of operational research, 123, 325-332, (2000) · Zbl 0961.90090
[19] Martello, S.; Toth, P., Knapsack problems—algorithms and computer implementations, (1990), Wiley & Sons · Zbl 0708.68002
[20] Bellman, R., Dynamic programming, (1957), Princeton University Press · Zbl 0077.13605
[21] Toth, P., Dynamic programming algorithm for the zero – one knapsack problem, Computing, 25, 29-45, (1980) · Zbl 0431.90076
[22] Knapsack problems benchmark, \(\langle\)http://www.laas.fr/laas09/cda/23-31300-knapsack-problems.php〉.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.