Shape-Aware Optimization for Non-Square Matrix Operations

59 concepts33 papers

For decades, high-performance linear algebra libraries have operated under a foundational assumption: the ideal matrix is a large, balanced square. Standard General Matrix Multiplication (GEMM) routines in legacy BLAS libraries are meticulously engineered around this assumption, maximizing hardware occupancy by slicing matrices into uniform, square tiles that perfectly fit hierarchical processor caches.

However, modern computational workloads—most notably deep learning and specialized scientific simulations—frequently break this symmetry. Neural network layers, transformer attention mechanisms, and algorithmic transformations regularly produce "ill-shaped" matrices. These operands are often extremely tall-and-skinny, short-and-wide, or highly asymmetric.

When forced through standard, square-optimized kernels, these irregular shapes suffer severe performance degradation. To bridge this gap, a prominent research direction focuses on shape-aware kernel optimization. Rather than treating irregular matrices as suboptimal exceptions that must be padded or forced into rigid templates, this paradigm adapts the underlying computational execution—including micro-kernel dimensions, cache allocations, and parallelization strategies—to the exact geometric properties of the input data.

The Hardware Tax of Shape Mismatches

To understand why standard libraries fail when processing non-square matrices, we must look at how hardware caches and execution pipelines interact with matrix dimensions.

Cache Underutilization and Thrashing

Standard libraries use fixed cache configuration parameters optimized for square matrices. When operating on a "tall-and-skinny" matrix where one dimension is small, these static configurations leave large portions of the available cache completely unused, turning a compute-heavy operation into a memory-bound bottleneck. As demonstrated by Hèctor Martínez et al. in Cache-aware optimization of matrix multiplication and matrix factorizations on multicore processors, rigid cache configurations fail to adapt to the changing shapes of matrix operands during runtime execution, leading to massive data movement overhead and reduced throughput during complex operations like LU or QR factorizations.

The Compute-to-Memory Shift

In standard GEMM, operational intensity is high because data reuse scales with matrix size. However, as Cody Rivera et al. point out in TSM2X: High-performance tall-and-skinny matrix-matrix multiplication on GPUs, when one matrix dimension becomes significantly smaller than the others, the bottleneck shifts from being compute-bound to memory- or latency-bound. Traditional square tiling strategies cannot saturate the hardware's computational resources under these conditions because they fail to maintain high data reuse.

The Inefficiency of Padding

To make irregular shapes compatible with standard vendor libraries, frameworks often resort to zero-padding. Shangfei Yin argues in Optimizing Irregular-Shaped Matrix-Matrix Multiplication on Multi-Core DSPs that treating irregular matrices as suboptimal versions of regular ones by adding padding consumes unnecessary memory and wastes computational cycles. Instead, treating irregular shapes as primary targets avoids these significant performance penalties.

Standard Square Tiling on Skinny Matrix:
+---+---+---+---+
| X |   |   |   |  <-- Wasteful: Tile extends beyond matrix boundary,
+---+---+---+---+      leading to empty registers or zero-padding.
| X |   |   |   |
+---+---+---+---+

Shape-Aware Rectangular Tiling:
+---+
| X |
+---+                  <-- Efficient: Tile dimensions match the matrix shape,
| X |                      maximizing register and cache utilization.
+---+

How Shape-Aware Optimization Works

The core insight of shape-aware optimization is that the execution engine must be as flexible as the data shapes it encounters. This flexibility is achieved through three main mechanisms.

1. Dynamic Micro-Kernel Customization

Instead of relying on a single, hand-tuned assembly micro-kernel, frameworks can automatically generate a diverse family of micro-kernels with varying tile dimensions. Adrián Castelló 0001 et al. show in Micro-kernels for portable and efficient matrix multiplication in deep learning that optimizing micro-kernel dimensions to match the specific non-square shapes found in deep learning layers yields higher performance than using a single, highly optimized static kernel.

By choosing between different assembly-level implementations at runtime, the system minimizes memory stalls and maximizes throughput for diverse matrix geometries. This is further supported by Guillermo Alaejos et al. in Automatic generation of ARM NEON micro-kernels for matrix multiplication, who demonstrate that generating a diverse family of kernels tailored to specific workload dimensions allows for better hardware utilization across varied neural network layers than traditional one-size-fits-all optimization strategies.

2. Dimension-Aware Auto-Tuning

The optimal execution parameters for a computational kernel depend heavily on both the hardware architecture and the specific dimensions of the input data. Frameworks like ISAAC, developed by Philippe Tillet et al. in Input-aware auto-tuning of compute-bound HPC kernels, use machine learning to dynamically map input characteristics (such as exact matrix dimensions) to optimal tuning parameters at runtime.

This ensures high hardware occupancy and consistent performance regardless of how irregular the data shape is. Similarly, Adrián Castelló 0001 et al. leverage compiler frameworks in Algorithm 1039: Automatic Generators for a Family of Matrix Multiplication Routines with Apache TVM to automatically select tiling parameters that optimize cache utilization for non-square workloads.

3. Adaptive Parallelization Strategies

The optimal way to distribute work across multiple processor cores depends heavily on matrix geometry. Shangfei Yin demonstrates that adapting parallelization strategies to the specific dimensions—such as using row-wise distribution for tall matrices and inner-dimension partitioning for skinny ones—maximizes core utilization far better than static parallelization schemes.

Impact Across Domains

Deep Learning Inference and Transformers

In transformer models, token generation and self-attention mechanisms often result in highly asymmetric, skinny matrix operations. Hèctor Martínez et al. show in Inference with Transformer Encoders on ARM and RISC-V Multicore Processors that dynamically adjusting cache configuration parameters at runtime based on these specific skinny dimensions yields substantial speedups on low-power edge processors.

Furthermore, algorithmic transformations like Winograd convolutions inherently produce irregular, tall, or skinny matrix shapes. The authors of Automatic Generation of High-Performance Convolution Kernels on ARM CPUs for Deep Learning demonstrate that tailoring compute kernels specifically for these non-standard dimensions unlocks massive performance gains that general-purpose libraries miss.

Scientific Computing and Alternative Frameworks

The benefits of shape-aware design extend well beyond neural networks:

  • Quantum Circuit Simulation: Gate operations generate highly irregular matrix shapes. Hiroyuki Ootomo et al. show in Quantum Circuit Simulation by SGEMM Emulation on Tensor Cores and Automatic Precision Selection that tailoring matrix multiplication kernels to these specific shapes dramatically increases memory bandwidth efficiency.
  • Distributed Factorizations: In large-scale simulations, communication costs dominate. Grey Ballard et al. highlight in A 3D Parallel Algorithm for QR Decomposition the necessity of recursive frameworks that can adapt to varying matrix dimensions during computation to hit theoretical lower bounds for data movement.
  • Approximate Computing: Even approximate methods are sensitive to geometry. In Multiplying Matrices Without Multiplying, Davis W. Blalock et al. demonstrate that lookup-based approximate multiplication methods show the greatest efficiency for tall matrices, where the computational overhead of the encoding step can be effectively amortized over a much larger dimension.

By shifting the optimization target from fixed hardware-centric templates to flexible data-centric execution, shape-aware optimization ensures that modern accelerators maintain peak efficiency, regardless of how irregular the workload becomes.

Key Foundational Work

Input-aware auto-tuning of compute-bound HPC kernels (2017) — contributed 3 concept elements to this direction.
High Performance Zero-Memory Overhead Direct Convolutions (2018) — contributed 1 concept elements to this direction.
A 3D Parallel Algorithm for QR Decomposition (2018) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_matrix_shape_mismatch_5aa6aa08,
  title = {matrix shape mismatch},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/matrix-shape-mismatch/rdr_5aa6aa08611846178bc49dc0ffb9d20c},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_matrix_shape_mismatch_5aa6aa08_v1,
  title = {matrix shape mismatch},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/matrix-shape-mismatch/rdr_5aa6aa08611846178bc49dc0ffb9d20c/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}

See something wrong? Report a mistake