Uma Implementação MPI Tolerante a Falhas do Algoritmo Paralelo de Ordenação Quickmerge

  • Felipe Xavier Universidade Tecnológica Federal do Paraná
  • Edson Tavares Camargo Universidade Tecnológica Federal do Paraná
  • Elias Duarte Jr

Resumo


O algoritmo de ordenação paralelo Quickmerge combina a estratégia do algoritmo Quicksort com operações de fusão de subconjuntos criados a partir de elementos chaves, chamados pivôs. Duas versões do algoritmo Quickmerge que executam sobre o hipercubo foram encontradas na literatura, porém nenhuma considera falhas de processos. Este trabalho apresenta uma implementação MPI tolerante a falhas dos algoritmos Quickmerge e Quickmerge Modificado na topologia virtual denominada VCube. Os algoritmos propostos são capazes de executar a ordenação mesmo que todos menos um processo falhem. Os algoritmos são comparados a uma implementação tolerante a falhas do algoritmo paralelo Hyperquicksort. Resultados mostram a eficiência da implementação na ordenação de até 1 bilhão de números inteiros em cenários com e sem falhas.

Referências

Ashraf, R. A., Hukerikar, S., and Engelmann, C. (2018). Shrink or substitute: Handling process failures in HPC systems using in-situ recovery. In Euromicro Int. Conference on Parallel, Distributed and Network-based Processing (PDP), pages 178–185.

Bland, W., Bouteiller, A., Hérault, T., Bosilca, G., and Dongarra, J. (2013). Post-failure recovery of MPI communication capability: Design and rationale. International Journal of HPC Applications, 27(3):244–254.

Camargo, E. T. and Duarte, Jr., E. (2016). Uma implementação MPI tolerante a falhas do algoritmo hyperquicksort. In Simp. Brasileiro de Redes de Computadores e Sistemas Distribuı́dos (SBRC) 2016 - Workshop de Tolerância a Falhas.

Camargo, E. T. d. and Duarte, Jr., E. P. (2017). Minicurso v: Técnicas para a construção de sistemas MPI tolerantes a falhas. In Minicurso do Simpósio de Sistemas Computacionais de Alto Desempenho (WSCAD) 2017.

Camargo, E. T. d. and Duarte, Jr., E. P. (2018). Running resilient MPI applications on a dynamic group of recommended processes. J. of the Brazilian Comp. Society, 24(1):5.

Duarte, E. P., Bona, L. C. E., and Ruoso, V. K. (2014). Vcube: A provably scalable distributed diagnosis algorithm. In 2014 5th Workshop on Latest Advances in Scalable Algorithms for Large-Scale Systems, pages 17–22.

Evans, D. (1990). A parallel sorting - merging algorithm for tightly coupled multiprocessors. Parallel Computing, 14(1):111 – 121.

Forum, M. (2015). Document for a standard message-passing interface 3.1. Technical report, University of Tennessee, http://www.mpi-forum.org/docs/mpi-3.1.

Forum, M. (2019). MPI forum website. http://mpi-forum.org/. Em 23/07/2019.

Freiling, F. C., Guerraoui, R., and Kuznetsov, P. (2011). The failure detector abstraction. ACM Comput. Surv., 43(2):9:1–9:40.

Gamell, M., Teranishi, K., Mayo, J., Kolla, H., Heroux, M. A., Chen, J., and Parashar, M. (2017). Modeling and simulating multiple failure masking enabled by local recovery for stencil-based applications at extreme scales. IEEE Transactions on Parallel and Distributed Systems, 28(10):2881–2895.

MPI-Forum (2019). User-level failure mitigation. https://bitbucket.org/icldistcomp/ulfm/. Acessado em 26/02/2019.

mpich.org (2017). High-performance portable mpi. http://www.mpich.org/. Acessado em 23/07/2019.

Parhami, B. (1999). Introduction to Parallel Processing: Algorithms and Architectures. Kluwer Academic Publishers, Norwell, MA, USA.

Quinn, M. J. (1988). Parallel sorting algorithms for tightly coupled multiprocessors. Parallel Computing, 6(3):349 – 357.

Quinn, M. J. (1989). Analysis and benchmarking of two parallel sorting algorithms: Hyperquicksort and quickmerge. BIT Numerical Mathematics, 29(2):239–250.

Shahzad, F., Thies, J., Kreutzer, M., Zeiser, T., Hager, G., and Wellein, G. (2019). Craft: A library for easier application-level checkpoint/restart and automatic fault tolerance. IEEE Transactions on Parallel and Distributed Systems, 30(3):501–514.

Shi, H. and Schaeffer, J. (1992). Parallel sorting by regular sampling. Journal of Parallel and Distributed Computing, 14(4):361 – 372.

Träff, J. L. (2018) Parallel quicksort without pairwise element exchange. CoRR, abs/1804.07494.

Wagar, B. (1987). Hyperquicksort: A fast sorting algorithm for hypercubes. Hypercube Multiprocessors, 1987:292–299.
Publicado
08/11/2019
XAVIER, Felipe; CAMARGO, Edson Tavares; DUARTE JR, Elias. Uma Implementação MPI Tolerante a Falhas do Algoritmo Paralelo de Ordenação Quickmerge. In: SIMPÓSIO EM SISTEMAS COMPUTACIONAIS DE ALTO DESEMPENHO (SSCAD), 20. , 2019, Campo Grande. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2019 . p. 276-287. DOI: https://doi.org/10.5753/wscad.2019.8675.