🕵 The Cache Hit Paradox

This profiling detective case demonstrates how memory access patterns create 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 inefficient memory access patterns

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):

• Coalescing matters more than caching for memory-bound workloads
• Poor access patterns can cause artificial cache hit inflation
• Memory bandwidth utilization is the real performance indicator

Root cause analysis - memory access patterns

Actual Kernel Implementations from p30.mojo:

Kernel 1 - Efficient Coalesced Access:

fn kernel1[
    layout: Layout
](
    output: LayoutTensor[mut=True, dtype, layout],
    a: LayoutTensor[mut=False, dtype, layout],
    b: LayoutTensor[mut=False, dtype, layout],
    size: Int,
):
    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 - Inefficient Strided Access:

fn kernel2[
    layout: Layout
](
    output: LayoutTensor[mut=True, dtype, layout],
    a: LayoutTensor[mut=False, dtype, layout],
    b: LayoutTensor[mut=False, dtype, layout],
    size: Int,
):
    tid = block_idx.x * block_dim.x + thread_idx.x
    stride = 512

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

Large stride=512 creates memory access gaps - same operation but scattered access

Kernel 3 - Efficient Reverse Access:

fn kernel3[
    layout: Layout
](
    output: LayoutTensor[mut=True, dtype, layout],
    a: LayoutTensor[mut=False, dtype, layout],
    b: LayoutTensor[mut=False, dtype, layout],
    size: Int,
):
    tid = block_idx.x * block_dim.x + thread_idx.x
    total_threads = (SIZE // 1024) * 1024

    for step in range(0, size, total_threads):
        forward_i = step + tid
        if forward_i < size:
            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: Catastrophic strided access - threads jump by 512 elements
• 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:

alias SIZE = 16 * 1024 * 1024          # 16M elements (64MB of float32 data)
alias THREADS_PER_BLOCK = (1024, 1)    # 1024 threads per block
alias BLOCKS_PER_GRID = (SIZE // 1024, 1)  # 16,384 blocks total
alias 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 (Strided by 512):
Warp threads 0-31:             Warp threads 0-31:
  Thread 0: Memory[0]            Thread 0: Memory[0]
  Thread 1: Memory[1]            Thread 1: Memory[512]
  Thread 2: Memory[2]            Thread 2: Memory[1024]
  ...                           ...
  Thread 31: Memory[31]          Thread 31: Memory[15872]

Result: 1 cache line fetch       Result: 32 separate cache line fetches
Status: ~308 GB/s throughput     Status: ~6 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: ~310 GB/s throughput (nearly identical to 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 repetition: Each 512-element jump stays within overlapping cache line regions
2. False efficiency illusion: Same cache lines accessed repeatedly = artificially high “hit rates”
3. Bandwidth catastrophe: 32 threads × 32 separate cache lines = massive memory traffic
4. Warp execution mismatch: GPU designed for coalesced access, but getting scattered access

Concrete example with float32 (4 bytes each):

• Cache line: 128 bytes = 32 float32 values
• Stride 512: Thread jumps by 512×4 = 2048 bytes = 16 cache lines apart!
• Warp impact: 32 threads need 32 different cache lines instead of 1

The key insight: High cache hits in Kernel2 are repeated access to inefficiently fetched data, not 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: ~308 GB/s            → i = block_idx*block_dim + thread_idx (coalesced)
- Kernel2: ~6 GB/s, 99% L2 hits → i += 512 (catastrophic stride)
- Kernel3: ~310 GB/s            → reverse_i = size-1-forward_i (reverse coalesced)

The profiler data directly reveals the memory access efficiency!

Evidence-to-Code Connection:

• High throughput + normal cache rates = Coalesced access (Kernels 1 & 3)
• Low throughput + high cache rates = Inefficient strided access (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. Memory patterns dominate: Access patterns often matter more than algorithmic complexity
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 poor memory access patterns (not good performance)
• Memory bandwidth utilization matters more than cache statistics
• Simple coalesced patterns often outperform complex algorithms
• 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.