Overlapping computations and communications in torus networks

Abstract

A fundamental aspect in the design of parallel applications consists 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, on to 2D or 1D 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 the PEs (processing elements) that makes overlapping computations and communications possible. To start with, we obtain parallel algorithms with a number of processes that is 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.