🕵 The Cache Hit Paradox

This profiling detective case demonstrates how the amount of work a kernel issues creates orders-of-magnitude performance differences, even when kernels perform identical mathematical operations.

Performance evidence from profiling

Nsight Systems Timeline Analysis:

• Kernel 1: Short execution time - EFFICIENT
• Kernel 3: Similar to Kernel 1 - EFFICIENT
• Kernel 2: Dramatically longer execution time - INEFFICIENT

Nsight Compute Memory Analysis (Hardware-Agnostic Patterns):

• Efficient kernels (1 & 3): High memory throughput, good bandwidth utilization, moderate cache hit rates
• Inefficient kernel (2): Very low memory throughput, poor bandwidth utilization, extremely high cache hit rates

The cache paradox revealed

🤯 The Counterintuitive Discovery:

• Kernel2 has the HIGHEST cache hit rates but WORST performance
• This challenges conventional wisdom: “High cache hits = good performance”
• The truth: High cache hit rates can be a symptom of re-reading data the grid has already fetched

Why the Cache Paradox Occurs:

Traditional CPU intuition (INCORRECT for GPUs):

• Higher cache hit rates always mean better performance
• Cache hits reduce memory traffic, improving efficiency

GPU memory reality (CORRECT understanding):

• Delivered bandwidth matters more than hit rate for memory-bound workloads
• Redundant work can inflate cache hit rates while starving throughput
• Memory bandwidth utilization is the real performance indicator

Root cause analysis - redundant work

Actual Kernel Implementations from p30.mojo:

Kernel 1 - Efficient Coalesced Access:

def kernel1(
    output: TileTensor[mut=True, dtype, LayoutType, MutAnyOrigin],
    a: TileTensor[mut=False, dtype, LayoutType, ImmutAnyOrigin],
    b: TileTensor[mut=False, dtype, LayoutType, ImmutAnyOrigin],
    size_dev: Int32,
):
    var size = Int(size_dev)
    var i = block_dim.x * block_idx.x + thread_idx.x
    if i < size:
        output[i] = a[i] + b[i]

Standard thread indexing - adjacent threads access adjacent memory

Kernel 2 - Redundant Grid-Stride Loop:

def kernel2(
    output: TileTensor[mut=True, dtype, LayoutType, MutAnyOrigin],
    a: TileTensor[mut=False, dtype, LayoutType, ImmutAnyOrigin],
    b: TileTensor[mut=False, dtype, LayoutType, ImmutAnyOrigin],
    size_dev: Int32,
):
    var size = Int(size_dev)
    var tid = block_idx.x * block_dim.x + thread_idx.x
    var stride = 512

    var i = tid
    while i < size:
        output[i] = a[i] + b[i]
        i += stride

Grid-stride loop with stride = 512. The stride separates successive iterations of a single thread, not the threads within a warp—so each warp access is still contiguous. The cost is redundant work: the grid is already SIZE threads wide, one per element, so having every thread additionally walk the whole buffer performs 16,384x the element operations kernel1 does. The last element is written by 32,768 separate threads.

Kernel 3 - Efficient Reverse Access:

def kernel3(
    output: TileTensor[mut=True, dtype, LayoutType, MutAnyOrigin],
    a: TileTensor[mut=False, dtype, LayoutType, ImmutAnyOrigin],
    b: TileTensor[mut=False, dtype, LayoutType, ImmutAnyOrigin],
    size_dev: Int32,
):
    var size = Int(size_dev)
    var tid = block_idx.x * block_dim.x + thread_idx.x
    var total_threads = (SIZE // 1024) * 1024

    for step in range(0, size, total_threads):
        var forward_i = step + tid
        if forward_i < size:
            var reverse_i = size - 1 - forward_i
            output[reverse_i] = a[reverse_i] + b[reverse_i]

Reverse indexing but still predictable - adjacent threads access adjacent addresses (just backwards)

Pattern Analysis:

• Kernel 1: Classic coalesced access - adjacent threads access adjacent memory
• Kernel 2: Coalesced within each warp access, but the grid-stride loop makes the whole grid re-traverse the buffer thousands of times
• Kernel 3: Reverse but still coalesced within warps - predictable pattern

Understanding the memory system

GPU Memory Architecture Fundamentals:

• Warp execution: 32 threads execute together
• Cache line size: 128 bytes (32 float32 values)
• Coalescing requirement: Adjacent threads should access adjacent memory

p30.mojo Configuration Details:

comptime SIZE = 16 * 1024 * 1024          # 16M elements (64MB of float32 data)
comptime THREADS_PER_BLOCK = (1024, 1)    # 1024 threads per block
comptime BLOCKS_PER_GRID = (SIZE // 1024, 1)  # 16,384 blocks total
comptime dtype = DType.float32             # 4 bytes per element

Why these settings matter:

• Large dataset (16M): Makes memory access patterns clearly visible
• 1024 threads/block: Maximum CUDA threads per block
• 32 warps/block: Each block contains 32 warps of 32 threads each

Memory Access Efficiency Visualization:

KERNEL 1 (Coalesced):           KERNEL 2 (Grid-stride loop, stride 512):
Warp threads 0-31:             Warp threads 0-31, iteration 0:
  Thread 0: Memory[0]            Thread 0: Memory[0]
  Thread 1: Memory[1]            Thread 1: Memory[1]
  Thread 2: Memory[2]            Thread 2: Memory[2]
  ...                           ...
  Thread 31: Memory[31]          Thread 31: Memory[31]

                               Thread 0 across iterations:
                                 iter 0: Memory[0]
                                 iter 1: Memory[512]
                                 iter 2: Memory[1024]

Result: 1 cache line fetch       Result: 1 cache line fetch, ×16,384 passes
Status: ~2.06 TB/s throughput    Status: ~8.7 GB/s throughput
Cache: Efficient utilization     Cache: Same lines hit repeatedly!

KERNEL 3 (Reverse but Coalesced):

Warp threads 0-31 (first iteration):
  Thread 0: Memory[SIZE-1]     (reverse_i = SIZE-1-0)
  Thread 1: Memory[SIZE-2]     (reverse_i = SIZE-1-1)
  Thread 2: Memory[SIZE-3]     (reverse_i = SIZE-1-2)
  ...
  Thread 31: Memory[SIZE-32]   (reverse_i = SIZE-1-31)

Result: Adjacent addresses (just backwards)
Status: ~1.78 TB/s throughput (same order as Kernel 1)
Cache: Efficient utilization despite reverse order

The cache paradox explained

Why Kernel2 (stride=512) has high cache hit rates but poor performance:

The stride=512 disaster explained:

# Each thread processes multiple elements with huge gaps:
Thread 0: elements [0, 512, 1024, 1536, 2048, ...]
Thread 1: elements [1, 513, 1025, 1537, 2049, ...]
Thread 2: elements [2, 514, 1026, 1538, 2050, ...]
...

Why this creates the cache paradox:

1. Cache line reuse across the grid: a 512-element jump on float32 is 2048 bytes—16 cache lines further on—but every one of those lines has already been pulled in by another thread, since the grid spans the whole buffer
2. False efficiency illusion: the same cache lines are accessed over and over = artificially high “hit rates”
3. Redundant work: the grid already has one thread per element, so the loop makes it re-traverse the buffer 16,384 times over—this is the dominant cost, and it is what the repeated cache hits are hits on
4. Long residency: the loop keeps every block resident far longer than the one-element-per-thread kernels, so the grid drains much more slowly

Concrete example with float32 (4 bytes each):

• Cache line: 128 bytes = 32 float32 values
• Stride 512: a single thread jumps 512×4 = 2048 bytes = 16 cache lines between its own iterations
• Warp impact: a warp still reads 32 consecutive floats per iteration, so each access is one cache line—the waste is in how many times the grid revisits those lines, not in how many lines a warp touches

The key insight: High cache hits in Kernel2 come from re-reading data the grid has already fetched, not from smart caching!

Profiling methodology insights

Systematic Detective Approach:

Phase 1: Nsight Systems (Big Picture)

• Identify which kernels are slow
• Rule out obvious bottlenecks (memory transfers, API overhead)
• Focus on kernel execution time differences

Phase 2: Nsight Compute (Deep Analysis)

• Analyze memory throughput metrics
• Compare bandwidth utilization percentages
• Investigate cache hit rates and patterns

Phase 3: Connect Evidence to Theory

PROFILING EVIDENCE → CODE ANALYSIS:

Nsight Compute Results:           Actual Code Pattern:
- Kernel1: ~2.06 TB/s            → i = block_idx*block_dim + thread_idx (coalesced)
- Kernel2: ~8.7 GB/s, 99% L2 hits → i += 512 (redundant re-traversal)
- Kernel3: ~1.78 TB/s            → reverse_i = size-1-forward_i (reverse coalesced)

The profiler data directly reveals how much work each kernel issues!

Evidence-to-Code Connection:

• High throughput + normal cache rates = Coalesced access (Kernels 1 & 3)
• Low throughput + high cache rates = Redundant re-traversal of data already fetched (Kernel 2)
• Memory bandwidth utilization reveals true efficiency regardless of cache statistics

Real-world performance implications

This pattern affects many GPU applications:

Scientific Computing:

• Stencil computations: Neighbor access patterns in grid simulations
• Linear algebra: Matrix traversal order (row-major vs column-major)
• PDE solvers: Grid point access patterns in finite difference methods

Graphics and Image Processing:

• Texture filtering: Sample access patterns in shaders
• Image convolution: Filter kernel memory access
• Color space conversion: Channel interleaving strategies

Machine Learning:

• Matrix operations: Memory layout optimization in GEMM
• Tensor contractions: Multi-dimensional array access patterns
• Data loading: Batch processing and preprocessing pipelines

Fundamental GPU optimization principles

Memory-First Optimization Strategy:

1. Count the work first: the number of element operations a grid issues often dwarfs every other effect, as kernel2 shows
2. Coalescing is critical: Design for adjacent threads accessing adjacent memory
3. Measure bandwidth utilization: Focus on actual throughput, not just cache statistics
4. Profile systematically: Use Nsight tools to identify real bottlenecks

Key Technical Insights:

• Memory-bound workloads: Bandwidth utilization determines performance
• Cache metrics can mislead: High hit rates don’t always indicate efficiency
• Warp-level thinking: Design access patterns for 32-thread execution groups
• Hardware-aware programming: Understanding GPU memory hierarchy is essential

Key takeaways

This detective case reveals that GPU performance optimization requires abandoning CPU intuition for memory-centric thinking:

Critical insights:

• High cache hit rates can indicate wasted work (not good performance)
• Memory bandwidth utilization matters more than cache statistics
• Doing the work once beats re-reading data the grid has already fetched
• Profiling tools reveal counterintuitive performance truths

Practical methodology:

• Profile systematically with Nsight Systems and Nsight Compute
• Design for adjacent threads accessing adjacent memory (coalescing)
• Let profiler evidence guide optimization decisions, not intuition

The cache paradox demonstrates that high-level metrics can mislead without architectural understanding - applicable far beyond GPU programming.