# Red-blue pebbling revisited: near optimal parallel matrix-matrix multiplication

arXiv: https://arxiv.org/abs/1908.09606 · HTML: https://mlsanity.com/paper/1908.09606/

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Aug 2019.

## Built on by (most cited first, 21 of 21)

- [Chimera: Efficiently Training Large-Scale Neural Networks with Bidirectional Pipelines](https://mlsanity.com/paper/2107.06925/) (2021)
- [Parallel and Distributed Graph Neural Networks: An In-Depth Concurrency Analysis](https://mlsanity.com/paper/2205.09702/) (2022)
- [Improving Parallel Program Performance with LLM Optimizers via Agent-System Interfaces](https://mlsanity.com/paper/2410.15625/) (2024)
- [GraphMineSuite: Enabling High-Performance and Programmable Graph Mining Algorithms with Set Algebra](https://mlsanity.com/paper/2103.03653/) (2021)
- [HammingMesh: A Network Topology for Large-Scale Deep Learning](https://mlsanity.com/paper/2209.01346/) (2022)
- [PipeOptim: Ensuring Effective 1F1B Schedule with Optimizer-Dependent Weight Prediction](https://mlsanity.com/paper/2312.00839/) (2023)
- [Demystifying Higher-Order Graph Neural Networks](https://mlsanity.com/paper/2406.12841/) (2024)
- [Distributed-Memory Sparse Kernels for Machine Learning](https://mlsanity.com/paper/2203.07673/) (2022)
- [SINGA-Easy: An Easy-to-Use Framework for MultiModal Analysis](https://mlsanity.com/paper/2108.02572/) (2021)
- [VisualTextRank: Unsupervised Graph-based Content Extraction for Automating Ad Text to Image Search](https://mlsanity.com/paper/2108.02725/) (2021)
- [Text is NOT Enough: Integrating Visual Impressions into Open-domain Dialogue Generation](https://mlsanity.com/paper/2109.05778/) (2021)
- [Discovering Personalized Semantics for Soft Attributes in Recommender Systems using Concept Activation Vectors](https://mlsanity.com/paper/2202.02830/) (2022)
- [Reinforced MOOCs Concept Recommendation in Heterogeneous Information Networks](https://mlsanity.com/paper/2203.11011/) (2022)
- [Explanation-Guided Fairness Testing through Genetic Algorithm](https://mlsanity.com/paper/2205.08335/) (2022)
- [Using Graph Neural Networks for Program Termination](https://mlsanity.com/paper/2207.14648/) (2022)
- [Tribe or Not? Critical Inspection of Group Differences Using TribalGram](https://mlsanity.com/paper/2303.09664/) (2023)
- [Slicing Is All You Need: Towards A Universal One-Sided Algorithm for Distributed Matrix Multiplication](https://mlsanity.com/paper/2510.08874/) (2025)
- [Space Filling Curves is All You Need: Communication-Avoiding Matrix Multiplication Made Simple](https://mlsanity.com/paper/2601.16294/) (2026)
- [Communication-Avoiding Linear Algebraic Kernel K-Means on GPUs](https://mlsanity.com/paper/2601.17136/) (2026)
- [Approaching I/O-optimality for Approximate Attention](https://mlsanity.com/paper/2605.23751/) (2026)
- [Maia 200: A Software Defined Dataflow System for Large-scale AI Acceleration](https://mlsanity.com/paper/2608.24664/) (2026)

## Abstract (arXiv)

We propose COSMA: a parallel matrix-matrix multiplication algorithm that is near communication-optimal for all combinations of matrix dimensions, processor counts, and memory sizes. The key idea behind COSMA is to derive an optimal (up to a factor of 0.03% for 10MB of fast memory) sequential schedule and then parallelize it, preserving I/O optimality. To achieve this, we use the red-blue pebble game to precisely model MMM dependencies and derive a constructive and tight sequential and parallel I/O lower bound proofs. Compared to 2D or 3D algorithms, which fix processor decomposition upfront and then map it to the matrix dimensions, it reduces communication volume by up to √3 times. COSMA outperforms the established ScaLAPACK, CARMA, and CTF algorithms in all scenarios up to 12.8x (2.2x on average), achieving up to 88% of Piz Daint's peak performance. Our work does not require any hand tuning and is maintained as an open source implementation.