Accelerating parallel particle swarm optimization via GPU

Abstract

Particle swarm optimization (PSO) is a population-based stochastic and derivative-free method that has been used to solve various optimization problems due to its simplicity and efficiency. While solving high-dimensional or complicated problems, PSO requires a large number of particles to explore the problem domains and consequently introduces high computational costs. In this paper, we focus on the acceleration of PSO for solving box-constrained, load-balanced optimization problems by parallelization on a graphics processing unit (GPU). We propose a GPU-accelerated PSO (GPSO) algorithm by using a thread pool model and implement GPSO on a GPU. Numerical results show that the GPU architecture fits the PSO framework well by reducing computational timing, achieving high parallel efficiency and finding better optimal solutions by using a large number of particles. For example, while solving the 100-dimensional test problems with 65,536 (16×2¹²) particles, GPSO has achieved up to 280X and 83X speedups on a NVIDIA Tesla C1060 1.30 GHz GPU relative to an Intel Xeon-X5450 3.00 GHz central processing unit running in single- and quad-core mode, respectively. GPSO provides a promising method for tackling high-dimensional and difficult optimization problems using a low-cost and many-core GPU system.

Keywords:

• particle swarm optimization
• parallel computing
• graphic process unit

Acknowledgements

The authors are grateful to the anonymous referees and Dianne P. O'Leary for helpful comments and suggestions. This work is partially supported by the National Science Council, the Taida Institute for Mathematical Sciences, and the Mathematics Division of the National Centre for Theoretical Sciences (Taipei Office) in Taiwan.