The Impact of Application´s Micro-Imbalance on the Communication-Computation Overlap

Although the community sees overlapping communication and computation as a perspective avenue for advancing parallel execution, it remains unclear what type of applications, under which conditions, and to which extent could benefit from this technique. To tackle this issue, we designed a simulation environment that allowed us to profoundly study overlap. We found out that overlapping potential in an application is determined by the application´s parallel behavior and the pattern by which each process locally produces/consumes data involved in communication. We identified two behaviors that directly influence the application´s overlapping potential - we name them microscopic imbalance of computation and microscopic imbalance of communication. In an application that expresses some of these two behaviors, a fine-grain overlapping technique can achieve a significant execution speedup, a speedup that can even be higher than 2. We believe that our findings can help a programmer estimate how much his application could benefit from overlap, and therefore decide whether implementing that technique is worth the effort.