Multi-GPU island-based genetic algorithm for solving the knapsack problem

Author

Jaros, Jiri

Author_Institution

ANU Coll. of Eng. & Comput. Sci., Australian Nat. Univ., Canberra, ACT, Australia

fYear

2012

fDate

10-15 June 2012

Firstpage

1

Lastpage

8

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 processed by CUDA warps, which enables the solution of large knapsack instances and eliminates undesirable thread divergence. The MPI interface is used to exchange genetic material among isolated islands and collect statistical data. The characteristics of the proposed GAs are investigated on a two-node cluster composed of 14 Fermi GPUs and 4 six-core Intel Xeon processors. The overall GPU performance of the proposed GA reaches 5.67 TFLOPS.

Keywords

genetic algorithms; graphics processing units; knapsack problems; message passing; multiprocessing systems; CUDA warps; Fermi GPU; MPI interface; genetic material; knapsack problem; multiGPU cluster; multiGPU island-based genetic algorithm; six-core Intel Xeon processors; thread divergence; two-node cluster; Biological cells; Genetic algorithms; Genetics; Graphics processing unit; Instruction sets; Kernel; Layout; CUDA; GA; GPU; MPI; island model; knapsack;

fLanguage

English

Publisher

ieee

Conference_Titel

Evolutionary Computation (CEC), 2012 IEEE Congress on

Conference_Location

Brisbane, QLD

Print_ISBN

978-1-4673-1510-4

Electronic_ISBN

978-1-4673-1508-1

Type

conf

DOI

10.1109/CEC.2012.6256131

Filename

6256131