A cooperative GPU-based Parallel Multistart Simulated Annealing algorithm for Quadratic Assignment Problem
| Autor: | Baha Sen, Emrullah Sonuc, Safak Bayir |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Fluid Flow and Transfer Processes
021103 operations research Computer Networks and Communications Computer science Heuristic (computer science) Quadratic assignment problem Mechanical Engineering 0211 other engineering and technologies Metals and Alloys Parallel algorithm Combinatorial optimization problem 02 engineering and technology Parallel computing Electronic Optical and Magnetic Materials Biomaterials CUDA Acceleration lcsh:TA1-2040 Hardware and Architecture Simulated annealing 0202 electrical engineering electronic engineering information engineering Benchmark (computing) 020201 artificial intelligence & image processing lcsh:Engineering (General). Civil engineering (General) Civil and Structural Engineering |
| Zdroj: | Engineering Science and Technology, an International Journal, Vol 21, Iss 5, Pp 843-849 (2018) |
| ISSN: | 2215-0986 |
| Popis: | GPU hardware and CUDA architecture provide a powerful platform to develop parallel algorithms. Implementation of heuristic and metaheuristic algorithms on GPUs are limited in literature. Nowadays developing parallel algorithms on GPU becomes very important. In this paper, NP-Hard Quadratic Assignment Problem (QAP) that is one of the combinatorial optimization problems is discussed. Parallel Multistart Simulated Annealing (PMSA) method is developed with CUDA architecture to solve QAP. An efficient method is developed by providing multistart technique and cooperation between threads. The cooperation is occurred with threads in both the same and different blocks. This paper focuses on both acceleration and quality of solutions. Computational experiments conducted on many Quadratic Assignment Problem Library (QAPLIB) instances. The experimental results show that PMSA runs up to 29x faster than a single-core CPU and acquires best known solution in a short time in many benchmark datasets. Keywords: Combinatorial optimization, CUDA, GPU, Multistart Simulated Annealing, Parallel algorithms, Quadratic Assignment Problem |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|