high performance computing on graphics processing units: hgpu.org

Real-world optimization problems are very complex and NP-hard. The modeling of such problems is in constant evolution in term of constraints and objectives and their resolution is expensive in computation time. With all this change, even metaheuristics, well known for their efficiency, begin to be overtaken by data explosion. Recently, Thanks to the publication of languages as OpenCL and CUDA, the development of parallel metaheuristics on GPU platform has a growing interest. Throughout this paper, we propose a parallelization in an iterative level of a local search. The contribution of this work is to propose a robust local search through two popular neighborhood structures. This contribution is applied to some combinatorial problems and adapted for the GPU platform. For this, several techniques have been proposed to accelerate the memory access, control the divergence and to maximize the parallelization. Many versions have been implemented with the OpenCL language to test parallelization on both GPU and CPU. Computational performance of this parallel local search are reported and compared to the sequential version.