Skip to content

FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness ​

所属主题

原笔记参考:知乎文章。

Background ​

Self-Attention 的计算过程是: 三个矩阵 Q,K,V∈RN×d,Self-Attention 计算如下:

  • S=QKT/d∈RN×N (1)
  • P=softmax(S)∈RN×N (2)
  • O=PV∈RN×d (3)

Self-Attention 中(1) 和 (3) 的计算最密集,(1) 和 (3) 中的矩阵乘法复杂度为 O(dN2)。若把 N×N 的分数和概率矩阵物化到 HBM,中间张量读写会成为显著成本。FlashAttention 的出发点是减少这部分 IO;具体是否受带宽限制仍取决于硬件和问题规模。

标准的 Attention 算法对于 (1) 需要从 HBM 读取 2 次,写入 1 次,对于 (2) 需要从 HBM 读取一次,写入一次,对于 (3) 需要从 HBM 读取 2 次写入一次。为了减少对于 HBM 的读写,FlashAttention 分块将数据送入 SRAM。但分块后需要计算 softmax,而 softmax 需要读取一行作为分母,因此难点主要在分块算 softmax。

FlashAttention Design ​

softmax(xi)=exi∑j=1Bexj (4) 为了避免溢出,大多数深度学习框架都使用的 softmax 的稳定版本:

  • m(x)=max([x1,x2,...xB]) (5)
  • f(x)=[ex1−m(x),...exB−m(x)] (6)
  • l(x)=∑if(xi) (7)
  • softmax(x)=f(x)l(x) (8)

分块后保存每块的最大值 m 和指数和 l;合并两块时,先把指数尺度统一到新的最大值,再相加,而不是平均两个局部 softmax。

例如两块分别包含分数 [0] 与 [ln⁡2]。局部状态为 (m1,l1)=(0,1)、(m2,l2)=(ln⁡2,1)。统一到 m=ln⁡2 后,指数和为 l=e0−m+eln⁡2−m=1.5,两个位置的权重为 1/3、2/3,与整行 softmax 一致。对输出的加权和也做同样的尺度修正,就无需保存整行概率。

完整递推见 online softmax 与 FlashAttention 版本演进。

论文 Algorithm 1:

  • L1: 根据 SRAM 的大小选择合适的分块大小 Bc 和 Br。

  • L2:初始化一些变量

  • L3 & L4: 将矩阵 Q,O 沿着行方向切分成 Tr 块,将向量 l,m 切成 Tr 块,将 K,V 沿着行方向切成 Tc 块。

  • L5: 外循环遍历 K,V

  • L6: 将遍历的 Kj,Vj 从 HBM 读入 SRAM。

  • L7: 内循环遍历

  • L8: 内循环变量读入 SRAM

  • L9: 使用当前遍历的 Qi,Kj,计算分块的 Attention Score = QiKjT/d∈RBr×Bc

  • L10:对于分块的 Attention Score,计算每一行的最大值,指数项,求和项

  • L11: 更新 mi,li

这些步骤解释前向的分块数据流;原版 Algorithm 1 的 K/V 外循环组织不应直接套用到所有后续 FlashAttention 版本。

记录原理、连接知识、积累实践。