Scientific computing on bulk synchronous parallel architectures

Abstract

Bulk synchronous parallel architectures oer the prospect of achieving both scalable parallel performance and architecture independent parallel software. They provide a robust model on which to base the future development of general purpose parallel computing systems. In this paper, we theoretically and experimentally analyse the eciency with which a wide range of important scientic computations can be performed on bulk synchronous parallel architectures. The computations considered include the iterative solution of sparse linear systems, molecular dynamics, and the solution of partial dierential equations on a multidimensional discrete grid. We analyse these computations in a uniform manner by formulating their basic procedures as a sparse matrix-vector multiplication.