Conference paper

ZÁŇ Drahoslav and JAROŠ Jiří. Solving Multidimensional Knapsack Problem using CUDA Accelerated PSO. In: 2014 IEEE Congress on Evolutionary Computation. Beijing: IEEE Computational Intelligence Society, 2014, pp. 2933-2939. ISBN 978-1-4799-1488-3.
Publication language:english
Original title:Solving the Multidimensional Knapsack Problem using a CUDA Accelerated PSO
Title (cs):Řešení Multidimenzionálního Knapsack Problému pomocí CUDA akcelerovaného PSO
Pages:2933-2939
Proceedings:2014 IEEE Congress on Evolutionary Computation
Conference:IEEE Congress on Evolutionary Computation 2014
Place:Beijing, CN
Year:2014
ISBN:978-1-4799-1488-3
Publisher:IEEE Computational Intelligence Society
Files: 
+Type Name Title Size Last modified
iconE-14647.pdf259 KB2014-07-28 14:43:27
^ Select all
With selected:
Keywords
Particle Swarm Optimization, Multidimensional Knapsack Problem,
GPU, CUDA, Performance comparison.
Annotation
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.
Abstract
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.

BibTeX:
@INPROCEEDINGS{
   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 = {2014 IEEE Congress on Evolutionary Computation},
   year = {2014},
   location = {Beijing, CN},
   publisher = {IEEE Computational Intelligence Society},
   ISBN = {978-1-4799-1488-3},
   language = {english},
   url = {http://www.fit.vutbr.cz/research/view_pub.php?id=10480}
}

Your IPv4 address: 54.80.209.254
Switch to IPv6 connection

DNSSEC [dnssec]