Adaptive Strategy Selection for Sparse Matrix Operations

22 concepts11 papers1 proposal

In dense matrix multiplication, data access patterns are perfectly predictable. Hardware can easily prefetch data, and loops can be unrolled optimally because every element exists. Sparse matrices break this predictability. Because non-zero elements are distributed irregularly, the optimal way to store a matrix and traverse its elements depends entirely on the shape of that sparsity.

As established by Qichang Chen et al. in A model-driven partitioning and auto-tuning integrated framework for sparse matrix-vector multiplication on GPUs, no single sparse matrix storage format—whether Compressed Sparse Row (CSR), Coordinate (COO), or ELLPACK (ELL)—is universally optimal. A format that minimizes memory footprint for a highly uniform sparse matrix might cause severe load imbalance or uncoalesced memory accesses on a GPU when applied to a power-law graph matrix. To maximize hardware utilization, modern computing frameworks must dynamically adapt to the data at runtime.

The Two Dimensions of Adaptation: Formats and Dataflows

To optimize sparse operations, systems must adapt along two primary axes: how data is structured in memory (storage formats) and how data moves through processing elements (dataflows).

Storage Formats

Instead of forcing an entire matrix into a single format, adaptive frameworks partition matrices or select formats dynamically based on local density. For instance, Bor-Yiing Su and Kurt Keutzer proposed the "Cocktail Format" in clSpMV: A Cross-Platform OpenCL SpMV Framework on GPUs, which breaks a matrix into submatrices and assigns each the format best suited to its local density.

Similarly, Shizhao Chen et al. developed a hybrid format (HYB5) that combines SELL-C-σ and CSR5 to better exploit SIMD capabilities on multi-core CPUs, using an adaptive threshold to partition the matrix based on its structural properties (Adaptive Hybrid Storage Format for Sparse Matrix–Vector Multiplication on Multi-Core SIMD CPUs).

Execution Dataflows

In sparse-sparse matrix multiplication (SpMSpM), the choice of dataflow determines whether a system optimizes for input reuse or output reuse.

  • An inner-product dataflow computes one output element at a time, maximizing output reuse but requiring random, irregular accesses to sparse inputs.
  • An outer-product dataflow processes input elements to generate partial outputs, maximizing input reuse but requiring a complex reduction network to merge those partial results.

As explained by Francisco Muñoz-Martínez et al. in their work on the Flexagon accelerator (Flexagon: A Multi-Dataflow Sparse-Sparse Matrix Multiplication Accelerator for Efficient DNN Processing), the optimal dataflow shifts dynamically depending on the specific sparsity patterns and dimensions of the input matrices. A fixed-dataflow architecture inevitably suffers from severe underutilization when the matrix structure changes.

Why Static Strategies Fail in Modern Workloads

In traditional scientific computing, a matrix's structure might remain constant throughout a long simulation. However, modern workloads like Deep Neural Networks (DNNs), Graph Neural Networks (GNNs), and 3D point cloud processing feature highly dynamic sparsity patterns.

Hartwig Anzt et al. demonstrated that static execution strategies fail to optimize for real-time structural variations when performing batched sparse operations on GPUs (Flexible batched sparse matrix-vector product on GPUs). In a GNN, for example, data density and distribution evolve across different layers and training epochs.

Shenghao Qiu et al. observed that relying on a static default format like PyTorch's CSR severely bottlenecks performance because the optimal storage structure shifts as the model executes (Optimizing Sparse Matrix Multiplications for Graph Neural Networks).

[Static Execution]  ---> Forces all layers/matrices into one format/dataflow ---> Hardware Underutilization

[Adaptive Selection] ---> Profiles matrix structure at runtime ---> Selects optimal format/dataflow per layer

Predicting the Optimal Strategy at Runtime

If the optimal format or dataflow depends on the matrix's real-time structure, how can a system choose the best strategy without incurring an unacceptable profiling overhead? The research community has converged on two main approaches: analytical performance modeling and machine learning.

The authors of A model-driven partitioning and auto-tuning integrated framework for sparse matrix-vector multiplication on GPUs utilized an analytical performance model to predict kernel execution times, allowing the system to partition matrices and tune GPU parameters before execution.

More recently, machine learning has been deployed to handle highly complex, non-linear hardware interactions. Shenghao Qiu et al. implemented an XGBoost-based predictor to dynamically select between CSR, COO, and BSR formats at runtime for GNNs (Optimizing Sparse Matrix Multiplications for Graph Neural Networks).

In the context of hardware dataflows, Bahar Asgari and Sanjali Yadav introduced Misam, a framework that uses machine learning to dynamically switch between inner, outer, and row-wise dataflows based on matrix characteristics (Misam: Using ML in Dataflow Selection of Sparse-Sparse Matrix Multiplication). By predicting whether input or output reuse will yield better performance, Misam matches the computational strategy to the specific data structure at runtime.

Hardware-Aware Execution and Fine-Grained Tuning

Choosing the right format or dataflow is only half the battle; the execution engine must also adapt its low-level parameters to the underlying hardware architecture.

On GPUs, this requires managing thread cooperation and memory coalescing. Marco Maggioni and Tanya Y. Berger-Wolf developed a structure-independent, architecture-aware heuristic that optimizes how GPU warps access memory, showing that fine-grained thread mapping can yield significant speedups across multiple sparse formats (An Architecture-Aware Technique for Optimizing Sparse Matrix-Vector Multiplication on GPUs).

For complex operations like 3D sparse convolutions in point cloud processing, Jiacheng Yang et al. introduced Minuet, which employs an adaptive autotuning strategy to dynamically adjust tile sizes and reorder operations based on the specific layer and hardware configuration (Minuet: Accelerating 3D Sparse Convolutions on GPUs).

To address load balancing and cache contention, Xing Cong et al. proposed CB-SpMV, an algorithm that dynamically adjusts column aggregation and load balancing based on sub-block sparsity, ensuring high cache locality on heterogeneous hardware (CB-SpMV: A Data Aggregating and Balance Algorithm for for Cache-Friendly Block-Based SpMV on GPUs).

Despite these advances, automating this profiling pipeline efficiently remains a core challenge. As noted by Donglin Chen et al., identifying bottlenecks like shared cache contention and unbalanced data distribution automatically is critical for scaling sparse operations on emerging many-core architectures (Characterizing Scalability of Sparse Matrix-Vector Multiplications on Phytium FT-2000+).

Key Foundational Work

clSpMV: A Cross-Platform OpenCL SpMV Framework on GPUs (2012) — contributed 4 concept elements to this direction.
A model-driven partitioning and auto-tuning integrated framework for sparse matrix-vector multiplication on GPUs (2011) — contributed 2 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_adaptive_dataflow_selection_a4eb266b,
  title = {adaptive dataflow selection},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/adaptive-dataflow-selection/rdr_a4eb266b384a455bbe9da4bc380e082a},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_adaptive_dataflow_selection_a4eb266b_v1,
  title = {adaptive dataflow selection},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/adaptive-dataflow-selection/rdr_a4eb266b384a455bbe9da4bc380e082a/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake