Feasibility analysis of the use of GPU to improve the efficiency of metaheuristics optimization algorithms
DOI:
https://doi.org/10.37135/ns.01.11.04Keywords:
AC Model, CUDA, GPU, Meta-heuristic, Optimization, Particle Swarm Optimization, Transmission Expansion PlanningAbstract
Currently, several real-world optimization problems have been mathematically modeled. The modeling process considers as much information as possible to provide valid results, and the obtained model is commonly computationally solved. However, as information increases, complexity also increases. Consequently, a larger computational capacity is needed to solve complex and scalable problems. As a result, meta-heuristic algorithms have been developed to solve complex optimization problems. These algorithms are commonly used for two or more dimensions in which vector and matrix operations are involved. Therefore, it is helpful to carry out parallel processes that reduce the runtime to solve this problem. Currently, multi-core central processing units (CPUs) manage to solve small problems with parallel calculations easily. However, the Graphics Processing Unit (GPU) improves performance because it integrates a more significant number of cores than the CPU. It is very useful for solving problems using several processes in parallel. The matrix operations, the Travelling Salesman Problem (TSP), and the electric transmission expansion planning (TEP) problem have been implemented using the GPU to verify the processor's contribution to the performance of scientific calculations. In the results, the GPU helped solve the TSP. Because more solutions or candidate particles were analyzed in less time. Because of these results, it was assumed that there would be a better performance in solving the TEP problem by using the GPU and analyzing a more significant number of candidate topologies in less time. However, this was not the case; according to the results, the use of the GPU takes longer when analyzing more particles.
Downloads
References
Al-Rfou, R., Alain, G., Almahairi, A., Angermueller, C., Bahdanau, D., Ballas, N., ... & Zhang, Y. (2016). “Theano: A Python Framework for Fast Computation of Mathematical Expressions.” ArXiv E-Prints arXiv--1605. https://ui.adsabs.harvard.edu/abs/2016arXiv160502688T/abstract
Anzt, H., Hahn, T., Heuveline, V., & Rocker, B. (2010). “GPU Accelerated Scientific Computing: Evaluation of the NVIDIA Fermi Architecture.” Elementary Kernels and Linear Solvers, KIT. DOI: https://doi.org/10.11588/emclpp.2010.04.11677
Bonate, P. L., & Howard, D. R. (2013). “Evolutionary Optimization Algorithms: Biologically Inspired and Population-Based Approaches to Computer Intelligence.”
Crist, J. (2016). “Dask & Numba: Simple Libraries for Optimizing Scientific Python Code.” In 2016 IEEE International Conference on Big Data (Big Data) (pp. 2342-2343). IEEE. DOI: 10.1109/BigData.2016.7840867
Dogaru, R., & Dogaru, I. (2015).. “A Low Cost High Performance Computing Platform for Cellular Nonlinear Networks Using Python for Cuda.”. In 2015 20th International Conference on Control Systems and Computer Science (pp. 593-598). IEEE. DOI: 10.1109/CSCS.2015.36
Domínguez, J. M., Crespo, A. J., & Gómez-Gesteira, M. (2013). Optimization strategies for CPU and GPU implementations of a smoothed particle hydrodynamics method. Computer Physics Communications, 184(3), 617-627. DOI: https://doi.org/10.1016/j.cpc.2012.10.015
Dorigo, M., & Stützle, T. (2003). The ant colony optimization metaheuristic: Algorithms, applications, and advances. Handbook of metaheuristics, 250-285. DOI:https://doi.org/10.1007/0-306-48056-5_9
Fonseka, J., & Miranda, V. (2004). A hybrid meta‐heuristic algorithm for transmission expansion planning. COMPEL-The international journal for computation and mathematics in electrical and electronic engineering, Vol. 23 No. 1, pp. 250-262. DOI: https://doi.org/10.1108/03321640410507789
Knepley, M. G., & Yuen, D. A. (2013). Why Do Scientists and Engineers Need GPU’s Today?. In GPU Solutions to Multi-scale Problems in Science and Engineering (pp. 3-11). Springer, Berlin, Heidelberg. DOI: https://doi.org/10.1007/978-3-642-16405-7_1
Kurniasih, J., Utami, E., & Raharjo, S. (2019, August). Heuristics and metaheuristics approach for query optimization using genetics and memetics algorithm. In 2019 1st international conference on cybernetics and intelligent system (ICORIS) (Vol. 1, pp. 168-172). IEEE. DOI: 10.1109/ICORIS.2019.8874909
Lam, S. K., Pitrou, A., & Seibert, S. (2015). Numba: A llvm-based python jit compiler. In Proceedings of the Second Workshop on the LLVM Compiler Infrastructure in HPC (pp. 1-6). DOI: https://doi.org/10.1145/2833157.2833162
Lambert-Torres, G., Martins, H. G., Coutinho, M. P., Salomon, C. P., & Filgueiras, L. S. (2008, December). Particle swarm optimization applied to restoration of electrical energy distribution systems. In International Symposium on Intelligence Computation and Applications (pp. 228-238). Springer, Berlin, Heidelberg. DOI: https://doi.org/10.1007/978-3-540-92137-0_26
Lezama, J. M. L., & Pareja, L. A. G. (2008). Flujo de potencia óptimo con restricciones de seguridad usando un metodo de punto interior. Scientia et technica, 2(39). DOI: https://doi.org/10.22517/23447214.3143
Lin, S. (1965). Computer solutions of the traveling salesman problem. Bell System Technical Journal, 44(10), 2245-2269. https://doi.org/10.1002/j.1538-7305.1965.tb04146.x
Van Luong, T., Melab, N., & Talbi, E. G. (2011). GPU computing for parallel local search metaheuristic algorithms. IEEE transactions on computers, 62(1), 173-185. DOI: 10.1109/TC.2011.206
Matute, N. E., Torres, S. P., Morquecho, E. G., Astudillo-Salinas, F., Lopez, J. C., & Flores, W. C. (2020). Improving the AC Transmission Expansion Planning by Using Initial Solutions Algorithms. In 2020 IEEE PES Innovative Smart Grid Technologies Europe (ISGT-Europe) (pp. 494-498). IEEE. DOI: 10.1109/ISGT-Europe47291.2020.9248778
Morquecho, E. G., Torres, S. P., & Castro, C. A. (2021). An efficient hybrid metaheuristics optimization technique applied to the AC electric transmission network expansion planning. Swarm and Evolutionary Computation, 61, 100830. DOI: https://doi.org/10.1016/j.swevo.2020.100830
Morquecho, E. G., Torres, S. P., Matute, N. E., Astudillo-Salinas, F., Lopez, J. C., & Flores, W. C. (2020). AC dynamic transmission expansion planning using a hybrid optimization algorithm. In 2020 IEEE PES Innovative Smart Grid Technologies Europe (ISGT-Europe) (pp. 499-503). IEEE. DOI: 10.1109/ISGT-Europe47291.2020.9248898
Nebro, A. J., Durillo, J. J., Garcia-Nieto, J., Coello, C. C., Luna, F., & Alba, E. (2009). SMPSO: A new PSO-based metaheuristic for multi-objective optimization. In 2009 IEEE Symposium on computational intelligence in multi-criteria decision-making (MCDM) (pp. 66-73). IEEE. DOI: 10.1109/MCDM.2009.4938830
Oliphant, T. E. (2006). A guide to NumPy (Vol. 1). USA: Trelgol Publishing. Obtenido de https://ecs.wgtn.ac.nz/foswiki/pub/Support/ManualPagesAndDocumentation/numpybook.pdf
Preferred Networks, inc., and inc. Preferred Infrastructure. 2018. “CuPy Documentation.”. Obtenido de https://docs.cupy.dev/_/downloads/en/v2.3.0/pdf/
Rodriguez, J. I. R., Falcão, D. M., & Taranto, G. N. (2008). Short-term transmission expansion planning with AC network model and security constraints. 16th PSCC, 1-7. Obtenido de https://www.researchgate.net/profile/Falcao-Djalma/publication/229000110_Short-Term_Transmission_Expansion_Planning_with_AC_Network_Model_and_Security_Constraints/links/548347d90cf25dbd59eb0ca4/Short-Term-Transmission-Expansion-Planning-with-AC-Network-Model-and-Security-Constraints.pdf
Sapra, D., Sharma, R., & Agarwal, A. P. (2017). Comparative study of metaheuristic algorithms using Knapsack Problem. In 2017 7th International Conference on Cloud Computing, Data Science & Engineering-Confluence (pp. 134-137). IEEE. DOI: 10.1109/CONFLUENCE.2017.7943137
Souza, D. L., Monteiro, G. D., Martins, T. C., Dmitriev, V. A., & Teixeira, O. N. (2011). PSO-GPU: accelerating particle swarm optimization in CUDA-based graphics processing units. In Proceedings of the 13th annual conference companion on Genetic and evolutionary computation (pp. 837-838). DOI: https://doi.org/10.1145/2001858.2002114
Sunitha, N. V., Raju, K., & Chiplunkar, N. N. (2017). Performance improvement of CUDA applications by reducing CPU-GPU data transfer overhead. In 2017 international conference on inventive communication and computational technologies (ICICCT) (pp. 211-215). IEEE. DOI: 10.1109/ICICCT.2017.7975190
Teodoro, G., Sachetto, R., Sertel, O., Gurcan, M. N., Meira, W., Catalyurek, U., & Ferreira, R. (2009). Coordinating the use of GPU and CPU for improving performance of compute intensive applications. In 2009 IEEE International Conference on Cluster Computing and Workshops (pp. 1-10). IEEE. DOI: 10.1109/CLUSTR.2009.5289193
Thurner, L., Scheidler, A., Dollichon, J., Schäfer, F., Menke, J. H., Meier, F., & Meinecke, S. (2016). pandapower: Convenient Power System Modelling and Analysis based on PYPOWER and pandas.
Torres, S. P., & Castro, C. A. (2012, September). Parallel particle swarm optimization applied to the static transmission expansion planning problem. In 2012 Sixth IEEE/PES Transmission and Distribution: Latin America Conference and Exposition (T&D-LA) (pp. 1-6). IEEE. DOI: 10.1109/TDC-LA.2012.6319053
Torres, S. P., & Castro, C. A. (2014). Expansion planning for smart transmission grids using AC model and shunt compensation. IET Generation, Transmission & Distribution, 8(5), 966-975. https://doi.org/10.1049/iet-gtd.2013.0231
Trelea, I. C. (2003). The particle swarm optimization algorithm: convergence analysis and parameter selection. Information processing letters, 85(6), 317-325. DOI: https://doi.org/10.1016/S0020-0190(02)00447-7
Verma, S., & Mukherjee, V. (2016). Transmission expansion planning: A review. In 2016 International Conference on Energy Efficient Technologies for Sustainability (ICEETS) (pp. 350-355). IEEE. DOI: 10.1109/ICEETS.2016.7583779
Zimmerman, R. D., Murillo-Sánchez, C. E., & Thomas, R. J. (2010). MATPOWER: Steady-state operations, planning, and analysis tools for power systems research and education. IEEE Transactions on power systems, 26(1), 12-19. DOI: 10.1109/TPWRS.2010.2051168
