Evaluación comparativa del rendimiento entre procesadores CPU y GPU para el problema del viajante
un estudio comparativo computacional utilizando un algoritmo de fuerza bruta
DOI:
https://doi.org/10.47385/cadunifoa.v21.n56.5758Palabras clave:
Optimización combinatoria, CUDA, Computación paralela, GPUResumen
El Problema del Viajante de Comercio (PVC) es uno de los problemas de optimización combinatoria más estudiados en la ciencia de la computación y pertenece a la clase NP-difícil. Este trabajo presenta un análisis comparativo entre implementaciones secuenciales en CPU e implementaciones paralelas en GPU utilizando CUDA para resolver el PVC mediante el algoritmo de fuerza bruta. El estudio se realizó en Python con las bibliotecas NumPy y CuPy en el entorno de Google Colab. Para un grafo con 10 vértices, totalizando 362.880 permutaciones, la implementación en GPU presentó una aceleración (speedup) de 1,30x en relación con la CPU, reduciendo el tiempo de ejecución de 1,3622 segundos a 1,0450 segundos. Los resultados destacan el potencial de la computación paralela en GPU para problemas de optimización combinatoria, especialmente cuando el volumen computacional justifica la sobrecarga de transferencia de datos entre CPU y GPU.
Descargas
Citas
APPLEGATE, D. L. et al. The traveling salesman problem: a computational study. Princeton: Princeton University Press, 2007.
GUTIN, G.; PUNNEN, A. P. The traveling salesman problem and its variations. Boston: Springer, 2006. DOI: https://doi.org/10.1007/b101971
KIRK, D. B.; HWEU, W. W. Programming massively parallel processors: a hands-on approach. 3. ed. Burlington: Morgan Kaufmann, 2016.
LAWLER, E. L. et al. The traveling salesman problem: a guided tour of combinatorial optimization. Chichester: Wiley, 1985. DOI: https://doi.org/10.2307/2582681
MITTAL, S.; VETTER, J. S. A survey of CPU-GPU heterogeneous computing techniques. ACM Computing Surveys, v. 47, n. 4, p. 1-35, 2015. Available at: https://dl.acm.org/doi/10.1145/2788396. Accessed on: 20 maio 2025. DOI: https://doi.org/10.1145/2788396
SANDERS, J.; KANDROT, E. CUDA by example: an introduction to general-purpose GPU programming. Boston: Addison-Wesley, 2010.
Binjubeir, Mohammed Mahfoudh & Ismail, Mohd Arfian & Tusher, Ekramul Haque & Aljanabi, Mohammad. (2024). A GPU Accelerated Parallel Genetic Algorithm for the Traveling Salesman Problem. Journal of Soft Computing and Data Mining. 5. 137-150. Available at: http://umpir.ump.edu.my/id/eprint/43901/. Accessed on: 26 maio 2025.
EKER, Musa; ŞEN, Baha; KUMRU, Pinar Yildiz. An efficient solving of the traveling salesman problem: the ant colony system having parameters optimized by the Taguchi method. Turkish Journal of Electrical Engineering and Computer Sciences, v. 21, n. 7, art. 15, 2013. DOI: https://doi.org/10.3906/elk-1109-44. Available at: https://journals.tubitak.gov.tr/elektrik/vol21/iss7/15. Accessed on: 6 jun. 2025.
K. Rocki and R. Suda. High Performance GPU Accelerated Local Optimization in TSP. 2013 IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum, Cambridge, MA, USA, 2013, pp. 1788-1796, doi: 10.1109/IPDPSW.2013.227. Accessed on: 6 mai. 2025. DOI: https://doi.org/10.1109/IPDPSW.2013.227
FUJIMOTO, N. TSUTSUI, S. A highly-parallel TSP solver for a GPU computing platform. In: INTERNATIONAL CONFERENCE ON PARALLEL PROCESSING AND APPLIED MATHEMATICS, 2010. Available at: https://link.springer.com/chapter/10.1007/978-3-642-18466-6_31. Accessed on: 1 mai. 2025.
FOSIN, J.; DAVIDOVIĆ, D.; CARIĆ, T. A GPU implementation of local search operators for symmetric travelling salesman problem. Promet - Traffic & Transportation, v. 25, n. 3, p. 225-234, 2013. Available at: https://hrcak.srce.hr/clanak/164448. Accessed on: 10 mai. 2025. DOI: https://doi.org/10.7307/ptt.v25i3.300
Descargas
Publicado
Cómo citar
Número
Sección
Licencia
Derechos de autor 2026 Cadernos UniFOA
Esta obra está bajo una licencia internacional Creative Commons Atribución-NoComercial-CompartirIgual 4.0.
Declaração de Transferência de Direitos Autorais - Cadernos UniFOA como autor(es) do artigo abaixo intitulado, declaro(amos) que em caso de aceitação do artigo por parte da Revista Cadernos UniFOA, concordo(amos) que os direitos autorais e ele referentes se tornarão propriedade exclusiva desta revista, vedada qualquer produção, total ou parcial, em qualquer outra parte ou meio de divulgação, impressa ou eletrônica, sem que a prévia e necessária autorização seja solicitada e, se obtida, farei(emos) constar o agradecimento à Revista Cadernos UniFOA, e os créditos correspondentes. Declaro(emos) também que este artigo é original na sua forma e conteúdo, não tendo sido publicado em outro periódico, completo ou em parte, e certifico(amos) que não se encontra sob análise em qualquer outro veículo de comunicação científica.
O AUTOR desde já está ciente e de acordo que:
- A obra não poderá ser comercializada e sua contribuição não gerará ônus para a FOA/UniFOA;
- A obra será disponibilizada em formato digital no sítio eletrônico do UniFOA para pesquisas e downloads de forma gratuita;
- Todo o conteúdo é de total responsabilidade dos autores na sua forma e originalidade;
- Todas as imagens utilizadas (fotos, ilustrações, vetores e etc.) devem possuir autorização para uso;
- Que a obra não se encontra sob a análise em qualquer outro veículo de comunicação científica, caso contrário o Autor deverá justificar a submissão à Editora da FOA, que analisará o pedido, podendo ser autorizado ou não.
O AUTOR está ciente e de acordo que tem por obrigação solicitar a autorização expressa dos coautores da obra/artigo, bem como dos professores orientadores antes da submissão do mesmo, se obrigando inclusive a mencioná-los no corpo da obra, sob pena de responder exclusivamente pelos danos causados.
