Tiled Attention Against the SRAM Budget

MediumML Coding

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 of bc x d each, a score tile of br x bc, an output accumulator of br x d, and two running statistics per query row (2 * br values).

largest_block(sram_bytes, d, bytes_per_elem)

  • The largest power of two b, with br = bc = b, whose tile fits in sram_bytes; return 0 if even b = 1 does not fit.

standard_attention_traffic(n, d, bytes_per_elem)

  • HBM bytes for unfused attention on one head of length n: read Q, K, V (3nd elements), write the score matrix (n^2), read it and write the probabilities for the softmax (2n^2), read the probabilities and V (n^2 + nd), write the output (nd); in total 5nd + 4n^2 elements.

tiled_attention_traffic(n, d, br, bytes_per_elem)

  • HBM bytes for the tiled algorithm with query blocks of br rows: Q is read once and the output written once (2nd), and every query block re-reads all of K and V (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