Patterns for Overlapping Communication and Computation

Parallel applications commonly face the problem of sitting idle while waiting for remote data to become available. Even for problems where plenty of parallelism is available and good load balance is achievable, performance may be disappointing if local work cannot be overlapped with communication. We describe three patterns for achieving the overlap of communication with computation: overdecomposition, non-blocking communication, and speculation.