Tech Report CS-93-19

Limits on Heterogeneous Supercomputing

John E. Savage

May 1993

Abstract:

Heterogeneous supercomputers, machines that couple traditional serial and parallel supercomputers via high-bandwidth channels offer much higher performance than can be achieved with either type of machine alone. In this paper we define and analyze the capabilities of the Mesh SuperHet, a heterogeneous supercomputer consisting of a serial front end and a $d$-dimensional toroidal mesh of coarse-grained parallel processors connected by a high-bandwidth channel. The channel consists of connections between individual front-end memory modules and processors on one face of the mesh. All processors and memory units operate at the same speed. We examine sorting, the fast Fourier transform, and matrix multiplication on this machine and show that, for large problems, matrix multiplication can achieve a full speedup but sorting and the FFT are limited to a speedup of approximately $p^{1-1/d} \log (mp)$ which can be achieved, where $p$ is the number of parallel processors and $m$ is the amount of memory per parallel processor. As heterogeneous supercomputers become more common, studies such as this will both reveal fundamental limitations on such architectures and set the context for algorithm development.

(complete text in pdf or gzipped postscript)