Ing. Jiří Jaroš, Ph.D.

ZÁŇ Drahoslav a JAROŠ Jiří. Solving the Multidimensional Knapsack Problem using a CUDA Accelerated PSO. In: 2014 IEEE Congress on Evolutionary Computation. Beijing: IEEE Computational Intelligence Society, 2014, s. 2933-2939. ISBN 978-1-4799-1488-3.
Jazyk publikace:angličtina
Název publikace:Solving the Multidimensional Knapsack Problem using a CUDA Accelerated PSO
Název (cs):Řešení Multidimenzionálního Knapsack Problému pomocí CUDA akcelerovaného PSO
Strany:2933-2939
Sborník:2014 IEEE Congress on Evolutionary Computation
Konference:IEEE Congress on Evolutionary Computation 2014
Místo vydání:Beijing, CN
Rok:2014
ISBN:978-1-4799-1488-3
Vydavatel:IEEE Computational Intelligence Society
Soubory: 
+Typ Jméno Název Vel. Poslední změna
iconE-14647.pdf259 KB2014-07-28 14:43:27
^ Vybrat vše
S vybranými:
Klíčová slova
Particle Swarm Optimization, Multidimensional Knapsack Problem,
GPU, CUDA, Performance comparison.
Anotace
Príspevok poukazauje na možnosť využitia GPU ako platformy na riešenie MKP problému pomocou algoritmu PSO. Cieľom je vyhodnotiť dosiahnutý výkon plne optimalizovaného GPU kódu, oproti efektívnemu riešeniu na viacjadrovom CPU, pričom kvalita riešenia zostane zachovaná.
Abstrakt
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.cs?id=10480}
}

Vaše IPv4 adresa: 54.196.33.246
Přepnout na IPv6 spojení

DNSSEC [dnssec]