FlashAttention-2: Faster Attention with Better Parallelism and Work Partitioning
- 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}
}
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 . 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, says what we are looking for, provides the clues to compare against, and holds the content we eventually retrieve. Imagine attention scores as a table. Its rows come from , its columns from , 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 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.
The first worker computes the first group of rows, the second worker the next group. Both may read the same 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 . 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 , the gradients sent back to . A tile receives contributions from many query rows. Giving one worker a column lets it accumulate that column's itself.
, in contrast, receives contributions from different columns. Those workers use atomic adds when updating , so simultaneous writes do not overwrite one another. Forward workers own output rows; backward workers own gradients.
Divide at the end
A worker assigned some query rows still has to read 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 and , with corresponding values and . To keep exponentials under control, use the largest score seen so far, , as a reference. Also keep the sum of exponentials and the weighted sum , before division.
Start with the first tile in the diagram. Its maximum score is , so . Its weighted sum is . The first generation would calculate a partial output, , at this point. The second generation keeps and without dividing.
The second tile brings a higher score, . Old values used as their reference. To put everything on the new scale, multiply the old by . Add the second tile to obtain and . Only after both tiles are done do we divide: . Softmax over the whole row gives the same answer.
In general, let be a newly read tile of scores and its values. A prime marks the state after that tile:
The factor is the 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 and its value-weighted contribution to .
In real attention, contains vectors, so is a vector too. The diagram uses single numbers so we can work it out by hand. Each query row maintains its own and computes only when it is finished.
The backward pass must recompute attention weights. The authors save just one normalization number per row, . Since , a score has weight . Scores are still recomputed, but there is no need to retain the full weight matrix or save and 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.
On the left, four warps share the same , but each gets part of . 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 while 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.
At 8k, the first generation reaches 110 TFLOPs/s and the second 175, a ratio of . 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 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.
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.