Tamanho da fonte:
Uma implementação MPI tolerante a falhas do algoritmo de ordenação paralela Quickmerge
Última alteração: 2019-02-04
Resumo
Um dos problemas mais frequentes em computação é a ordenação de dados. Os algoritmos de ordenação resolvem o problema da ordenação de forma sequencial ou paralela. A versão paralela se destaca por ordenar uma sequência grande de elementos em tempo de execução menor. Para tanto, o problema é dividido em partes menores e distribuído para um conjunto de nodos ou processos computacionais. Cada processo é responsável por resolver parte do problema. Este trabalho apresenta os esforços iniciais na obtenção de uma implementação tolerante a falhas do algoritmo de ordenação paralela chamado Quickmerge no modelo de memória distribuída. O algoritmo Quickmerge é uma versão paralela do algoritmo Quicksort e destaca-se por utilizar a topologia de uma hipercubo virtual para organizar os processos. A implementação foi realizada usando o padrão MPI. O MPI é o principal padrão para o desenvolvimento de aplicações paralelas e distribuídas que fazem uso do paradigma de troca de mensagens. No entanto, o padrão não tolera falhas de processos. São apresentados resultados preliminares de desempenho do algoritmo implementado e um estudo das estratégias para transformá-lo em uma versão tolerante a falhas.
Palavras-chave
Ordenação de dados. Quickmerge. Message Passing Interface (MPI). Quicksort. Tolerância a falhas.
Texto completo:
PDF