Publication result detail

Multi-GPU Island-Based Genetic Algorithm Solving the Knapsack Problem

JAROŠ, J.

Original Title

Multi-GPU Island-Based Genetic Algorithm Solving the Knapsack Problem

English Title

Multi-GPU Island-Based Genetic Algorithm Solving the Knapsack Problem

Type

Paper in proceedings (conference paper)

Original Abstract

This paper introduces a novel implementation of the genetic algorithm exploiting a multi-GPU cluster. The proposed implementation employs an island-based genetic algorithm where every GPU evolves a single island. The individuals are treated by CUDA warps enabling to solve large knapsack instances and eliminate undesirable thread divergence. The OpenMPI interface is used to exchange genetic material among different islands and to collect statistical data. The implementation characteristics are investigated on a cluster composed of 14 GPUs and 4 six-core Intel Xeon processors.

English abstract

This paper introduces a novel implementation of the genetic algorithm exploiting a multi-GPU cluster. The proposed implementation employs an island-based genetic algorithm where every GPU evolves a single island. The individuals are treated by CUDA warps enabling to solve large knapsack instances and eliminate undesirable thread divergence. The OpenMPI interface is used to exchange genetic material among different islands and to collect statistical data. The implementation characteristics are investigated on a cluster composed of 14 GPUs and 4 six-core Intel Xeon processors.

Keywords

GPU; CUDA; MPI; GA; island model; knapsack

Key words in English

GPU; CUDA; MPI; GA; island model; knapsack

Authors

JAROŠ, J.

RIV year

2013

Released

11.06.2012

Publisher

Institute of Electrical and Electronics Engineers

Location

CA

ISBN

978-1-4673-1508-1

Book

2012 IEEE Congress on Evolutionary Computation, CEC 2012

Pages from

217

Pages to

224

Pages count

8

URL

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

BibTex

@inproceedings{BUT96925,
  author="Jiří {Jaroš}",
  title="Multi-GPU Island-Based Genetic Algorithm Solving the Knapsack Problem",
  booktitle="2012 IEEE Congress on Evolutionary Computation, CEC 2012",
  year="2012",
  pages="217--224",
  publisher="Institute of Electrical and Electronics Engineers",
  address="CA",
  doi="10.1109/CEC.2012.6256131",
  isbn="978-1-4673-1508-1",
  url="https://www.fit.vut.cz/research/publication/9860/"
}

Documents

Multi-GPU Island-Based Genetic Algorithm for Solving the Knapsack Problem