Conference paper

POSPÍCHAL Petr, SCHWARZ Josef and JAROŠ Jiří. Parallel Genetic Algorithm Solving 0/1 Knapsack Problem Running on the GPU. In: 16th International Conference on Soft Computing MENDEL 2010. Brno: Brno University of Technology, 2010, pp. 64-70. ISBN 978-80-214-4120-0.
Publication language:english
Original title:Parallel Genetic Algorithm Solving 0/1 Knapsack Problem Running on the GPU
Title (cs):Paralelní genetický algoritmus řešící 0/1 Knapsack problém běžící na GPU
Pages:64-70
Proceedings:16th International Conference on Soft Computing MENDEL 2010
Conference:16th International Mendel Conference on Soft Computing
Place:Brno, CZ
Year:2010
ISBN:978-80-214-4120-0
Publisher:Brno University of Technology
Files: 
+Type Name Title Size +Last modified
iconmendel2010.pdf597 KB2010-07-13 14:41:58
^ Select all
With selected:
Keywords
massively parallel, genetic algorithm, island model, CUDA, GPU, 0/1 Knapsack problem
Annotation
In this work, we show that consumer-level $100 GPU can be used to significantly speed-up optimization
of 0/1 Knapsack problem. We identify strong and weak points of GPU architecture and propose our parallel
genetic algorithm model implemented in CUDA running entirely on the GPU. We show that GPU must be utilized
for sufficiently long time in order to obtain reasonable program speedup. Then we compare results quality and
speed of our model with single-threaded CPU code implemented using Galib. Peak speedup of GPU GA execution
performance is 1340x resp. 134x for 4-bit resp. 40-bit problem instances while maintaining reasonable results
quality.
BibTeX:
@INPROCEEDINGS{
   author = {Petr Posp{\'{i}}chal and Josef Schwarz and Ji{\v{r}}{\'{i}}
	Jaro{\v{s}}},
   title = {Parallel Genetic Algorithm Solving 0/1 Knapsack Problem
	Running on the GPU},
   pages = {64--70},
   booktitle = {16th International Conference on Soft Computing MENDEL 2010},
   year = {2010},
   location = {Brno, CZ},
   publisher = {Brno University of Technology},
   ISBN = {978-80-214-4120-0},
   language = {english},
   url = {http://www.fit.vutbr.cz/research/view_pub.php?id=9253}
}

Your IPv4 address: 54.162.107.122
Switch to IPv6 connection

DNSSEC [dnssec]