Uma Implementação de Algoritmos BSP/CGM de Ordenação
Resumo
Neste trabalho descrevemos três algoritmos paralelos de ordenação: Ordenação_Bitônica, Ordenação_CD e Ordenação_Divisão, desenvolvidos no modelo CGM e suas respectivas implementações. No CGM, cada processador possui memória local de tamanho O(n/p) e em cada rodada de comunicação cada processador pode enviar ou receber O(n/p) dados, onde n é o tamanho da entrada e p é o número de processadores utilizados. O algoritmo Ordenação_Bitônica utiliza O(log p) rodadas de comunicação e tempo de computação local O(n log n/p) e sua implementação apresenta um bom desempenho em relação ao algoritmo seqüencial. Além disso, não foi encontrada nenhuma outra implementação deste algoritmo no modelo CGM e este algoritmo pode ser utilizado em ordenação externa. Os algoritmos Ordenação_CD e Ordenação_Divisão utilizam O(1) rodadas de comunicação e tempo de computação local O(n log n/p). Entretanto, o algoritmo Ordenação_ CO apresenta um desempenho um pouco melhor. A implementação do deste algoritmo apresenta resultados muito bons em relação ao tempo de execução, mostrando que este algoritmo é eficiente se executado para tamanhos de entradas grandes.
Referências
A. Chan and F. Dehne. A note on coarsed grained parallel integer sorting. In Parallel Processing Leuer, volume 9, pages 533-538, 1999.
E. N. Cáceres, H. Mongelli, and S. W. Song. Algoritmos Paralelos Usando CGM/PVM: Uma lntrodução, pages 219-278. XXI Congresso da Sociedade Brasileira de Computação, Julho 2001.
F. Dehne, A. Fabri, and A. Rau-Chaplin. Scalable parallel computational geometry for coarse grained multicomputers. In Proceedings of the ACM 9th Anual Computational Geometry, pages 298-307, 1993.
F. Dehne, A. Ferreira, E. N. Cáceres, S. W. Song, and A. Roncato. Efficient parallel graph algorithms for coarsed grained multicomputers and BSP. Algorithmica, 33:183- 200, 2002.
A. Ferreira. Discrete computing with PC clusters: an algorithmic approach. Tutorial, International School on Advanced Algorithmic Techniques for Parallel Computation with Applications, Setembro 1999.
L. Gonda. Algoritmos BSP/CGM para ordenação. Master's thesis, Universidade Federal de Mato Grosso do Sul, Agosto 2004.
D. E. Knuth. The Art of Computer Programming, volume 3. Addison-Wesley Publishing Company, 1973.
L. G. Valiant. A bridging model for parallel computation. Communications of the ACM, 33:103-111, 1990.
B. Wilkinson and M. Allen. Parallel Programming- Techniques and Applications Using Networked Workstations and Parallel Computers. Prentice Hall, 1999.
