Uma Implementação MPI Tolerante a Falhas do Algoritmo Paralelo de Ordenação Quickmerge - Xavier, Felipe; Camargo, Edson Tavares; Duarte Jr, Elias (Anais do Simpósio em Sistemas Computacionais de Alto Desempenho (SSCAD); 2019: Anais do XX Simpósio em Sistemas Computacionais de Alto DesempenhoDO - 10.5753/wscad.2019.8675, 2019)
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.