Exploring parallel multi-GPU local search strategies in a metaheuristic framework

• Published in: Journal of parallel and distributed computing 2018-01, Vol.111, p.39-55
• Main Authors: Rios, Eyder, Ochi, Luiz Satoru, Boeres, Cristina, Coelho, Vitor N., Coelho, Igor M., Farias, Ricardo
• Format: Article
• Language: English
• Subjects: GRASP; ILS; Local search; Minimum latency problem; Multi-GPU; Parallel metaheuristic; VND
• ISSN: 0743-7315; 1096-0848
• DOI: 10.1016/j.jpdc.2017.06.011

Optimization tasks are often complex, CPU-time consuming and usually deal with finding the best (or good enough) solution among alternatives for a given problem. Parallel metaheuristics have been used in many real-world and scientific applications to efficiently solve these kind of problems. Local Search (LS) is an essential component for some metaheuristics and, very often, represents the dominant computational effort accomplished by an algorithm. Several metaheuristic approaches try to adapt traditional LS models to parallel platforms without considering the intrinsic features of the available architectures. In this work, we present a novel local search strategy, so-called Distributed Variable Neighborhood Descent (DVND), specially designed for CPU and multi-GPU environment. Furthermore, a new neighborhood search strategy, so-called Multi Improvement, is introduced, taking advantage of GPU massive parallelism in order to boost up LS procedures. A hard combinatorial problem is considered as case of study, the Minimum Latency Problem (MLP). For tackling this problem, a hybrid metaheuristic algorithm is considered, which combines good quality initial solutions, generated by a Greedy Randomized Adaptive Search Procedures, with a flexible and powerful refinement procedure, inside the scope of an Iterated Local Search. The DVND was compared to the classic local search procedures, producing results that outperformed the best known sequential algorithm found in the literature. The speedups ranged from 7.3 to 13.7, for the larger MLP instances with 500 to 1000 clients. Results demonstrate the effectiveness of the proposed techniques in terms of solution quality, performance and scalability. •A new neighborhood exploration engine called Multi Improvement is proposed, which is capable of exploring the massive parallelism of GPU devices.•A novel multi-neighborhood search procedure called DVND is proposed, specially suited for distributed computing systems.•A multi-GPU and multi-core metaheuristic based on ILS and GRASP was developed.•The results of the metaheuristic outperform previously state-of-the-art solution costs for a NP-Hard problem (the Minimum Latency Problem).•The proposed techniques achieve maximum speedups of 13 times when compared to the state-of-the-art best sequential algorithm.