Parallel evolutionary algorithms on consumer-level graphics processing unit

Tien Tsin WONG, Man Leung WONG

Research output: Book Chapters | Papers in Conference ProceedingsBook ChapterResearchpeer-review

18 Citations (Scopus)

Abstract

In this research, we have implemented a parallel EP on consumer-level graphics processing units and proposed indirect indexing and many optimization skills to achieve maximal efficiency. The parallel EP is a hybrid of masterslave and fine-grained models. Competition and selection are performed by CPU (i.e. the master) while fitness evaluation, mutation, and reproduction are performed by GPU which is essentially a massively parallel machine with shared memory. Unlike other fine-grained parallel computers such as Maspar, GPU allows processors to communicate with, not only nearby processors, but also any other processors. Hence more flexible fine-grained EAs can be implemented on GPU. We have done experiments to compare our parallel EP on GPU and an ordinary EP on CPU. It is found that the speed-up factor of our parallel EP ranges from 1.25 to 5.02, when the population size is large enough. Moreover, there is a sub-linear relation between the population size and the execution time. Thus, our parallel EP will be very useful for solving difficult problems that require huge population sizes. For future work, we plan to implement a parallel genetic algorithm on GPU and compare it with the approach reported in this paper.
Original languageEnglish
Title of host publicationParallel Evolutionary Computations
PublisherSpringer-Verlag GmbH and Co. KG
Pages133-155
Number of pages23
ISBN (Print)9783540328377
DOIs
Publication statusPublished - 1 Jan 2006

Fingerprint

Parallel algorithms
Evolutionary algorithms
Program processors
Graphics processing unit
Genetic algorithms
Data storage equipment
Experiments

Cite this

WONG, T. T., & WONG, M. L. (2006). Parallel evolutionary algorithms on consumer-level graphics processing unit. In Parallel Evolutionary Computations (pp. 133-155). Springer-Verlag GmbH and Co. KG. https://doi.org/10.1007/3-540-32839-4_7
WONG, Tien Tsin ; WONG, Man Leung. / Parallel evolutionary algorithms on consumer-level graphics processing unit. Parallel Evolutionary Computations. Springer-Verlag GmbH and Co. KG, 2006. pp. 133-155
@inbook{7a8f365c6b4443ac877fbb357b7a6be3,
title = "Parallel evolutionary algorithms on consumer-level graphics processing unit",
abstract = "In this research, we have implemented a parallel EP on consumer-level graphics processing units and proposed indirect indexing and many optimization skills to achieve maximal efficiency. The parallel EP is a hybrid of masterslave and fine-grained models. Competition and selection are performed by CPU (i.e. the master) while fitness evaluation, mutation, and reproduction are performed by GPU which is essentially a massively parallel machine with shared memory. Unlike other fine-grained parallel computers such as Maspar, GPU allows processors to communicate with, not only nearby processors, but also any other processors. Hence more flexible fine-grained EAs can be implemented on GPU. We have done experiments to compare our parallel EP on GPU and an ordinary EP on CPU. It is found that the speed-up factor of our parallel EP ranges from 1.25 to 5.02, when the population size is large enough. Moreover, there is a sub-linear relation between the population size and the execution time. Thus, our parallel EP will be very useful for solving difficult problems that require huge population sizes. For future work, we plan to implement a parallel genetic algorithm on GPU and compare it with the approach reported in this paper.",
author = "WONG, {Tien Tsin} and WONG, {Man Leung}",
year = "2006",
month = "1",
day = "1",
doi = "10.1007/3-540-32839-4_7",
language = "English",
isbn = "9783540328377",
pages = "133--155",
booktitle = "Parallel Evolutionary Computations",
publisher = "Springer-Verlag GmbH and Co. KG",
address = "Germany",

}

WONG, TT & WONG, ML 2006, Parallel evolutionary algorithms on consumer-level graphics processing unit. in Parallel Evolutionary Computations. Springer-Verlag GmbH and Co. KG, pp. 133-155. https://doi.org/10.1007/3-540-32839-4_7

Parallel evolutionary algorithms on consumer-level graphics processing unit. / WONG, Tien Tsin; WONG, Man Leung.

Parallel Evolutionary Computations. Springer-Verlag GmbH and Co. KG, 2006. p. 133-155.

Research output: Book Chapters | Papers in Conference ProceedingsBook ChapterResearchpeer-review

TY - CHAP

T1 - Parallel evolutionary algorithms on consumer-level graphics processing unit

AU - WONG, Tien Tsin

AU - WONG, Man Leung

PY - 2006/1/1

Y1 - 2006/1/1

N2 - In this research, we have implemented a parallel EP on consumer-level graphics processing units and proposed indirect indexing and many optimization skills to achieve maximal efficiency. The parallel EP is a hybrid of masterslave and fine-grained models. Competition and selection are performed by CPU (i.e. the master) while fitness evaluation, mutation, and reproduction are performed by GPU which is essentially a massively parallel machine with shared memory. Unlike other fine-grained parallel computers such as Maspar, GPU allows processors to communicate with, not only nearby processors, but also any other processors. Hence more flexible fine-grained EAs can be implemented on GPU. We have done experiments to compare our parallel EP on GPU and an ordinary EP on CPU. It is found that the speed-up factor of our parallel EP ranges from 1.25 to 5.02, when the population size is large enough. Moreover, there is a sub-linear relation between the population size and the execution time. Thus, our parallel EP will be very useful for solving difficult problems that require huge population sizes. For future work, we plan to implement a parallel genetic algorithm on GPU and compare it with the approach reported in this paper.

AB - In this research, we have implemented a parallel EP on consumer-level graphics processing units and proposed indirect indexing and many optimization skills to achieve maximal efficiency. The parallel EP is a hybrid of masterslave and fine-grained models. Competition and selection are performed by CPU (i.e. the master) while fitness evaluation, mutation, and reproduction are performed by GPU which is essentially a massively parallel machine with shared memory. Unlike other fine-grained parallel computers such as Maspar, GPU allows processors to communicate with, not only nearby processors, but also any other processors. Hence more flexible fine-grained EAs can be implemented on GPU. We have done experiments to compare our parallel EP on GPU and an ordinary EP on CPU. It is found that the speed-up factor of our parallel EP ranges from 1.25 to 5.02, when the population size is large enough. Moreover, there is a sub-linear relation between the population size and the execution time. Thus, our parallel EP will be very useful for solving difficult problems that require huge population sizes. For future work, we plan to implement a parallel genetic algorithm on GPU and compare it with the approach reported in this paper.

UR - http://commons.ln.edu.hk/sw_master/2354

U2 - 10.1007/3-540-32839-4_7

DO - 10.1007/3-540-32839-4_7

M3 - Book Chapter

SN - 9783540328377

SP - 133

EP - 155

BT - Parallel Evolutionary Computations

PB - Springer-Verlag GmbH and Co. KG

ER -

WONG TT, WONG ML. Parallel evolutionary algorithms on consumer-level graphics processing unit. In Parallel Evolutionary Computations. Springer-Verlag GmbH and Co. KG. 2006. p. 133-155 https://doi.org/10.1007/3-540-32839-4_7