Algoritmos BSP/CGM para Ordenação - Gonda, Luciano (2004)
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.