Tiled Attention Against the SRAM Budget
Problem statement
A GPU has a few hundred kilobytes of on-chip SRAM per streaming multiprocessor, orders of magnitude faster than the HBM that holds the model. FlashAttention exploits that gap by processing attention in tiles that never leave SRAM. Implement the five functions below, which do the arithmetic that decides how big a tile can be and how much HBM traffic tiling saves.
attention_tile_bytes(br, bc, d, bytes_per_elem)
- Bytes held on chip while one tile is processed: a query tile of
br x d, a key tile and a value tile ofbc x deach, a score tile ofbr x bc, an output accumulator ofbr x d, and two running statistics per query row (2 * brvalues).
largest_block(sram_bytes, d, bytes_per_elem)
- The largest power of two
b, withbr = bc = b, whose tile fits insram_bytes; return0if evenb = 1does not fit.
standard_attention_traffic(n, d, bytes_per_elem)
- HBM bytes for unfused attention on one head of length
n: readQ,K,V(3ndelements), write the score matrix (n^2), read it and write the probabilities for the softmax (2n^2), read the probabilities andV(n^2 + nd), write the output (nd); in total5nd + 4n^2elements.
tiled_attention_traffic(n, d, br, bytes_per_elem)
- HBM bytes for the tiled algorithm with query blocks of
brrows:Qis read once and the output written once (2nd), and every query block re-reads all ofKandV(ceil(n / br) * 2nd).
traffic_ratio(n, d, br, bytes_per_elem)
standard_attention_traffic / tiled_attention_traffic, rounded to 3 decimals.
Example
Input:
attention_tile_bytes(64, 64, 64, 2)
Output:
41216
Reasoning: Q, O, K, V and the score tile are each 64 x 64 = 4096 elements (K and V together are 8192), plus 2 64 = 128 running statistics, at 2 bytes each: 2 (4096 + 8192 + 4096 + 4096 + 128) = 41216.
Show hint
Which arrays must be resident on chip at the same time while one query block meets one key/value block?
Relevant roles: Deep Learning Engineer, LLM Engineer, ML Engineer and Research Scientist.
Related free problems
- PagedAttention: Block-wise Attention ComputationLLMs & GenAIHard