ACI Avances en Ciencias e Ingenierías

Artículos

Vol. 17 Núm. 1 (2025)

Evaluación empírica de implementaciones paralelas de MergeSort

Enviado
November 20, 2024
Publicado
2025-05-08

Resumen

Los algoritmos de ordenación son una pieza fundamental en el desarrollo de sistemas informáticos. MergeSort es un conocido algoritmo de ordenación, muy apreciado por su eficiencia, relativa simplicidad y otras características. Este artículo presenta una evaluación empírica de versiones paralelas de MergeSort, aplicando memoria compartida y distribuida, en una infraestructura informática de alto rendimiento. El principal resultado indica que la paralelización de invocaciones recursivas combinada con una operación de fusión paralela ofrece un mayor aumento de velocidad que la mera paralelización de invocaciones recursivas. Además, en un entorno de memoria compartida se consigue una mayor aceleración.

 

Referencias

  1. Knuth, D. E. (1997). The art of computer programming, volume 3: Sorting and searching (2nd ed.). Addison–Wesley.
  2. Katajainen, J., & Träff, J. L. (1997). Algorithms and complexity. In Proceedings of the 3rd Italian Conference on Algorithms and Complexity.
  3. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to algorithms (3rd. ed.). The MIT Press.
  4. Rolfe, T. J. (2010). A specimen of parallel programming: Parallel merge sort implementation. ACM Inroads, 1(4), 72–79. http://doi.org/10.1145/1869746.1869767
  5. Radenski, A. (2011). Shared memory, message passing, and hybrid merge sorts for standalone and clustered SMPs. In Proceedings of the 2011 International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA’11) (pp. 367–373).
  6. Duvanenko, V. (2011). Parallel merge sort. https://duvanenko.tech.blog/2018/01/13/parallel-merge-sort/
  7. Axtmann, M., Bingmann, T., Sanders, P., & Schulz, C. (2015). Practical massively parallel sorting. In Proceedings of the 27th ACM symposium on Parallelism in Algorithms and Architectures (pp. 13–23). https://doi.org/10.1145/2755573.2755595
  8. Nesmachnow, S., & Iturriaga, S. (2019). Cluster-UY: Collaborative scientific high performance computing in Uruguay. In M. Torres & J. Klapp (Eds.), Supercomputing (pp. 188–202). Springer. https://doi.org/10.1007/978-3-030-38043- 4_16

Descargas

Los datos de descarga todavía no están disponibles.