Ke Ding
ABSTRACT
Swarm intelligence algorithms have been widely used to solve difficult real world problems in both academic and engineering domains. Thanks to the inherent parallelism, various parallelized swarm intelligence algorithms have been proposed to speed up the optimization process, especially on the massively parallel processing architecture GPUs. However, conventional swarm intelligence algorithms are usually not designed specifically for the GPU architecture.They neither can fully exploit the tremendous computational power of GPUs nor can extend effectively as the problem scales go large. To address this shortcoming, a novel GPU-based Fireworks Algorithm (GPU-FWA) is proposed in this paper. In order to fully leverage GPUs' high performance, GPU-FWA modified the original FWA so that it is more suitable for the GPU architecture. An implementation of GPU-FWA on the CUDA platform is presented and then tested on a suite of well-known benchmark optimization problems. We extensively evaluated GPU-FWA and compared it with FWA and PSO, with respect to both running time and solution quality, on a state-of-the-art commodity Fermi GPU.Experimental results demonstrate that GPU-FWA generally outperforms both FWA and PSO, and enjoys a significant speedup as high as 200x, compared to the sequential version of FWA and PSO running on an up-to-date CPU. GPU-FWA also enjoys the advantages of being easy to implement and scalable.
- P. E. Andries and P. Engelbrecht. Fundamentals of Computational Swarm Intelligence. Wyley, 2005. Google Scholar
Digital Library
- D. Bratton and J. Kennedy. Defining a standard for particle swarm optimization. In Swarm Intelligence Symposium, 2007. SIS 2007. IEEE, pages 120--127, April 2007.Google ScholarDigital Library
- L. de P. Veronese and R. A. Krohling. Swarm's flight: Accelerating the particles using c-cuda. In Evolutionary Computation, 2009. CEC '09. IEEE Congress on, pages 3264--3270, May 2009. Google ScholarDigital Library
- R. C. Eberhart, Y. Shi, and J. Kennedy. Swarm Intelligence. Morgan Kaufmann, San Francisco, California, 2001.Google Scholar
- A. Janecek and Y. Tan. Swarm intelligence for non-negative matrix factorization. International Journal of Swarm Intelligence Research, 2(4):12--34, October-December 2011.Google ScholarCross Ref
- P. Krömer, V. Snåšel, J. Platoš, and A. Abraham. Many-threaded implementation of differential evolution for the cuda platform. In Proceedings of the 13th annual conference on Genetic and evolutionary computation, GECCO '11, pages 1595--1602. ACM, 2011. Google ScholarDigital Library
- M. Molga and C. Smutnicki. Test functions for optimization needs, 2005.Google Scholar
- NVIDIA. NVIDIA CUDA C Best Practices Guide 5.0, October 2012.Google Scholar
- NVIDIA. NVIDIA's Next Generation CUDA#8482; Compute Architecture: Fermi#8482;, 2012.Google Scholar
- NVIDIA. Toolkit 5.0 CURAND Guide, September 2012.Google Scholar
- J. Owens, M. Houston, D. Luebke, S. Green, J. Stone, and J. Phillips. Gpu computing. Proceedings of the IEEE, 96(5):879--899, May 2008.Google ScholarCross Ref
- J. D. Owens, D. Luebke, N. Govindaraju, M. Harris, J. Krüger, A. E. Lefohn, and T. J. Purcell. A survey of general-purpose computation on graphics hardware. Computer Graphics Forum, 26(1):80--113, March 2007.Google ScholarCross Ref
- V. Roberge and M. Tarbouchi. Parallel particle swarm optimization on graphical processing unit for pose estimation. WSEAS TRANSACTIONS on COMPUTERS, 11(6):170 --179, June 2012.Google Scholar
- S. Solomon, P. Thulasiraman, and R. Thulasiram. Collaborative multi-swarm pso for task matching using graphics processing units. In Proceedings of the 13th annual conference on Genetic and evolutionary computation, GECCO '11, pages 1563--1570, New York, NY, USA, 2011. ACM. Google ScholarDigital Library
- Y. Tan and Y. Zhu. Fireworks algorithm for optimization. In Advances in Swarm Intelligence, volume 6145 of Lecture Notes in Computer Science, pages 355--364. Springer Berlin Heidelberg, 2010. Google ScholarDigital Library
- M.-L. Wong, T.-T. Wong, and K.-L. Fok. Parallel evolutionary algorithms on graphics processing unit. In Evolutionary Computation, 2005. The 2005 IEEE Congress on, volume 3, pages 2286--2293, September 2005.Google ScholarCross Ref
- Y. Zhou and Y. Tan. Gpu-based parallel particle swarm optimization. In Evolutionary Computation, 2009. CEC '09. IEEE Congress on, pages 1493--1500, May 2009. Google ScholarDigital Library
- Y. Zhou and Y. Tan. Gpu-based parallel multi-objective particle swarm optimization. International Journal of Artificial Intelligence, 7(A11):125--141, October 2011.Google Scholar
Index Terms
- A GPU-based parallel fireworks algorithm for optimization
Recommendations
Optimization principles and application performance evaluation of a multithreaded GPU using CUDA
PPoPP '08: Proceedings of the 13th ACM SIGPLAN Symposium on Principles and practice of parallel programmingGPUs have recently attracted the attention of many application developers as commodity data-parallel coprocessors. The newest generations of GPU architecture provide easier programmability and increased generality while maintaining the tremendous memory ...
An efficient parallel collaborative filtering algorithm on multi-GPU platform
Collaborative filtering (CF) is one of the essential algorithms in recommendation system. As the size of the data in real applications is huge, usually at the magnitude of Petabytes, parallel computing technique is required to accelerate the ...
A parallel Bees Algorithm implementation on GPU
Bees Algorithm is a population-based method that is a computational bound algorithm whose inspired by the natural behavior of honey bees to finds a near-optimal solution for the search problem. Recently, many parallel swarm based algorithms have been ...
Comments