リケラボ論文検索は、全国の大学リポジトリにある学位論文・教授論文を一括検索できる論文検索サービスです。

リケラボ 全国の大学リポジトリにある学位論文・教授論文を一括検索するならリケラボ論文検索大学・研究所にある論文を検索できる

リケラボ 全国の大学リポジトリにある学位論文・教授論文を一括検索するならリケラボ論文検索大学・研究所にある論文を検索できる

大学・研究所にある論文を検索できる 「GPU-based Parallel Single and Multi-objective Particle Swarm Optimization for Large Swarms and High Dimensional Problems」の論文概要。リケラボ論文検索は、全国の大学リポジトリにある学位論文・教授論文を一括検索できる論文検索サービスです。
リケラボ

コピーが完了しました

URLをコピーしました

論文の公開元へ論文の公開元へ
書き出し

GPU-based Parallel Single and Multi-objective Particle Swarm Optimization for Large Swarms and High Dimensional Problems

HUSSAIN MD MARUF 大阪府立大学 DOI:info:doi/10.24729/00017392

2021.05.11

概要

The social learning process of birds and fishes inspired the development of the heuristic Particle Swarm Optimization (PSO) search algorithm. The advancement of Graphics Processing Units (GPU) and the Compute Unified Device Architecture (CUDA) platform plays a significant role to reduce the computational time in search algorithm development. This doctoral thesis paper presents a good implementation for the Standard Particle Swarm Optimization (SPSO) on a GPU based on the CUDA architecture, which uses coalescing memory access. Here, we also present an analysis of the performance of the various Pseudorandom Number Generators (PRNGs) on a GPU SPSO on the CUDA architecture. The algorithm is evaluated on a suite of well-known benchmark optimization functions. The experiments are performed on an NVIDIA GeForce GTX 980 GPU and a single core of 3.20 GHz Intel Core i5 4570 CPU and the test results demonstrate that the GPU algorithm runs about maximum 170 times faster than the corresponding CPU algorithm. The success of the PSO algorithm as a single objective optimizer has motivated us to extend its use in multi-objective optimization problems (MOOPs). During the last couple of years, parallel MOPSO (Multi-objective Particle Swarm Optimization) with two or more objectives has gained a lot of attention in the literature on GPU computing. A number of implementations have been published for MOPSO on a GPU. However, none of them have been able to capture good enough Pareto fronts fast. In addition, the authors have pointed out their limitations in various aspects such as archive handling, picking up fewer nondominated solutions and so on. Previous literature also lacks evaluation of its MOPSO implementation with large swarms and high dimensional problems. This thesis paper presents a faster implementation of parallel MOPSO on a GPU based on the CUDA architecture. We achieved our faster implementation by using coalescing memory access, a fast pseudorandom number generator, Thrust library, CUB library, an atomic function, parallel archiving and so on. The proposed parallel implementation of MOPSO using a master-slave model provides up to 157 times speedup compared to the corresponding CPU implementation.

As the proposed implementations perform very highly even with increased size of problem dimensionality and swarm population, it can be widely used in real world optimization problems.

論文の公開元へ

この論文で使われている画像

関連論文

関連論文をもっと見る

参考文献

[1] J. Kennedy and R. C. Eberhart, Particle Swarm Optimization, IEEE International Conference on Neural Networks 4 (1995) 1942-1948.

[2] A. P. Engelbrecht, Fundamentals of Computational Swarm Intelligence, Wiley (2005).

[3] J. Kołodziejczyk Survey on Particle Swarm Optimization accelerated on GPGPU, International Journal of Scientific Engineering and Research 5(12) (2014) 2229-5518.

[4] M. M. Hussain, H. Hattori, and N. Fujimoto, A CUDA Implementation of the Standard Particle Swarm Optimization, 18th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (2016) 219-226.

[5] M. M. Hussain and N. Fujimoto, Effect of the Pseudorandom Number Generators on the Standard Particle Swarm Optimization on a GPU, International Conference on Computational Science and Computational Intelligence (CSCI) (2018).

[6] J. Moore and R. Chapman, Application of Particle Swarm to Multiobjective Optimization, department of Computer Science and Software Engineering, Auburn University (1999).

[7] B. Cao, J. Zhao, Z. Lv, X. Liu, S. Yang, X. Kang, and K. Kang, Distributed Parallel Particle Swarm Optimization for Multi-Objective and Many-Objective Large-Scale Optimization, IEEE Access 5 (2017) 8214-8221.

[8] J. P. Arun, M. Mishra, and S. V. Subramaniam, Parallel Implementation of MOPSO on GPU Using OpenCL and CUDA, 18th International Conference on High Performance Computing (HiPC) (2011) 1-10.

[9] Y. Zhou and Y. Tan, GPU-Based Parallel Multiobjective Particle Swarm Optimization, International Journal of Artificial Intelligence 7, A11 (2011).

[10] X. Hu, Particle Swarm Optimization, www.swarmintelligence.org (2006).

[11] D. Bratton and J. Kennedy, Defining a Standard for Particle Swarm Optimization, IEEE Swarm Intelligence Symposium (2007) 120-127.

[12] J. C. Bansal, P. K. Singh, and M. Saraswat, Inertia Weight Strategies in Particle Swarm Optimization, Third World Congress on Nature and Biologically Inspired Computing (2011) 633-640.

[13] V. Kumar and S. Minz, Multi-Objective Particle Swarm Optimization: An Introduction, Smart Computing Review 4(5) (2014) 335-353.

[14] C. A. C. Coello, G. T. Pulido, and M. S. Lechuga, Handling Multiple Objectives With Particle Swarm Optimization, IEEE Transactions On Evolutionary Computation 8 (3) (2004) 256-279.

[15] K. Deb, Multi-Objective Optimization Using Evolutionary Algorithms, Wiley (2009).

[16] E. Zitzler, K. Deb and L.Thiele, Comparison of Multiobjective Evolutionary Algorithms: Empirical Results, Evolutionary Computation 8 (2) (2000) 173-195.

[17] NVIDIA, CUDA Toolkit Documentation 10.1.168, http://docs.nvidia.com/cuda (2019).

[18] K. E. Hoff III, T. Culver, J. Keyser, M. Lin, and D. Manocha, Fast Computation of Generalized Voronoi Diagrams Using Graphics Hardware, 26th Annual Conference on Computer Graphics and Interactive Techniques (1999) 277-286.

[19] Z. W. Luo, H. Liu, and X. Wu, Artificial Neural Network Computation on Graphic Process Unit, IEEE International Joint Conference on Neural Networks 1 (2005) 622-626.

[20] W. Liu and B. Vinter, An Efficient GPU General Sparse Matrix-Matrix Multiplication for Irregular Data, 28th IEEE International on Parallel and Distributed Processing Symposium (2014) 370-381.

[21] G. Dafeng and W. Xiaojun, Real-time Visual Hull Computation Based on GPU, IEEE International Conference on Robotics and Biomimetics (ROBIO) (2015) 1792-1797.

[22] A. P. Yazdanpanah, A. K. Mandava, E. E. Regentova, V. Muthukumar, and G. Bebis, A CUDA Based Implementation of Locally-and Feature-Adaptive Diffusion Based Image Denoising Algorithm, 11th International Conference on Information Technology: New Generations (ITNG) (2014) 388-393.

[23] NVIDIA, CUDA C Best Practices Guide 10.1.168, https://docs.nvidia.com/cuda/cuda-c-best-practices-guide/index.html (2019).

[24] L. Howes and D. Thomas, Efficient Random Number Generation and Application Using CUDA, GPU Gems 3, Chapter 37, http://developer.nvidia. com/gpugems/GPUGems3/gpugems3_pref01.html (2016).

[25] P. L’ecuyer, Tables of Maximally Equidistributed Combined LFSR Generators, Mathematics of Computation 68 (225) (1999) 261-269.

[26] D. E. Knuth, The Art of Computer Programming, Volume 2: Seminumerical Algorithms (2nd Edition) (1969).

[27] G. Marsaglia, Xorshift RNGs, Journal of Statistical Software 8 (2003) 1-6.

[28] F. Panneton and P. L’Ecuye, Particle Swarm Optimization, IEEE International Conference on Neural Networks 4 (1995) 1942-1948.

[29] J. Kaur, S. Singh and S. Singh, Parallel Implementation of PSO Algorithm Using GPGPU, Second International Conference on Computational Intelligence and Communication Technology (CICT) (2016).

[30] NVIDIA, cuRAND, https://docs.nvidia.com/cuda (2019).

[31] NVIDIA, Thrust, http://docs.nvidia.com/cuda/thrust/index .html (2019).

[32] T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms, The MIT Press (2009).

[33] NVIDIA, CUB Documentation ,https://nvlabs.github.io /cub/index.html (2013).

[34] NVIDIA, CUDA Programming Guide 10.1.168, https://docs.nvidia.com/cuda/cuda-c-programming-guide/index.html (2019).

[35] D. A. VanVeldhuizenr, J. B. Zydallis and G. B. Lamont, Considerations in Engineering Parallel Multiobjective Evolutionary Algorithms, IEEE Transactions on Evolutionary Computation 7 (2) (2003) 144-173.

[36] Y. Zhou and Y. Tan, GPU-based Parallel Particle Swarm Optimization, 11th IEEE Congress on Evolutionary Computation (2009) 1493-1500.

[37] R. M. Calazan, N. Nedjah, and L. D. M. Mourelle, Parallel GPU-based Implementation of High Dimension Particle Swarm Optimizations, IEEE Fourth Latin American Symposium on Circuits and Systems (LASCAS) (2013) 1-4.

[38] V. K. Reddy and L. S. S. Reddy, Performance Evaluation of Particle Swarm Optimization Algorithms on GPU Using CUDA, International Journal of Computer Science and Information Technologies 5(1) (2012) 65-81.

[39] L. Mussia, F. Daoliob, and S. Cagnoni, Evaluation of Parallel Particle Swarm Optimization Algorithms within the CUDA™ Architecture, Information Sciences on Interpretable Fuzzy Systems 181 (2011) 4642-4657.

[40] W. Li and Z. Zhang, A CUDA-based Multichannel Particle Swarm Algorithm, International Conference on Control, Automation and Systems Engineering (CASE) (2011) 1-4.

[41] R. M. Calazan, N. Nedjah, and L. D. M. Mourelle, A Cooperative Parallel Particle Swarm Optimization for High-Dimension Problems on GPUs, BRICS Congress on Computational Intelligence and 11th Brazilian Congress on Computational Intelligence (2013) 356-361.

[42] H. Zhu, Y. Guo, J. Wu, and J. Gu, Paralleling Euclidean Particle Swarm Optimization in CUDA, 4th International Conference on Intelligent Networks and Intelligent Systems (ICINIS) (2011) 93-96.

[43] E. H. M. Silva and C. J. A. B. Filho, PSO Efficient Implementation on GPUs Using Low Latency Memory, IEEE Latin America Transactions 13(5) (2015) 1619-1624.

[44] O. Bali, W. Elloumi, P. Krömer, and A. M. Alimi, GPU Particle Swarm Optimization Applied to Travelling Salesman Problem, IEEE 9th International Symposium on Embedded Multicore/Many-core Systems-on-Chip (MCSoC) (2015) 112-119.

[45] X. Yang, Test Problems in Optimization, Cornell University Library (2010).

[46] NVIDIA, GeForce GTX 980 for Desktop, http://www.geforce.com/hardware/desktop-gpus/geforce-gtx-980.

[47] K. Masuda and K. Kurihara, A Constrained Global Optimization Method Based on Multi-Objective Particle Swarm Optimization, Electronics and Communications in Japan 95 (1) (2012) 43-54.

[48] K. E. Parsopoulos and M. N. Vrahatis, Recent Approaches to Global Optimization Problems through Particle Swarm Optimization, Natural Computing (1) (2002) 235-306.

[49] K. E. Parsopoulos and M. N. Vrahatis, Particle Swarm Optimization Method in Multiobjective Problems, ACM Symposium on Applied Computing (2002) 603-607.

[50] NVIDIA, NVIDIA TITAN V, https://www.nvidia.com/en-us/titan/titan-v.

[51] Intel, Intel Xeon E3-1220 v5, https://ark.intel.com/content/www/us/en/ark/products/88172/ intel-xeon-processor-e3-1220-v5-8m-cache-3- 00-ghz.html.

[52] NVIDIA, GeForce 9800 GT, https://www.geforce.com/hardware/desktop-gpus/geforce-9800gt.

[53] K. E. Parsopoulos, D.K. Tasoulis, and M. N. Vrahatis, Multiobjective Optimization Using Parallel Vector Evaluated Particle Swarm Optimization, IASTED International Conference on Artificial Intelligence and Applications 2 (2004) 823-828.

[54] M. L. Wong , Parallel Multi-objective Evolutionary Algorithms on Graphics Processing Units, 11th Annual Conference Companion on Genetic and Evolutionary Computation Conference (2009) 2515-2522.

参考文献をもっと見る

全国の大学の
卒論・修論・学位論文
を
一発検索！

この論文の関連論文を見る