Detail publikačního výsledku

Parallel Genetic Algorithm Solving 0/1 Knapsack Problem Running on the GPU

POSPÍCHAL, P.; SCHWARZ, J.; JAROŠ, J.

Originální název

Parallel Genetic Algorithm Solving 0/1 Knapsack Problem Running on the GPU

Anglický název

Parallel Genetic Algorithm Solving 0/1 Knapsack Problem Running on the GPU

Druh

Stať ve sborníku v databázi WoS či Scopus

Originální abstrakt

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.

Anglický abstrakt

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.

Klíčová slova

massively parallel, genetic algorithm, island model, CUDA, GPU, 0/1 Knapsack problem

Klíčová slova v angličtině

massively parallel, genetic algorithm, island model, CUDA, GPU, 0/1 Knapsack problem

Autoři

POSPÍCHAL, P.; SCHWARZ, J.; JAROŠ, J.

Rok RIV

2012

Vydáno

13.07.2010

Nakladatel

Brno University of Technology

Místo

Brno

ISBN

978-80-214-4120-0

Kniha

16th International Conference on Soft Computing MENDEL 2010

Strany od

64

Strany do

70

Strany počet

7

URL

https://www.fit.vut.cz/research/publication/9253/

BibTex

@inproceedings{BUT34660,
  author="Petr {Pospíchal} and Josef {Schwarz} and Jiří {Jaroš}",
  title="Parallel Genetic Algorithm Solving 0/1 Knapsack Problem Running on the GPU",
  booktitle="16th International Conference on Soft Computing MENDEL 2010",
  year="2010",
  pages="64--70",
  publisher="Brno University of Technology",
  address="Brno",
  isbn="978-80-214-4120-0",
  url="https://www.fit.vut.cz/research/publication/9253/"
}

Dokumenty

mendel2010