A Lightweight Island Model for the Genetic Algorithm over GPGPU

Authors

  • Mohammad Alraslan Idlib University, Faculty of Informatics Engineering, Department of Software Engineering, Idlib, Syria https://orcid.org/0000-0002-9973-4164
  • Ahmad H. AlKurdi Idlib University, Faculty of Informatics Engineering, Department of Software Engineering, Idlib, Syria

DOI:

https://doi.org/10.32985/ijeces.14.7.3

Keywords:

GPGPU, Speed up, TSP, Island Model, Genetic algorithm

Abstract

This paper presents a parallel approach of the genetic algorithm (GA) over the Graphical Processing Unit (GPU) to solve the Traveling Salesman Problem (TSP). Since the earlier studies did not focus on implementing the island model in a persistent way, this paper introduces an approach, named Lightweight Island Model (LIM), that aims to implement the concept of persistent threads in the island model of the genetic algorithm. For that, we present the implementation details to convert the traditional island model, which is separated into multiple kernels, into a computing paradigm based on a persistent kernel. Many synchronization techniques, including cooperative groups and implicit synchronization, are discussed to reduce the CPU-GPU interaction that existed in the traditional island model. A new parallelization strategy is presented for distributing the work among live threads during the selection and crossover steps. The GPU configurations that lead to the best possible performance are also determined. The introduced approach will be compared, in terms of speedup and solution quality, with the traditional island model (TIM) as well as with related works that concentrated on suggesting a lighter version of the master-slave model, including switching among kernels (SAK) and scheduled light kernel (SLK) approaches. The results show that the new approach can increase the speed-up to 27x over serial CPU, 4.5x over the traditional island model, and up to 1.5–2x over SAK and SLK approaches.

Author Biographies

Mohammad Alraslan, Idlib University, Faculty of Informatics Engineering, Department of Software Engineering, Idlib, Syria

 

 

 

Ahmad H. AlKurdi, Idlib University, Faculty of Informatics Engineering, Department of Software Engineering, Idlib, Syria

 

 

 

Downloads

Published

2023-09-05

How to Cite

[1]
M. Alraslan and A. H. . AlKurdi, “A Lightweight Island Model for the Genetic Algorithm over GPGPU”, IJECES, vol. 14, no. 7, pp. 753-763, Sep. 2023.

Issue

Section

Original Scientific Papers