Uma Experiência de Implementação de Métodos de Ordenação Paralelos em Máquina SIMD
Abstract
This work describes the implementation of three sorting algorithms on a SIMD machine with SK processors of 1 bit each. These algorithms are: Odd-Even Transposition Sort, a hybrid composed by Odd-Even and Shellsort, and Linear Array Sort. The tests performed have shown that, since the number of items to be sorted is relatively large (greater than 4096), the hybrid algorithm is the most efficient. Otherwise, Odd-Even must be used, Linear Array has been the one which performed worst, due to its greater flexibility with relation to the generation of the items to be sorted. In addition, it was shown that doubling the number of virtual processors used, generally reduces the execution time of these sorting methods by 50%. Finally, it was found that eliminating the parallelism at all can cause the running times of the algorithnis in study to be increased by a factor of down to 100.
References
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.
