Abstract
The design of efficient parallel algorithms in a message-based, distributed-memory multiprocessor system should consider both time-space tradeoffs and computation-communication tradeoffs. A generic model of distributed hypercube multiprocessors is introduced to characterize those important parameters that would affect the performance of algorithms. To implement a good data-parallel algorithm on the hypercube multiprocessor, one has to consider the number of processors required, an efficient way to partition the data, and an efficient way to map partitions into processors. Two simple examples, array summation and matrix multiplication, are used to demonstrate various techniques to solve these problems. An analysis based on the proposed model is presented.