Department of Computer Systems

Papers

Pospíchal Petr, Schwarz Josef, Jaroš Jiří: Parallel Genetic Algorithm Solving 0/1 Knapsack Problem Running on the GPU, In: 16th International Conference on Soft Computing MENDEL 2010, Brno, CZ, VUT v Brně, 2010, p. 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:

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íchal and Josef Schwarz and Jiří Jaroš},
   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}
}

Nacházíte se v sekcích

Main menu

Department of Computer Systems

Papers