Skip to content

CUDA kernels (research): shared-memory tiling of the dense operand #94

Closed as not planned

Description

@aarmey

Motivation

(Research.) The dense-operand gather is the dominant on-chip traffic, and the long stalls come from L1 misses on it: after #85 the L1 hit rate is 71% for the aligned VCSR @ B (operand B is 2,000 x 16 floats, 128 KB) and only 16% for B @ VCSC, where the transposed operand Bt is 60,000 x 16 floats (3.8 MB) and is indexed by cell id. A shared-memory tile of the operand would remove those misses.

The obstacle is layout. Tiling by column needs each row's nonzeros grouped by column tile, which conflicts with the value-run grouping (a run would have to be swept once per tile, with pointer metadata per (row, tile, run)).

To investigate

Activity

  1. self-assigned this
    on Nov 15, 2026
  2. aarmey commented on Nov 15, 2026

    @aarmey
    MemberAuthor

    Ran the upper-bound experiment from the issue. It shows too little to win, so I'm closing this without building any layout.

    Experiment. In the aligned kernels, I replaced the dense-operand row index mi with mi & 511. Results are wrong, but every B read then hits a 512-row table that is fully L1-resident, which is at least as good as a perfect shared-memory tile with no staging cost. RTX 5080, 60,000 x 2,000, time after / time before:

    case w=4 w=16 w=64
    VCSR @ B, uniform 5% 0.99x 0.87x 0.76x
    B @ VCSC, uniform 5% 0.84x 0.85x 0.67x
    VCSR @ B, Zipf-skewed 1.01x 0.89x 0.95x
    B @ VCSC, Zipf-skewed 0.93x 0.88x 0.67x

    Reading. Removing all dense-operand cache misses buys 0-15% at widths 4-16, the common widths, and 25-33% only at width 64 for the two cases with the worst hit rates. A real tile would do worse than this bound: it needs per-(row, tile, run) metadata and a re-sweep of each run per tile, which costs nonzero traffic, and the shared-memory staging has its own cost. The hot-gene hybrid in the issue is also capped by this bound, since it only removes a subset of the misses.

    The gather is not where the remaining time goes at the widths that matter. The bigger win was balance: skewed matrices lost 3-10x to a few giant slices, fixed in #100 (#92). Reopen if a workload turns up with widths of 64+ where B @ VCSC dominates.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

Labels

No labels
No labels

Type

No type

Projects

No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions