On the Utility of Communication-Computation Overlap in Data-Parallel Programs

The computational speed of individual processors in distributed memory computers is increasing faster than the communication speed of the interconnection networks. This has led to the general perception among developers of compilers for data-parallel languages that overlapping communications with computations is an important optimization. We demonstrate that communication-computation overlap has limited utility. Overlapping communications with computations can never more than double the speed of a parallel application, and in practice the relative improvement in speed is usually far less than that. Most parallel algorithms have computational requirements that grow faster than their communication requirements. When this is the case, the gain from communication-computation overlap asymptotically approaches zero as the problem size increases. List of Symbols fi: Greek beta : Greek lambda \Omega : Greek Omega 2: Greek Theta A: Ay B: Bee C: See C o : See sub oh C r : See sub are ..