Workshops Archive

Slicing Is All You Need: Towards A Universal One-Sided Algorithm for Distributed Matrix Multiplication

Workshop: The 8th Annual Parallel Applications Workshop: Alternatives To MPI+X (PAW-ATM 2025)

Authors: Benjamin Brock and Renato Golin (Intel Corporation)

Abstract: Science, data analytics, and AI workloads depend on distributed matrix multiplication. Prior work has developed an array of algorithms suitable for different problem sizes, partitionings, and replication factors. A limitation of existing algorithms is that they are limited to a subset of partitionings. Multiple algorithm implementations are required to support the full space of possible partitionings. If no algorithm implementation is available for a set of partitions, one or more operands must be redistributed, increasing communication overhead. We present a one-sided algorithm for distributed matrix multiplication supporting all combinations of partitionings and replication factors. Our algorithm uses index arithmetic to compute sets of overlapping tiles that must be multiplied together. This list of local matrix multiplies can then either be executed directly, or reordered and lowered to an optimized IR to maximize overlap. We implement our algorithm using a high-level C++-based PGAS programming framework, finding it competitive with state-of-the-art systems.

Back to The 8th Annual Parallel Applications Workshop: Alternatives To MPI+X (PAW-ATM 2025) Archive Listing Back to Full Workshop Archive Listing