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 in terconnection networks. This has led to the general perception among d evelopers of compilers for data-parallel languages that overlapping co mmunications with computations is an important optimization. We demons trate that communication-computation overlap has limited utility. Over lapping communications with computations can never more than double th e speed of a parallel application, and in practice the relative improv ement in speed is usually far less than that. Most parallel algorithms have computational requirements that grow faster than their communica tion requirements. When this is the case, the gain from communication- computation overlap asymptotically approaches zero as the problem size increases. (C) 1996 Academic Press, Inc.