Uma Experiência de Implementação de Métodos de Ordenação Paralelos em Máquina SIMD

  • Rodrigo Lima Carcenori UFMG
  • Wagner Meira Júnior UFMG
  • Márcio Luiz Bunte de Carvalho UFMG

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

WAVETRACER, Inc. The MultiC programming language - user documentation. Acton, Massachusetts, 1991.

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.
Publicado
07/09/1993
CARCENORI, Rodrigo Lima; MEIRA JÚNIOR, Wagner; CARVALHO, Márcio Luiz Bunte de. Uma Experiência de Implementação de Métodos de Ordenação Paralelos em Máquina SIMD. In: INTERNATIONAL SYMPOSIUM ON COMPUTER ARCHITECTURE AND HIGH PERFORMANCE COMPUTING (SBAC-PAD), 5. , 1993, Florianópolis/SC. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 1993 . p. 189-201. DOI: https://doi.org/10.5753/sbac-pad.1993.23032.