Uma Experiência de Implementação de Métodos de Ordenação Paralelos em Máquina SIMD
Resumo
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.
Referências
M. Ajtai, J. Komlés, and E. Szmerédi. An O(n log n) sorting network. In Proceedings of the 15th ACM Annual Symposium on Theory of Computing, pp 1-9. New York, 1983.
D. E. Knuth. The art of computer programming, Vol. 3: Sorting and searching. Addison-Wesley Publishing Co., 1973.
F. T. Leighton, B. Maggs, and S, Rao. Universal packet routing algorithms, In Proceedings of the 29th Annual IEEE Symposium on Foundations of Computer Science, pp 256-269, 1988.
F. Albohassan, J. Keller, and D. Scherer. Optimal sorting in linear arrays with minimum global control. Preprint.
F. Abolhassan, J. Keller, and W. J. Paul. On the cost-effectiveness of PRAMs. In Proceedings of the 3rd IEEE Symposium on Parallel and Distributed Processing, pp 2-9, 1991.
R. S. Barr, and B. L. Hickman. Reporting computational experiments with parallel algorithms: issues, measures and experts' opinions. In ORSA Journal on Computing, Vol. 5, No. 1, pp 2-32, 1993.
