A Model for Multi-Grained Parallelism y

Multi-grained parallel computers can be very eective on computationally intensive problems that have important serial and parallel components. We examine the Mesh Su-perHet, a model of this type consisting of the close coupling of a d-dimensional toroidal mesh of coarse-grained processors to a serial machine containing memory modules con-nected via a low-diameter network to a fast serial processor. We exhibit problems for which the Mesh SuperHet is superior to its serial or parallel components alone and develop tight performance bounds for sorting, the fast Fourier transform, and matrix multiplication. As multi-grained machines become more common, studies such as this will both reveal the fundamental limitations on such architectures and set the context for algorithm development.