Uma Experiência de Implementação de Métodos de Ordenação Paralelos em Máquina SIMD - Carcenori, Rodrigo Lima; Meira Júnior, Wagner; Carvalho, Márcio Luiz Bunte de (Anais do International Symposium on Computer Architecture and High Performance Computing (SBAC-PAD); 1993: Anais do V Simpósio Brasileiro de Arquitetura de Computadores e Processamento de Alto Desempenho, 1993)
O presente trabalho baseia-se na implementação de três algoritmos de ordenação em uma máquina SIMD com 8K processadores de 1 bit. Os algoritmos implementados foram os seguintes: Odd-Even Transposition Sort, um híbrido composto a partir do Odd-Even e do Shellsort, e Linar Array Sort. Os testes realizados mostraram que o algoritmo híbrido é o mais eficiente, se o número de elementos a serem ordenados for relativamente elevado (maior que 4096). Em caso contrário, deve-se utilizar o Odd-Even. O algoritmo Linear Array apresentou um desempenho mais modesto, por ser mais flexível quanto à geração dos itens a serem ordenados. Adicionalmente, mostrou-se que uma duplicação do número de processadores virtuais utilizados permite, em geral, reduzir o tempo gasto na execução dos métodos estudados pela metade. Finalmente, constatou-se que a eliminação total do paralelismo pode provocar aumentos de até 100 vezes nos tempos de execução dos algoritmos em estudo.