#1971·warp

Reduce redundant radix sorting in CUDA BSR transpose

Author: maxkra15Created Sep 17, 2026Updated Sep 17, 2026
Labelswarp.sparse

Description

CUDA bsr_set_transpose() at 0e76b6a0 sorts all 64 bits of the combined destination-row/source-row key. Source blocks already follow source-row order, so a stable sort only needs the destination-row bits. Preserve a sentinel above valid rows so inactive padding sorts last.

Reproduction

Run the captured benchmark against separately built reference and candidate checkouts. It covers regular stencils, dense matrices, overallocated storage, and concentrated output rows.

Two reversed-order comparisons on an RTX 4090/CUDA 13.0 measured 1.83–2.32× speedups across those six patterns. The eight-shared-columns case improved 0.100 → 0.055 ms; overallocated storage improved 2.649 → 1.143 ms. Raw samples and pinned revisions.

Expected behavior

  • Preserve sorted topology, value bits, block transposition, padding, aliasing, and gradients.
  • Support changing active entries during CUDA Graph replay without host synchronization.
  • Improve sorting work without a concentrated-row performance regression.

Proposed implementation: #1940. It retains capacity-sized sorting with fewer radix passes; active-entry scaling is outside this change.