Brief Announcement: Optimality Conditions for Parallel Communication-Avoiding Matrix Multiplication with Overlapped Communication

When considering general matrix multiply (GEMM) algorithms for distributed-memory systems, the dominant paradigm is to minimize communication volume. However, to minimize time, one must consider how communication volume interacts with the system characteristics --- namely, communication bandwidth, memory capacity, and the co-scheduling of computation and communication. In this work, we demonstrate that the family of 3D GEMM algorithms --- although reducing overall communication by leveraging extra memory --- fundamentally concentrates communication to the phase of memory filling. This upfront cost hinders the ability to overlap communication with computation, and, consequently, calls for a revised view of the GEMM optimality regions. Our main contribution is derivation of optimality conditions for parallel matrix multiplication that jointly accounts for communication volume and overlap effects, pushing the 3D GEMM optimality region to start with the systems more than 11× larger than previously believed.