Space Filling Curves is All You Need: Communication-Avoiding Matrix Multiplication Made Simple

• URL: http://arxiv.org/abs/2601.16294v1
• Date: Thu, 22 Jan 2026 19:56:16 GMT
• Title: Space Filling Curves is All You Need: Communication-Avoiding Matrix Multiplication Made Simple
• Authors: Evangelos Georganas, Alexander Heinecke, Pradeep Dubey,
• Abstract summary: General Matrix multiplication is the cornerstone of Deep Learning and HPC workloads.<n>Modern platforms with matrix multiplication accelerators exhibit high FLOP/Byte machine balance.<n>In this work we revisit space filling curves (SFC) to alleviate the problem of this cumbersome tuning.<n>We obtain platform-oblivious and shape-oblivious matrix-multiplication schemes that exhibit inherently high degree of data locality.
• Score: 42.09057806159106
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: General Matrix Multiplication (GEMM) is the cornerstone of Deep Learning and HPC workloads; accordingly, academia and industry have heavily optimized this kernel. Modern platforms with matrix multiplication accelerators exhibit high FLOP/Byte machine balance, which makes implementing optimal matrix multiplication challenging. On modern CPU platforms with matrix engines, state-of-the-art vendor libraries tune input tensor layouts, parallelization schemes, and cache blocking to minimize data movement across the memory hierarchy and maximize throughput. However, the best settings for these parameters depend strongly on the target platform (number of cores, memory hierarchy, cache sizes) and on the shapes of the matrices, making exhaustive tuning infeasible; in practice this leads to performance "glass jaws". In this work we revisit space filling curves (SFC) to alleviate the problem of this cumbersome tuning. SFC convert multi-dimensional coordinates (e.g. 2D) into a single dimension (1D), keeping nearby points in the high-dimensional space close in the 1D order. We partition the Matrix Multiplication computation space using recent advancements in generalized SFC (Generalized Hilbert Curves), and we obtain platform-oblivious and shape-oblivious matrix-multiplication schemes that exhibit inherently high degree of data locality. Furthermore, we extend the SFC-based work partitioning to implement Communication-Avoiding (CA) algorithms that replicate the input tensors and provably minimize communication/data-movement on the critical path. The integration of CA-algorithms is seamless and yields compact code (~30 LOC), yet it achieves state-of-the-art results on multiple CPU platforms, outperforming vendor libraries by up to 2x(geometric-mean speedup) for a range of GEMM shapes.

Related papers

• GSPN-2: Efficient Parallel Sequence Modeling [101.33780567131716]
  Generalized Spatial Propagation Network (GSPN) addresses this by replacing quadratic self-attention with a line-scan propagation scheme.<n>GSPN-2 establishes a new efficiency frontier for modeling global spatial context in vision applications.
  arXiv  Detail & Related papers  (2025-11-28T07:26:45Z)
• AIRES: Accelerating Out-of-Core GCNs via Algorithm-System Co-Design [6.554916179445241]
  Graph convolutional networks (GCNs) are fundamental in various scientific applications, ranging from biomedical protein-protein interactions (PPI) to large-scale recommendation systems.<n>An essential component for modeling graph structures in GCNs is sparse general matrix-matrix multiplication (SpGEMM)<n>SpGEMMs are often conducted in an out-of-core fashion due to limited GPU memory space in resource-constrained systems.<n>We propose AIRES, a novel algorithm-system co-design solution to accelerate out-of-core SpGEMM computation for GCNs.
  arXiv  Detail & Related papers  (2025-07-02T00:35:43Z)
• Libra: Synergizing CUDA and Tensor Cores for High-Performance Sparse Matrix Multiplication [6.557224606759151]
  Modern accelerators are commonly equipped with cores and cores to accelerate sparse operators.<n>We show that utilizing one resource alone leads to inferior performance for sparse matrix multiplication, due to their respective limitations.<n>We propose a 2D-aware workload computation strategy find out the sweet point of task mapping operators, leveraging both the high performance of 2.9 cores and the low redundancy on cores.
  arXiv  Detail & Related papers  (2025-06-28T01:50:13Z)
• Orthogonal Finetuning Made Scalable [92.34573849209238]
  Orthogonal finetuning (OFT) offers highly parameter-efficient adaptation while preventing catastrophic forgetting, but its high runtime and memory demands limit practical deployment.<n>We identify the core computational bottleneck in OFT as its weight-centric implementation, which relies on costly matrix-matrix multiplications with cubic complexity.<n>We propose OFTv2, an input-centric reformulation that instead uses matrix-vector multiplications (i.e., matrix-free computation), reducing the computational cost to quadratic.<n>These modifications allow OFTv2 to achieve up to 10x faster training and 3x lower GPU memory usage without
  arXiv  Detail & Related papers  (2025-06-24T17:59:49Z)
• FFT-based Dynamic Subspace Selection for Low-Rank Adaptive Optimization of Large Language Models [49.397861654088636]
  We propose a two-step procedure to approximate SVD/QR-based gradient projections into lower-dimensional spaces.<n>We show that our strategy achieves faster runtime and reduced memory usage by up to $25%$ across different model sizes.
  arXiv  Detail & Related papers  (2025-05-23T14:37:00Z)
• VIRGOS: Secure Graph Convolutional Network on Vertically Split Data from Sparse Matrix Decomposition [10.972364935510152]
  Graph convolutional networks (GCNs) are critical for applying their analytical capabilities to privacy-sensitive data like social/credit networks.<n>Multiplying a sparse yet large adjacency matrix of a graph in GCN--a core operation in training/inference--poses a performance bottleneck in secure GCNs.<n>We propose a co-design secure multi-party computation (MPC) with matrix sparsity.
  arXiv  Detail & Related papers  (2025-02-13T22:54:27Z)
• SMM-Conv: Scalar Matrix Multiplication with Zero Packing for Accelerated Convolution [4.14360329494344]
  We present a novel approach for accelerating convolutions during inference for CPU-based architectures. Our experiments with commonly used network architectures demonstrate a significant speedup compared to existing indirect methods.
  arXiv  Detail & Related papers  (2024-11-23T21:43:38Z)
• Monarch: Expressive Structured Matrices for Efficient and Accurate Training [64.6871423399431]
  Large neural networks excel in many domains, but they are expensive to train and fine-tune. A popular approach to reduce their compute or memory requirements is to replace dense weight matrices with structured ones. We propose a class of matrices (Monarch) that is hardware-efficient.
  arXiv  Detail & Related papers  (2022-04-01T17:37:29Z)
• SKIing on Simplices: Kernel Interpolation on the Permutohedral Lattice for Scalable Gaussian Processes [39.821400341226315]
  Structured Kernel Interpolation (SKI) framework is used to perform efficient matrix vector multiplies (MVMs) on a grid. We develop a connection between SKI and the permutohedral lattice used for high-dimensional fast bilateral filtering. Using a sparse simplicial grid instead of a dense rectangular one, we can perform GP inference exponentially faster in the dimension than SKI. We additionally provide a implementation of Simplex-GP, which enables significant acceleration of MVM based inference.
  arXiv  Detail & Related papers  (2021-06-12T06:04:56Z)
• VersaGNN: a Versatile accelerator for Graph neural networks [81.1667080640009]
  We propose textitVersaGNN, an ultra-efficient, systolic-array-based versatile hardware accelerator. textitVersaGNN achieves on average 3712$times$ speedup with 1301.25$times$ energy reduction on CPU, and 35.4$times$ speedup with 17.66$times$ energy reduction on GPU.
  arXiv  Detail & Related papers  (2021-05-04T04:10:48Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.