4th Euromicro Workshop on Parallel and Distributed Processing (PDP '96)
Overlapping Computations and Communications in Torus Networks
PORTUGAL
January 24-January 26
ISBN: 0-8186-7376-1
A fundamental aspect in the design of parallel applications consist in minimizing communications: reducing the number of messages or overlapping computations and communications. The objective of this paper is the design of parallel algorithms that use processors and expensive resources such as communications efficiently. We present a partial embedding of computation and communication graphs that have a cubic or planar structure, onto 2-D or 1-D torus graphs. With this embedding good values for normal embedding metrics are obtained, and its advantage is that it allows an initial data distribution between PEs (Processing Elements) that makes overlapping computations and communications possible. To start with we obtain parallel algorithms with a number of processes dependent on the number of processors in the torus. Then we modify the embedding in order to execute problems with matrices whose size is independent of the number of processors of the torus multicomputer.