Topic 04: Custom CUDA FlashAttention & Online Softmax Tiling

Overview: The hardware memory bottleneck of standard multi-head attention, tiled execution using GPU on-chip shared memory (SRAM), the mathematical derivation of online-softmax rescaling, thread block synchronization barriers, and scaling auxiliary VRAM from $\mathcal{O}(N^2)$ down to $\mathcal{O}(N)$ to prevent Out-Of-Memory crashes at 4K context.


1. The Problem: The GPU Memory Wall in Attention

Standard Multi-Head Attention is formulated as:

$$\text{Attention}(Q, K, V) = \text{softmax}\left(\frac{Q K^T}{\sqrt{d}}\right) V$$

In a naive CUDA or PyTorch implementation, this is executed in three sequential kernels:

  1. Matrix Multiplication 1: Compute $S = Q K^T / \sqrt{d}$. Write the full $N \times N$ matrix $S$ to GPU High Bandwidth Memory (HBM).
  2. Softmax Normalization: Read $S$ from HBM, find row maximums, compute $\exp(S - \max)$, sum row denominators, and divide to get $P = \text{softmax}(S)$. Write $P$ ($N \times N$) back to HBM.
  3. Matrix Multiplication 2: Read $P$ and $V$ from HBM, compute $O = P V$, and write $O$ ($N \times d$) to HBM.

Why This Severely Bottlenecks Hardware


2. FlashAttention Architecture: Tiling with On-Chip SRAM

FlashAttention (Tri Dao et al., 2022) restructures attention to compute everything in small blocks directly inside fast on-chip Shared Memory (SRAM):

Global Memory (HBM: 6 GB, 192 GB/s)
   │               ▲
   │ Tile Load     │ Final O only (N x d)
   ▼               │
Shared Memory (SRAM: 48 KB per SM, ~10 TB/s)
┌────────────────────────────────────────────────────────┐
│  Qi (Br x d)  │  Kj (Bc x d)  │  Vj (Bc x d)  │  S     │
│  Tiled Q      │  Tiled K      │  Tiled V      │  BrxBc │
└────────────────────────────────────────────────────────┘

Tile Dimensions (`PA4/flash.cu`)


3. The Online Softmax Algorithm (Milakov & Gimelshein / Dao et al.)

The core mathematical hurdle to tiling attention is softmax normalization. In standard softmax, you cannot compute the denominator $\sum_j e^{s_j}$ until you have seen every single column in the row.

FlashAttention solves this using the online softmax algorithm. As each new K/V tile $j$ arrives, it maintains running statistics: running row max $m$ and running denominator sum $l$.

Mathematical Derivation Step-by-Step

For query row $i$, suppose we have processed tiles $0 \dots j-1$ with running max $m_{prev}$ and denominator $l_{prev}$, and we now process tile $j$ with local scores $S_{ij}$:

  1. Compute Local Tile Maximum: $$m_{curr} = \max_{y \in [0, B_c-1]} S_{ij}[y]$$
  2. Compute Local Exponentials & Sum: $$P_{ij}[y] = \exp(S_{ij}[y] - m_{curr}), \quad l_{curr} = \sum_{y=0}^{B_c-1} P_{ij}[y]$$
  3. Update Running Global Maximum: $$m_{new} = \max(m_{prev}, m_{curr})$$
  4. Rescale Previous & Current Exponentials: $$\alpha_{prev} = \exp(m_{prev} - m_{new}), \quad \alpha_{curr} = \exp(m_{curr} - m_{new})$$
  5. Update Running Denominator: $$l_{new} = l_{prev} \cdot \alpha_{prev} + l_{curr} \cdot \alpha_{curr}$$
  6. Rescale Output Accumulator $O$:

    The previous output $O_{prev}$ was normalized by $l_{prev}$ using max $m_{prev}$. We rescale $O_{prev}$ to the new maximum $m_{new}$ and blend in the new tile's weighted value contribution $P_{ij} V_j$:

    $$O_{new} = \frac{l_{prev} \cdot \alpha_{prev} \cdot O_{prev} + \alpha_{curr} \cdot (P_{ij} V_j)}{l_{new}}$$

When the loop over all $T_c$ tiles finishes, $O$ is mathematically identical to standard global softmax attention!


4. CUDA Kernel Implementation & Synchronization (`flash.cu`)

__global__ void flash_attention_kernel(
    const float* Q, const float* K, const float* V, float* O, 
    float* m, float* l, 
    int B, int NH, int N, int d, int Tc, int Tr, int Bc, int Br, float scale) {
    
    int tx = threadIdx.x; // Thread index [0 .. Br-1]
    
    // Shared Memory Pointers
    extern __shared__ float smem[];
    float* Qi = smem; 
    float* Kj = Qi + Br * d; 
    float* Vj = Kj + Bc * d; 
    float* S  = Vj + Bc * d; 

    // Outer Loop: Over K/V Tiles (j = 0 .. Tc - 1)
    for (int j = 0; j < Tc; j++) {
        
        // Cooperatively load Kj and Vj into shared memory
        for (int x = 0; x < d; x++) {
            Kj[tx * d + x] = K[qkv_base + (j * Bc + tx) * d + x];
            Vj[tx * d + x] = V[qkv_base + (j * Bc + tx) * d + x];
        }
        __syncthreads(); // BARRIER 1: All Bc rows of K/V are loaded in smem

        // Inner Loop: Over Q Tiles (i = 0 .. Tr - 1)
        for (int i = 0; i < Tr; i++) {
            int q_row_global = i * Br + tx;
            
            // 1. Load Qi row into shared memory
            for (int x = 0; x < d; x++) Qi[tx * d + x] = Q[...];

            // 2. Read running statistics from global memory
            float m_prev = m[lm_base + q_row_global];
            float l_prev = l[lm_base + q_row_global];

            // 3. Compute dot products S = (Qi . Kj^T) * scale
            // 4. Compute m_curr and l_curr
            // 5. Update m_new and l_new
            // 6. Rescale and update O[qkv_base + q_row_global * d + x]
            
            m[lm_base + q_row_global] = m_new;
            l[lm_base + q_row_global] = l_new;
        }
        __syncthreads(); // BARRIER 2: Prevent overwriting K/V before all inner loops finish
    }
}

Two Critical Edge Cases Handled

  1. Negative Infinity Initialization:

    `cudaMalloc` does not zero-initialize. Furthermore, initializing `d_m` to `0.0f` is fatal because any negative dot-product score from the first tile would be smaller than 0.0, clipping legitimate attention scores. We authored an initialization kernel `init_neg_inf` setting `d_m = -1e20f` across all entries.

  2. Barrier 2 Synchronization:

    A second `__syncthreads()` barrier at the end of the outer loop is mandatory. Without it, faster threads looping to tile $j+1$ would begin overwriting `Kj` and `Vj` in shared memory while slower threads in the same block were still reading tile $j$'s values.


5. Empirical Benchmark Comparison: Scaling to 4K Tokens

In our head-to-head benchmark on identical random tensors (`attention_bench.cu` on RTX 3050 GPU):

Sequence Length ($N$) Standard Attention (Global HBM) FlashAttention (SRAM Tiled) Speedup Max Absolute Diff Auxiliary VRAM Scaling
128 1.69 ms 1.25 ms 1.35x $1.49 \times 10^{-6}$ Standard: 0.5 MB vs Flash: 1 KB
256 4.10 ms 2.62 ms 1.56x $1.90 \times 10^{-6}$ Standard: 2.1 MB vs Flash: 2 KB
512 11.60 ms 6.19 ms 1.87x $2.38 \times 10^{-6}$ Standard: 8.4 MB vs Flash: 4 KB
1024 37.43 ms 16.33 ms 2.29x $2.86 \times 10^{-6}$ Standard: 33.6 MB vs Flash: 8 KB
2048 141.33 ms 51.12 ms 2.76x $3.57 \times 10^{-6}$ Standard: 134.2 MB vs Flash: 16 KB
4096 CUDA OutOfMemory (Tried 6.0 GB) 180.87 ms Infinite (Prevents Crash) -- $\mathcal{O}(N^2) \to \mathcal{O}(N)$

Numerical Precision: The maximum absolute difference between FlashAttention and Standard Attention was $< 4 \times 10^{-6}$, confirming pure float32 numerical equivalence.


6. Interview Takeaway & Soundbite

🎯 Interview Answer — "Why does FlashAttention scale better than standard attention?"
“Standard attention is IO-bound: it materializes the entire $N \times N$ score matrix in global HBM, requiring multiple DRAM read/write passes that saturate memory bandwidth and cause OOM at long context. FlashAttention tiles $Q, K, V$ into on-chip SRAM and uses the online softmax algorithm to maintain running normalization factors ($m$ and $l$). It updates the output accumulator in place and writes only the final $N \times d$ output to memory, scaling auxiliary memory from $\mathcal{O}(N^2)$ to $\mathcal{O}(N)$ and delivering up to 2.76x speedup.”