Avaliação de Algoritmos de Ordenação de Dados em Ambiente de HPC com Raspberry Pi
Resumo
A Computação de Alto Desempenho (HPC) integra hardware e software para explorar paralelismo e distribuição de tarefas, sendo fundamental em várias áreas científicas. Este artigo avalia seis algoritmos de ordenação de dados em três abordagens: sequencial, paralelismo em memória compartilhada (OpenMP) e paralelismo distribuído (MPI), executados em Raspberry Pi. Os resultados mostram que o MPI favorece algoritmos naturalmente divisíveis, como Merge Sort e Bubble Sort, enquanto o OpenMP apresenta melhor desempenho em algoritmos com bom paralelismo intra-nó, como Insertion Sort e Quick Sort. Já algoritmos eficientes de forma sequencial, como Radix Sort e Heap Sort, pouco se beneficiaram da paralelização. A comparação entre clusters de RPis evidenciou que avanços arquiteturais, resultam em ganhos, destacando que a escolha do modelo de paralelismo depende tanto da natureza do algoritmo quanto da arquitetura de execução.Referências
Ala’anzy, M. A.; Mazhit, Z.; Ala’anzy, A. F.; Algarni, A.; Akhmedov, R.; Bauyrzhan, A. (2024) “Comparative Analysis of Sorting Algorithms: A Review”. In 11th International Conference on Soft Computing & Machine Intelligence (ISCMI), Melbourne, Australia, pp. 88-100.
Andrews, G. R. (2001) “Foundations of Multithreaded, Parallel, and Distributed Programming”. Boston, Massachusetts, EUA: Addison-Wesley, 2 nd edition, 664p.
Aung, H. H. (2019) “Analysis and Comparative of Sorting Algorithms”. In International Journal of Trend in Scientific Research and Development (IJTSRD), 3(5):1049-1053, August.
Chandra, R.; Dagum, L.; Kohr, D.; Maydan, D.; McDonald, J.; Menon, R. (2000) “Parallel Programming in OpenMP”. San Francisco, CA, USA: Morgan Kaufmann, 1 st edition, 240p.
Colichio, H.; Pimenta, Y.; Borges, P.; Menecucci, M.; Barros, L.; Guardia, H. (2024) “Ordenação Paralela com OpenMP e CUDA”. In Escola Regional de Alto Desempenho de São Paulo (ERAD-SP), Rio Claro, SP, Brasil, pp. 9-12.
Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C. (2012) “Algoritmos: Teoria e Prática”. GEN LTC, 3ª edição, 944p.
Google Cloud. (2025) “BigQuery: Managed Data Warehouse for Analytics”, disponível em [link]. Acessado em 03/06/2025.
Gropp, W.; Lusk, E.; Skjellum, A. (1994) “Using MPI: Portable Parallel Programming with the Message Passing Interface”. Cambridge, Massachusetts, EUA: MIT Press, 1 st edition, 307p.
Ignácio, A. L. J.; Dias, W. R. A. (2023) “Análise do Desempenho Computacional de Algoritmos Paralelizados com OpenMP e MPI Executados em Raspberry Pi”. In Workshop de Iniciação Científica - Simpósio em Sistemas Computacionais de Alto Desempenho (SSCAD), Porto Alegre, RS, Brasil, pp. 41-48.
Knuth, D. E. (1998) “The Art of Computer Programming, Volume 3: Sorting and Searching”. Addison-Wesley.
Lima, F. A.; Moreno, E. D.; Dias, W. R. A. (2016) “Performance Analysis of a Low Cost Cluster with Parallel Applications and ARM Processors”. In IEEE Latin America Transactions, 14(11):4591-4596, December.
Moore, G. E. (1965). “Cramming More Components onto Integrated Circuits”. In Electronics, 38(8):114-117.
Mpi, (2025) “A Message-Passing Interface Standard Version 2.1”, disponível em www.mpiforum.org/docs/mpi21-report.pdf. Acessado em 10/07/2025.
OpenMP, (2025) “The OpenMP API Specification for Parallel Programming”, disponível em [link]. Acessado em 12/07/2025.
Pacheco, P. S. (2011) “An Introduction to Parallel Programming”. Morgan Kaufmann Publishers, 1 st ed., 370p.
Parhami, B. (2006) “Introduction to Parallel Processing - Algorithms and Architectures”. New York, USA: Kluwer Academic Publishers, 1 st edition, 532p.
Rajagopal, D.; Thilakavalli, K. (2016) “Different Sorting Algorithm’s Comparison based Upon the Time Complexity”. In International Journal of u- and e-Service, Science and Technology, 9(8):287-296, November.
Rauber, T.; Rünger, G. (2013) “Parallel Programming for Multicore Cluster Systems”. Springer, 2 nd ed., 516p.
Ribeiro, G. O.; Sêmeler, L. F.; Dias, W. R. A. (2024) “Análise do Desempenho Computacional de Algoritmos Paralelizados com OpenMP e MPI Executados em Raspberry Pi”. In Workshop de Iniciação Científica Simpósio em Sistemas Computacionais de Alto Desempenho (SSCAD), São Carlos, SP, Brasil, pp. 65-72.
Richardson, M.; Wallace, S. (2013) “Primeiros Passos com o Raspberry Pi”. São Paulo, Brasil: Novatec, 1 a edição, 192p.
Sedgewick, R. (1983) “Algorithms”. Addison-Wesley. 1 st edition, 552p.
Xavier, F.; Camargo, E. T.; Duarte Jr, E. (2019) “Uma Implementação MPI Tolerante a Falhas do Algoritmo Paralelo de Ordenação QuickMerge”. In Simpósio em Sistemas Computacionais de Alto Desempenho (SSCAD), Campo Grande, MS, Brasil, pp. 276-287.
Yue, Y. (2015) “Performance Evaluation of Sorting Algorithms in Raspberry Pi and Personal Computer”.
Masterís thesis for the degree of Master of Science in Technology, University of Vaasa - Faculty of Technology, 6 August, 78p.
Zaharia, M.; Chowdhury, M.; Franklin, M. J.; Shenker, S.; & Stoica, I. (2016) “Apache Spark: A Unified Engine for Big Data Processing”. In Communications of the ACM, 59(11):56-65, November.
Andrews, G. R. (2001) “Foundations of Multithreaded, Parallel, and Distributed Programming”. Boston, Massachusetts, EUA: Addison-Wesley, 2 nd edition, 664p.
Aung, H. H. (2019) “Analysis and Comparative of Sorting Algorithms”. In International Journal of Trend in Scientific Research and Development (IJTSRD), 3(5):1049-1053, August.
Chandra, R.; Dagum, L.; Kohr, D.; Maydan, D.; McDonald, J.; Menon, R. (2000) “Parallel Programming in OpenMP”. San Francisco, CA, USA: Morgan Kaufmann, 1 st edition, 240p.
Colichio, H.; Pimenta, Y.; Borges, P.; Menecucci, M.; Barros, L.; Guardia, H. (2024) “Ordenação Paralela com OpenMP e CUDA”. In Escola Regional de Alto Desempenho de São Paulo (ERAD-SP), Rio Claro, SP, Brasil, pp. 9-12.
Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C. (2012) “Algoritmos: Teoria e Prática”. GEN LTC, 3ª edição, 944p.
Google Cloud. (2025) “BigQuery: Managed Data Warehouse for Analytics”, disponível em [link]. Acessado em 03/06/2025.
Gropp, W.; Lusk, E.; Skjellum, A. (1994) “Using MPI: Portable Parallel Programming with the Message Passing Interface”. Cambridge, Massachusetts, EUA: MIT Press, 1 st edition, 307p.
Ignácio, A. L. J.; Dias, W. R. A. (2023) “Análise do Desempenho Computacional de Algoritmos Paralelizados com OpenMP e MPI Executados em Raspberry Pi”. In Workshop de Iniciação Científica - Simpósio em Sistemas Computacionais de Alto Desempenho (SSCAD), Porto Alegre, RS, Brasil, pp. 41-48.
Knuth, D. E. (1998) “The Art of Computer Programming, Volume 3: Sorting and Searching”. Addison-Wesley.
Lima, F. A.; Moreno, E. D.; Dias, W. R. A. (2016) “Performance Analysis of a Low Cost Cluster with Parallel Applications and ARM Processors”. In IEEE Latin America Transactions, 14(11):4591-4596, December.
Moore, G. E. (1965). “Cramming More Components onto Integrated Circuits”. In Electronics, 38(8):114-117.
Mpi, (2025) “A Message-Passing Interface Standard Version 2.1”, disponível em www.mpiforum.org/docs/mpi21-report.pdf. Acessado em 10/07/2025.
OpenMP, (2025) “The OpenMP API Specification for Parallel Programming”, disponível em [link]. Acessado em 12/07/2025.
Pacheco, P. S. (2011) “An Introduction to Parallel Programming”. Morgan Kaufmann Publishers, 1 st ed., 370p.
Parhami, B. (2006) “Introduction to Parallel Processing - Algorithms and Architectures”. New York, USA: Kluwer Academic Publishers, 1 st edition, 532p.
Rajagopal, D.; Thilakavalli, K. (2016) “Different Sorting Algorithm’s Comparison based Upon the Time Complexity”. In International Journal of u- and e-Service, Science and Technology, 9(8):287-296, November.
Rauber, T.; Rünger, G. (2013) “Parallel Programming for Multicore Cluster Systems”. Springer, 2 nd ed., 516p.
Ribeiro, G. O.; Sêmeler, L. F.; Dias, W. R. A. (2024) “Análise do Desempenho Computacional de Algoritmos Paralelizados com OpenMP e MPI Executados em Raspberry Pi”. In Workshop de Iniciação Científica Simpósio em Sistemas Computacionais de Alto Desempenho (SSCAD), São Carlos, SP, Brasil, pp. 65-72.
Richardson, M.; Wallace, S. (2013) “Primeiros Passos com o Raspberry Pi”. São Paulo, Brasil: Novatec, 1 a edição, 192p.
Sedgewick, R. (1983) “Algorithms”. Addison-Wesley. 1 st edition, 552p.
Xavier, F.; Camargo, E. T.; Duarte Jr, E. (2019) “Uma Implementação MPI Tolerante a Falhas do Algoritmo Paralelo de Ordenação QuickMerge”. In Simpósio em Sistemas Computacionais de Alto Desempenho (SSCAD), Campo Grande, MS, Brasil, pp. 276-287.
Yue, Y. (2015) “Performance Evaluation of Sorting Algorithms in Raspberry Pi and Personal Computer”.
Masterís thesis for the degree of Master of Science in Technology, University of Vaasa - Faculty of Technology, 6 August, 78p.
Zaharia, M.; Chowdhury, M.; Franklin, M. J.; Shenker, S.; & Stoica, I. (2016) “Apache Spark: A Unified Engine for Big Data Processing”. In Communications of the ACM, 59(11):56-65, November.
Publicado
28/10/2025
Como Citar
SILVA, Lucayan Felipe Teixeira da; DIAS, Wanderson Roger Azevedo.
Avaliação de Algoritmos de Ordenação de Dados em Ambiente de HPC com Raspberry Pi. In: WORKSHOP DE INICIAÇÃO CIENTÍFICA - SIMPÓSIO EM SISTEMAS COMPUTACIONAIS DE ALTO DESEMPENHO (SSCAD), 26. , 2025, Bonito/MS.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2025
.
p. 57-64.
DOI: https://doi.org/10.5753/sscad_estendido.2025.15942.
