Palabras clave
Ordenamiento paralelo
Cómo citar
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
Knuth, D. E. (1997). The art of computer programming, volume 3: Sorting and searching (2nd ed.). Addison–Wesley.
Katajainen, J., & Träff, J. L. (1997). Algorithms and complexity. In Proceedings of the 3rd Italian Conference on Algorithms and Complexity.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to algorithms (3rd. ed.). The MIT Press.
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
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).
Duvanenko, V. (2011). Parallel merge sort. https://duvanenko.tech.blog/2018/01/13/parallel-merge-sort/
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
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
Esta obra está bajo una licencia internacional Creative Commons Atribución-NoComercial 4.0.
Derechos de autor 2025 José Eduardo Solsona, Sergio Nesmachnow