Back to paper library
arXiv 2023ICLR 2024Language & TransformersPaper notes

FlashAttention-2

The GPU is just sitting there

Original paper

FlashAttention-2: Faster Attention with Better Parallelism and Work Partitioning

Paper authors

Tri Dao

Publication
ICLR 2024Conference
First submitted to arXiv
arXiv:2307.08691
Cite this paper · BibTeX

The citation identifies the linked source version. It cites the original paper and its authors.

@misc{transformersflashattention22023,
  title = {{FlashAttention-2: Faster Attention with Better Parallelism and Work Partitioning}},
  author = {Tri Dao},
  year = {2023},
  eprint = {2307.08691},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2307.08691}
}
On this page

FlashAttention used tiling, online softmax, and recomputation to keep the attention matrix from making repeated trips through HBM. It substantially reduced memory use and made the computation faster, too.

But when we open the GPU's work queue, something looks wrong.

Why is it...

so idle?

The problem

We all know that work is divided at two levels inside a GPU.

A GPU has many Streaming Multiprocessors (SMs) that can work at the same time. A program groups threads into a thread block and assigns the block to an SM. Within a block, threads are divided into warps, usually 32 threads per warp.

Think of an SM as a factory, a thread block as a work order, and a warp as one of the crews doing the work.

The first FlashAttention mainly assigns work according to batch size × number of attention heads. Take the A100 from the paper: it has 108 SMs. If batch size is 1 and there are 8 attention heads, we get only 8 thread blocks.

A hundred and eight factories. Eight work orders.

What do the other hundred do? Take a nap, apparently.

A longer sequence only makes those eight orders thicker; it does not bring more factories online. The paper reports that the first implementation reaches only 25–40% of theoretical peak throughput. There is plenty of room left on the GPU.

And that is not all.

Tensor Cores are excellent at matrix multiplication, but softmax requires many operations that are not matrix multiplications. These apparently simple operations run much less efficiently and slow the calculation down. Meanwhile, inside a first-generation block, different warps each handle part of K,VK,V. They then exchange partial results through shared memory, synchronize, and merge them.

To sum up the problem so far:

Too little work is distributed among SMs, and the work inside each block is divided poorly among warps.

Could we simply cut the work into smaller pieces and run more SMs at once?

Attention does not split that easily. Every score in a softmax row needs the same normalization information. During backpropagation, separate blocks may also need to add to the same gradient. Cut too coarsely and the GPU sits idle; cut too finely and everyone waits for everyone else.

How do we give everyone work without spending the day in meetings?

That is the problem FlashAttention-2 sets out to solve.

The method

The authors split the forward work in two places, with different thread blocks owning different groups of query rows and different warps within a block owning their own query rows. After that split, each row must still be able to finish its softmax. Let us follow one row through the arrangement.

Assign work by row

Of the three letters on the score table, QQ says what we are looking for, KK provides the clues to compare against, and VV holds the content we eventually retrieve. Imagine attention scores as a table. Its rows come from QQ, its columns from KK, and each cell scores one pairing.

Softmax runs across a row. Scores in the same row share a denominator, while a different row has its own denominator. The authors therefore assign a group of complete rows to one thread block, which reads the K,VK,V tiles it needs in sequence and produces those rows' outputs.

Look at the paper's Figure 2. In the left panel, each color marks a group of query rows assigned to one worker (a thread block). The white cells are skipped because of the causal mask. When generating text, earlier words must not look into the future, leaving the upper-right corner of the table empty.

Excerpt from paper Figure 2, arXiv:2307.08691v1, PDF page 8.

The first worker computes the first group of rows, the second worker the next group. Both may read the same K,VK,V tile, but they need not exchange intermediate softmax results. In our earlier example with one batch and eight heads, each head performs its own attention calculation. If we split each head's query rows into 16 groups, eight work orders become 8×16=1288\times16=128. Sixteen is just an illustration; the actual count depends on tile size. Either way, a longer sequence can now finally create more pieces of parallel work.

Why does the right panel switch to columns? The backward pass computes dQ,dK,dVdQ,dK,dV, the gradients sent back to Q,K,VQ,K,V. A K,VK,V tile receives contributions from many query rows. Giving one worker a column lets it accumulate that column's dK,dVdK,dV itself.

dQdQ, in contrast, receives contributions from different columns. Those workers use atomic adds when updating dQdQ, so simultaneous writes do not overwrite one another. Forward workers own output rows; backward workers own K,VK,V gradients.

Divide at the end

A worker assigned some query rows still has to read K,VK,V tile by tile. But the softmax denominator is not known until we have seen every score in the row. Could we divide the partial output after every tile? Yes; the first generation does. But if the next tile contains a higher score, we must rescale and divide again.

Let us work through a few numbers.

Split one row of scores into [3,1][3,1] and [4,2][4,2], with corresponding VV values [1,0][1,0] and [3,2][3,2]. To keep exponentials under control, use the largest score seen so far, mm, as a reference. Also keep the sum of exponentials ℓ\ell and the weighted sum UU, before division.

DOCSAID diagram based on FlashAttention-2 Algorithm 1: two score tiles and a single final division, O = U / ℓ.

Start with the first tile in the diagram. Its maximum score is 33, so ℓ1=e3−3+e1−3=1+e−2≈1.1353\ell_1=e^{3-3}+e^{1-3}=1+e^{-2}\approx1.1353. Its weighted sum is U1=1×1+e−2×0=1U_1=1\times1+e^{-2}\times0=1. The first generation would calculate a partial output, U1/ℓ1≈0.8808U_1/\ell_1\approx0.8808, at this point. The second generation keeps ℓ1\ell_1 and U1U_1 without dividing.

The second tile brings a higher score, 44. Old values used 33 as their reference. To put everything on the new scale, multiply the old ℓ1,U1\ell_1,U_1 by e3−4=e−1e^{3-4}=e^{-1}. Add the second tile to obtain ℓ2=e−1ℓ1+1+e−2≈1.5530\ell_2=e^{-1}\ell_1+1+e^{-2}\approx1.5530 and U2=e−1U1+3+2e−2≈3.6386U_2=e^{-1}U_1+3+2e^{-2}\approx3.6386. Only after both tiles are done do we divide: O=U2/ℓ2≈2.3429O=U_2/\ell_2\approx2.3429. Softmax over the whole row gives the same answer.

In general, let SjS_j be a newly read tile of scores and VjV_j its values. A prime marks the state after that tile:

m′=max⁡(m,max⁡Sj),ℓ′=em−m′ℓ+∑eSj−m′,U′=em−m′U+eSj−m′Vj.\begin{aligned} m'&=\max(m,\max S_j),\\ \ell'&=e^{m-m'}\ell+\sum e^{S_j-m'},\\ U'&=e^{m-m'}U+e^{S_j-m'}V_j. \end{aligned}

The factor em−m′e^{m-m'} is the e−1e^{-1} in our diagram, which moves the old denominator and weighted sum onto the new reference scale. The remaining terms add the new tile's exponentials to ℓ′\ell' and its value-weighted contribution to U′U'.

In real attention, VjV_j contains vectors, so UU is a vector too. The diagram uses single numbers so we can work it out by hand. Each query row maintains its own m,ℓ,Um,\ell,U and computes O=U/ℓO=U/\ell only when it is finished.

The backward pass must recompute attention weights. The authors save just one normalization number per row, L=m+log⁡ℓL=m+\log\ell. Since eL=emℓe^L=e^m\ell, a score SijS_{ij} has weight Pij=eSij−LiP_{ij}=e^{S_{ij}-L_i}. Scores are still recomputed, but there is no need to retain the full weight matrix or save mm and ℓ\ell separately.

Why bother saving a few divisions? The paper lists theoretical A100 throughput of 312 TFLOPs/s for FP16/BF16 matrix multiplication and 19.5 TFLOPs/s for ordinary FP32 operations. Reducing the latter leaves more time for the matrix multiplications Tensor Cores do best.

Reassign the warps

More thread blocks give more SMs work. Now open one of those blocks and look at its warps. In the paper's Figure 3, orange dashed outlines mark data split among warps; blue dashed outlines mark data available to all of them.

Excerpt from paper Figure 3, arXiv:2307.08691v1, PDF page 9.

On the left, four warps share the same QQ, but each gets part of K,VK,V. When they finish, each holds only part of the same output rows. To deliver complete rows, they write partial results to shared memory, wait, read them back, and combine them. The paper calls this split-K.

The right panel reverses the division, letting every warp use K,VK,V while QQ is split four ways. The first warp produces its own output rows, the second produces the next group. Each output row has one owner, so the forward pass no longer needs a shared-memory meeting to piece it together. Backward gradients still have dependencies and require some synchronization.

The two levels now line up. A head's query rows are distributed among more blocks, and each block's rows are divided among its warps. Within each row, the softmax division waits until the end.

Discussion

Measure attention first

The paper's Figure 4(a) compares attention forward plus backward on an A100 80GB SXM4, without a causal mask and with a head dimension of 64. The horizontal axis is sequence length. The vertical axis is throughput in TFLOPs/s, calculated using the paper's FLOP formula; at the same setting, a higher bar means a faster run. Orange marks the first generation and purple the second.

Excerpt from paper Figure 4(a), arXiv:2307.08691v1, PDF page 10.

At 8k, the first generation reaches 110 TFLOPs/s and the second 175, a ratio of 175/110≈1.59175/110\approx1.59. At 16k the numbers are 110 and 176. PyTorch is marked OOM at the far right because it ran out of memory in that setting.

For this chart, the authors hold the total number of tokens per test at 16k, so longer sequences mean a smaller batch, a point that ties back to the opening. At 8k the batch is 2; at 16k it is 1.

This chart uses 32 heads. At 16k, the first generation has only 1×32=321\times32=32 pieces of work from batch and head, facing 108 SMs on the A100. Splitting the query rows into additional blocks addresses that shortage of parallel work.

Then measure the whole training run

A faster attention layer is one thing. What about the whole model? The paper's Table 1 trains GPT-style models on eight A100s, comparing no FlashAttention, the first generation, and the second. The 1.3B and 2.7B labels are parameter counts; 2k and 8k are context lengths in tokens. Within one row of the table, a higher TFLOPs/s per GPU means higher training throughput.

Excerpt from paper Table 1, arXiv:2307.08691v1, PDF page 12.

Read across the two 1.3B rows. At 2k context, the first generation scores 189 and the second 196 TFLOPs/s, an increase of about 4%. At 8k, it goes from 170 to 220, about 29%. The 2.7B model at 8k similarly rises from 175 to 225, about 29%. Without FlashAttention, that same row reaches only 80, making the second generation about 2.8 times faster.

In this table, the shorter context gains relatively little while longer-context training gains more. That fits the reason for adding parallel work along the sequence.

Finally, the authors turn the peak 225 TFLOPs/s into 72% model FLOPs utilization. Utilization of the 108 SMs is a separate hardware metric. Table 1 divides a model-FLOP estimate by elapsed time. Following the convention used in earlier work, its formula does not subtract the roughly half of the attention score table omitted by causal masking. The numbers can compare training throughput under the same row's conditions.

Conclusion

The first FlashAttention addressed too much data movement. The second asks how to distribute the work.

It launches more thread blocks along the query sequence so more SMs can work at once, rearranges warps to reduce their exchanges, and changes the order of online-softmax operations to save some work outside matrix multiplication.

The design later became an acceleration option in PyTorch SDPA and Hugging Face. Still, dense attention grows quadratically with sequence length, and the best arrangement for an A100 need not be the best on an H100 or B200.

After all, if everyone looks busy, does that mean the whole production line is efficient?

Next time, the H100 takes the floor.