Abstract
Many scientific and technical problems with massive computation requirements could benefit from the graphics processing units (GPUs) using compute unified device architecture (CUDA). Gravitational search algorithm (GSA) is a population-based metaheuristic which can be effectively implemented on GPU to reduce the execution time. Nonetheless, the performance improvement depends strongly on the process used to adapt the algorithm into CUDA environment. In this paper, we discuss possible approaches to parallelize GSA on graphics hardware using CUDA. An in-depth study of the computation efficiency of parallel algorithms and capability to effectively exploit the architecture of GPU is performed. Additionally, a comparative study of parallel and sequential GSA was carried out on a set of standard benchmark optimization functions. The results show a significant speedup while maintaining results quality which re-emphasizes the utility of CUDA-based implementation for complex and computationally intensive parallel applications.
Similar content being viewed by others
References
Alba E, Luque G (2006) Evaluation of parallel metaheuristics. Lect Notes Comput Sci 4193:9–14
Calazan RM, Nedjah N, de Macedo Mourelle L (2012) Swarm grid: a proposal for high performance of parallel particle swarm optimization using GPGPU. In: Computational science and its applications-ICCSA 2012. Springer, Berlin, pp 148–160
Calazan RM, Nedjah N, de Macedo Mourelle L (2013) Parallel GPU-based implementation of high dimension particle swarm optimizations. In: IEEE Fourth Latin American Symposium on Circuits and systems (LASCAS), 2013, pp 1–4
Cárdenas-Montes M, Vega-Rodríguez MA, Rodríguez-Vázquez JJ, Gómez-Iglesias A (2012) A GPU-based evaluation to accelerate particle swarm algorithm. In: Computer aided systems theory-EUROCAST 2011. Springer, Berlin, pp 272–279
Charles JS, Potok TE, Patton R, Cui X (2008) Flocking-based document clustering on the graphics processing unit. Springer, Berlin
Chen Z, Yuan X, Tian H, Ji B (2014) Improved gravitational search algorithm for parameter identification of water turbine regulation system. Energy Convers Manag 78:306–315
de P Veronese L, Krohling RA (2009) Swarm’s flight: accelerating the particles using C-CUDA. In: IEEE Congress on Evolutionary computation, 2009, pp 3264–3270
Formato RA (2008) Central force optimization: a new nature inspired computational framework for multidimensional search and optimization. In: Nature Inspired Cooperative Strategies for Optimization (NICSO 2007). Springer, Berlin, pp 221–238
Gao S, Chai H, Chen B, Yang G (2013) Hybrid gravitational search and clonal selection algorithm for global optimization. In: Advances in swarm intelligence. Springer, Berlin, pp 1–10
Glodberg DE (1989) Genetic algorithms in search, optimization, and machine learning. Addion wesley, USA
Gotshall S, Rylander B (2008) Optimal population size and the genetic algorithm. Population 100(400):900
Green II RC, Wang L, Alam M, Formato RA (2012) Central force optimization on a GPU: a case study in high performance metaheuristics. J Supercomput 62(1):378–398
Harris M (2007) Optimizing parallel reduction in CUDA. NVIDIA Developer Technology
Kennedy J, Eberhart R (1995) Particle swarm optimization. In: IEEE International Conference on Neural Networks, vol 4, pp 1942–1948
Kumar J, Singh L, Paul S (2013) GPU based parallel cooperative particle swarm optimization using C-CUDA: a case study. In: IEEE International Conference on Fuzzy Systems (FUZZ), 2013, pp 1–8
Li J-M, Wang X-J, He R-S, Chi Z-X (2007) An efficient fine-grained parallel genetic algorithm based on GPU-accelerated. In: Proceedings of the 2007 IFIP International Conference on Network and Parallel Computing Workshops, pp 855–862
Li J, Wan D, Chi Z (2007) An efficient fine-grained parallel particle swarm optimization method based on GPU-acceleration. Int J Innov Comput Inform Control 3(6):1707–1714
Li-Ping Z, Huan-Jun Y, Shang-Xu H (2005) Optimal choice of parameters for particle swarm optimization. J Zhejiang Univ Sci A 6(6):528–534
Mallick S, Ghoshal SP, Acharjee P, Thakur SS (2013) Optimal static state estimation using improved particle swarm optimization and gravitational search algorithm. Int J Electr Power Energy Syst 52:254–265
Mussi L, Daolio F, Cagnoni S (2011) Evaluation of parallel particle swarm optimization algorithms within the CUDA architecture. Inform Sci 181(20):4642–4657
Mussi L, Nashed YSG, Cagnoni S (2011) GPU-based asynchronous particle swarm optimization. In: Proceedings of the 13th annual conference on Genetic and evolutionary computation, pp 1555–1562. ACM
CUDA Nvidia (2013) C programming guide 5.5. NVIDIA Corporation, USA
Pedersen Magnus EH (2010) Good parameters for particle swarm optimization. Hvass Lab., Copenhagen, Denmark, Tech. Rep. HL1001
Rashedi E, Nezamabadi-Pour H, Saryazdi S (2009) GSA: a gravitational search algorithm. Inform Sci 179(13):2232–2248
Rashedi E, Nezamabadi-Pour H, Saryazdi S (2011) Filter modeling using gravitational search algorithm. Eng Appl Artif Intell 24(1):117–122
Rong G, Liu G, Zheng M, Sun A, Tian Y, Wang H (2013) Parallel gravitation field algorithm based on the CUDA platform. J Inform Comput Sci 10:3635–3644
CUDA Toolkit (2013) Curand guide 5.5. NVIDIA Corporation, USA
Wong M-L, Wong T-T, Fok K-L (2005) Parallel evolutionary algorithms on graphics processing unit. In: The IEEE Congress on Evolutionary Computation, 2005, vol 3, pp 2286–2293
Zarrabi A, Samsudin K (2014) Task scheduling on computational grids using gravitational search algorithm. Cluster Comput 17(3):1001–1011
Zhou Y, Tan Y (2009) Gpu-based parallel particle swarm optimization. In: IEEE Congress on Evolutionary Computation, 2009. CEC’09, pp 1493–1500
Zhou Y, Tan Y (2010) Particle swarm optimization with triggered mutation and its implementation based on GPU. In: Proceedings of the 12th annual conference on Genetic and evolutionary computation, pp 1–8. ACM
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Zarrabi, A., Samsudin, K. & Karuppiah, E.K. Gravitational search algorithm using CUDA: a case study in high-performance metaheuristics. J Supercomput 71, 1277–1296 (2015). https://doi.org/10.1007/s11227-014-1360-1
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11227-014-1360-1