کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4951503 1441474 2018 17 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Exploring parallel multi-GPU local search strategies in a metaheuristic framework
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Exploring parallel multi-GPU local search strategies in a metaheuristic framework
چکیده انگلیسی


- 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.

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Parallel and Distributed Computing - Volume 111, January 2018, Pages 39-55
نویسندگان
, , , , , ,