Performance Analysis of Bulk Synchronous Parallel Algorithms
Resumo
In the last few years, there has been considerable interest in general purpose computational models of parallel computation to permit independent development of hardware and software. The BSP and related models represent an important step in this direction. This paper presents a methodology for the performance analysis of bulk synchronous parallel algorithms based on parameters which reflect the two-level memory hierarchy advocated by these models. A parallel sorting algorithm is taken as a case study where it is shown a close agreement between theoretical and experimental results.
Referências
Culler, D., Karp R., Patterson, D., Sahay, A., Schauser, K., Santos, E., Subramonian, R. and vonEicken, T. "LogP: Towards a Realistic Model of Parallel Computation". In Proceedings of the 4th ACM SIGPLAN Symposium on Principies and Practice of Parallel Programming PPOPP, San Diego, California, volume 28, pages 19-22, ACM Press, may 1993.
Francis, R. S. and Mathieson, I. D. "A Benchmark Parallel Sort for Shared Memory Multiprocessors", IEEE Transactions on Computers, Vol. 37, No. 12, pp. 1619-1626, December 1988.
McColl, W. F. "General purpose parallel computing". In A. M. Gibbons and P. Spirakis editors, Lectures on Parallel Computation. Proc. 1991 ALCOM Spring School on Parallel Computation, volume 4 of Cambridge International Series on Parallel Computation, pages 337-391. Cambridge University Press, Cambridge, UK, 1993.
Nash, J. M. and Dew, P. "Parallel Algorithm Design on the XPRAM model". In Proceedings of the 2nd Abstract machines Workshop, Leeds, 1993.
Nash, J. M., Dyer, M. E. and Dew, P. "Designing Practical Parallel Algorithms for Scalable Message Passing Machines". In Proceedings of the 1995 World Transputter Congress, pages 529-541, September 1995.
Nash, J. M. "A study of the XPRAM Model for Parallel Computing", PhD Thesis, University of Leeds, 1993.
Dowsing, R. D. and Martins, W. S. "Performance of a Selection of Sorting Algorithms on a General Purpose Parallel Computer", To appear in Concurrency: Practice and Experience.
Valiant, L. G. "General Purpose Parallel Architectures". In tire Handbook of Theoretical Computer Science, J. van Leeuwen, Ed. North Holland 1990, pp. 944971.
Valiant, L. G. "A Bridging Model for Parallel Computation", Communications of ACM, pp. 103-111, August 1990.
Francis, R. S. and Mathieson, I. D. "A Benchmark Parallel Sort for Shared Memory Multiprocessors", IEEE Transactions on Computers, Vol. 37, No. 12, pp. 1619-1626, December 1988.
McColl, W. F. "General purpose parallel computing". In A. M. Gibbons and P. Spirakis editors, Lectures on Parallel Computation. Proc. 1991 ALCOM Spring School on Parallel Computation, volume 4 of Cambridge International Series on Parallel Computation, pages 337-391. Cambridge University Press, Cambridge, UK, 1993.
Nash, J. M. and Dew, P. "Parallel Algorithm Design on the XPRAM model". In Proceedings of the 2nd Abstract machines Workshop, Leeds, 1993.
Nash, J. M., Dyer, M. E. and Dew, P. "Designing Practical Parallel Algorithms for Scalable Message Passing Machines". In Proceedings of the 1995 World Transputter Congress, pages 529-541, September 1995.
Nash, J. M. "A study of the XPRAM Model for Parallel Computing", PhD Thesis, University of Leeds, 1993.
Dowsing, R. D. and Martins, W. S. "Performance of a Selection of Sorting Algorithms on a General Purpose Parallel Computer", To appear in Concurrency: Practice and Experience.
Valiant, L. G. "General Purpose Parallel Architectures". In tire Handbook of Theoretical Computer Science, J. van Leeuwen, Ed. North Holland 1990, pp. 944971.
Valiant, L. G. "A Bridging Model for Parallel Computation", Communications of ACM, pp. 103-111, August 1990.
Publicado
04/08/1996
Como Citar
MARTINS, Wellington Santos.
Performance Analysis of Bulk Synchronous Parallel Algorithms. In: INTERNATIONAL SYMPOSIUM ON COMPUTER ARCHITECTURE AND HIGH PERFORMANCE COMPUTING (SBAC-PAD), 8. , 1996, Recife.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
1996
.
p. 11-20.
DOI: https://doi.org/10.5753/sbac-pad.1996.19810.
