Parallel local search on GPU and CPU with OpenCL

Omar Abdelkafi, Khalil Chebil, Mahdi Khemakhem
1st International Conference on Reasoning and Optimization in Information Systems (ROIS), 2013


   title={Parallel local search on GPU and CPU with OpenCL},

   author={ABDELKAFI, Omar and CHEBIL, Khalil and KHEMAKHEM, Mahdi},



Download Download (PDF)   View View   Source Source   



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.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2024 hgpu.org

All rights belong to the respective authors

Contact us: