Análisis de factibilidad del uso de GPU para mejorar la eficiencia de los algoritmos de optimización de metaheurísticas
DOI:
https://doi.org/10.37135/ns.01.11.04Palabras clave:
Modelo AC, CUDA, GPU, Meta-heurística, Optimización, optimización de enjambre de partículas, planificación de expansión de transmisión.Resumen
Actualmente, varios problemas de optimización del mundo real han sido modelados matemáticamente. El proceso de modelado considera la mayor cantidad de información posible para proporcionar resultados válidos, y el modelo obtenido comúnmente se resuelve computacionalmente. Sin embargo, a medida que aumenta la información, también aumenta la complejidad. En consecuencia, se necesita una mayor capacidad computacional para resolver problemas complejos y escalables. Como resultado, se han desarrollado algoritmos meta-heurísticos para resolver problemas complejos de optimización. Estos algoritmos se usan comúnmente para dos o más dimensiones en las que están involucradas operaciones vectoriales y matriciales. Por lo tanto, es útil realizar procesos paralelos que reduzcan el tiempo de ejecución para solucionar este problema. Actualmente, las unidades centrales de procesamiento (CPU, por sus siglas en inglés) multinúcleo logran resolver fácilmente pequeños problemas con cálculos paralelos. Sin embargo, la unidad de procesamiento de gráficos (GPU, por sus siglas en inglés) mejora el rendimiento porque integra una cantidad de núcleos más importante que la CPU. Es muy útil para resolver problemas utilizando varios procesos en paralelo. Las operaciones matriciales, el problema del vendedor y el problema de planificación de expansión de la transmisión (TEP) han sido seleccionados para implementarse utilizando la GPU para verificar la contribución del procesador al rendimiento de los cálculos científicos. En los resultados, la GPU ayudó a resolver el "problema del vendedor" porque se analizaron más soluciones o partículas candidatas en menos tiempo. Debido a estos resultados, se asumió que habría un mejor rendimiento resolviendo el problema TEP utilizando la GPU y analizando un número mayor de topologías candidatas en menos tiempo. Sin embargo, este no fue el caso; según los resultados, el uso de la GPU lleva más tiempo al analizar más partículas.
Descargas
Referencias
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
