Publication Details

Solving the Multidimensional Knapsack Problem using a CUDA Accelerated PSO

ZÁŇ Drahoslav and JAROŠ Jiří. Solving Multidimensional Knapsack Problem using CUDA Accelerated PSO. In: Proceedings of the 2014 IEEE Congress on Evolutionary Computation, CEC 2014. Beijing: IEEE Computational Intelligence Society, 2014, pp. 2933-2939. ISBN 978-1-4799-1488-3.
Czech title
Řešení Multidimenzionálního Knapsack Problému pomocí CUDA akcelerovaného PSO
Type
conference paper
Language
english
Authors
Keywords

Particle Swarm Optimization, Multidimensional Knapsack Problem,
GPU, CUDA, Performance comparison.

Abstract

This paper addresses the possibility of solving the MKP using a GPU accelerated Particle Swarm Optimisation (PSO). The goal is to evaluate the attainable performance benefit when using a highly optimised GPU code instead of an efficient multi-core CPU implementation while preserving the quality of the search process.

Annotation

The Multidimensional Knapsack Problem (MKP) represents an important model having numerous applications in combinatorial optimisation, decision-making and scheduling processes, cryptography, etc. Although the MKP is easy to define and implement, the time complexity of finding a good solution grows exponentially with the problem size. Therefore, novel software techniques and hardware platforms are being developed and employed to reduce the computation time. This paper addresses the possibility of solving the MKP using a GPU accelerated Particle Swarm Optimisation (PSO). The goal is to evaluate the attainable performance benefit when using a highly optimised GPU code instead of an efficient multi-core CPU implementation while preserving the quality of the search process. The paper shows that a single Nvidia GTX 580 graphics card can outperform a quad-core CPU by a factor of 5 to 10, depending on the problem size. As both implementations are memory bound, these speed-ups directly correspond to the memory bandwidth ratio between the investigated GPU and CPU.

Published
2014
Pages
2933-2939
Proceedings
Proceedings of the 2014 IEEE Congress on Evolutionary Computation, CEC 2014
Conference
IEEE Congress on Evolutionary Computation 2014, Beijing, CN
ISBN
978-1-4799-1488-3
Publisher
IEEE Computational Intelligence Society
Place
Beijing, CN
DOI
UT WoS
000356684604027
EID Scopus
BibTeX
@INPROCEEDINGS{FITPUB10480,
   author = "Drahoslav Z\'{a}\v{n} and Ji\v{r}\'{i} Jaro\v{s}",
   title = "Solving the Multidimensional Knapsack Problem using a CUDA Accelerated PSO",
   pages = "2933--2939",
   booktitle = "Proceedings of the 2014 IEEE Congress on Evolutionary Computation, CEC 2014",
   year = 2014,
   location = "Beijing, CN",
   publisher = "IEEE Computational Intelligence Society",
   ISBN = "978-1-4799-1488-3",
   doi = "10.1109/CEC.2014.6900534",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/10480"
}
Files
Back to top