Algoritmos BSP/CGM para Ordenação

• Ano de defesa: 2004
• Autor(a) principal: Gonda, Luciano
• Orientador(a): Mongelli, Henrique
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Palavras-chave em Português: Ordenação e Busca; Algoritmos Úteis e Específicos; Algoritmos e Estruturas de Dados; Programação Paralela
• Link de acesso: https://repositorio.ufms.br/handle/123456789/478

O problema de ordenação é um assunto bastante estudado em computação. Ordenar uma seqüência S = (a1, a2, . . . , an), consiste em obter uma seqüência S' = (a'1, a'2, . . . , a'n), onde a'i ≤ a'j , se i < j. A paralelização de problemas é utilizada para reduzir o tempo de execução dos problemas que necessitam de alto poder de processamento. Neste trabalho descreveremos três algoritmos de ordenação paralelos desenvolvidos no modelo BSP/CGM, no qual cada processador possui memória de tamanho O(n/p), e em cada rodada de comunicação são enviados ou recebidos, no Maximo, O(n/p) dados. Neste modelo queremos sempre minimizar o número de rodadas de comunicação. Os algoritmos que descreveremos são: Ordenação-Bitonica, Ordenação-CD e Ordenação-por-Divisão. O algoritmo Ordenação-Bitonica utiliza O(log p) rodadas de comunicação e tempo de computação local O(nlogn/p). Os algoritmos Ordenação-CD Ordenação-por-Divisão utilizam O(1) rodadas de comunicação e tempo de computação local O(nlogn/p). A implementação do algoritmo Ordenação-CD apresenta resultados muito bons em relação ao tempo de execução, mostrando que este algoritmo é eficiente se executado para entradas grandes. Segundo os resultados experimentais, o algoritmo Ordenação-CD é o que apresenta os melhores resultados para todas as entradas.