skip to main content
Idioma:

Novel parallel hybrid genetic algorithms on the GPU for the generalized assignment problem

Zhi-Bin, Huang ; Guang-Tao, Fu ; Dan-Yang, Dong ; Chen, Xiao ; Zhe-Lun, Ding ; Zhi-Tao, Dai

The Journal of supercomputing, 2022, Vol.78 (1), p.144-167 [Periódico revisado por pares]

New York: Springer US

Texto completo disponível

Citações Citado por
  • Título:
    Novel parallel hybrid genetic algorithms on the GPU for the generalized assignment problem
  • Autor: Zhi-Bin, Huang ; Guang-Tao, Fu ; Dan-Yang, Dong ; Chen, Xiao ; Zhe-Lun, Ding ; Zhi-Tao, Dai
  • Assuntos: Assignment problem ; Central processing units ; Combinatorial analysis ; Compilers ; Computer architecture ; Computer Science ; CPUs ; Genetic algorithms ; Graphics processing units ; Interpreters ; Operations research ; Optimization ; Parallel programming ; Processor Architectures ; Programming Languages ; Synchronism ; Time synchronization
  • É parte de: The Journal of supercomputing, 2022, Vol.78 (1), p.144-167
  • Descrição: The emergence of GPU-CPU heterogeneous architecture has led to a significant paradigm shift in parallel programming. How to effectively implement Parallel Genetic Algorithm (GA) in these environments has become one of the current hot issues. GA’s calculation and operators are closely related to specific problems, thereby significantly affecting the acceleration method of GA algorithms. The Generalized Assignment Problem (GAP) is a classic NP-hard combinatorial optimization problem. The more widely used genetic algorithms to solve the GAP in the CPU are difficult to be parallelized in a GPU environment due to severe data dependencies. To address this problem, two algorithms suitable for the implementation on the GPU are proposed, namely RPE algorithm and NNE algorithm, which obtain significant performance speedup by alleviating data dependencies and mutually exclusive synchronization overheads. At the same time, considering the new GPU architecture features and programming models, three different granular implementations of parallel genetic algorithms to solve the GAP are proposed, namely GPGA thread , GPGA warpsp and GPGA cgroup , by utilizing the warp-specialization technology and the cooperative group mechanism. GPGA series algorithms obtain better solution quality and very significant performance improvements compared with Serial GA, GTS (the GPU-CPU hybrid implementation of Scatter Search with Tabu lists) and Lagrange Relaxation algorithm on a CPU by solving 16 typical large-scale GAP instances.
  • Editor: New York: Springer US
  • Idioma: Inglês
Voltar para lista de resultados
Ir para página anteriorAnterior Resultado  10 AvançarIr para próxima página

  • Realização: ABCD-USP USP   Logos de Redes Sociais: Freepik

Buscando em bases de dados remotas. Favor aguardar.