↓ 跳过正文
  1. Posts/

Kahan Summation:用一个补偿变量挽回 FP32 累加丢失的精度

·2302 字·5 分钟

上一篇从浮点误差谈到 GPU 计算时,我提到了 H20 上的精度取舍:量化特征要做横截面累加,而 FP64 吞吐受限,直接用 FP32 又需要留意累加误差。Kahan 补偿求和看起来是个值得考虑的工具,但当时我把它的能力说得太满了。

上一篇写了误差界从 \(O(N\epsilon)\) 降到 \(O(\epsilon)\),还说它能拿到接近 FP64 的结果。这两句话都需要限定条件:前者描述的不是任意输入上的结果相对误差,后者也不是保证。顺着一个具体例子算一遍,我才看清补偿项能帮到哪里,又会在哪里丢失。

小数加到大数上,丢掉了什么
#

在默认的最近舍入、遇到中点取偶数规则下,用 FP32 按顺序累加 [1e8, 1, 1, -1e8],结果是 0,精确和是 2。在 1e8 附近,相邻 FP32 数之间的间距是 8;两个 1 分别加进去时,每次都被舍回 1e8,最后再减去 1e8 就只剩下 0。

我最初以为补偿求和会把这两个 1 都找回来。实际按标准 Kahan 算,这个序列的结果仍然是 0。补偿变量不是额外的高精度存储,它自己也要接受 FP32 舍入。

补偿项怎样参与下一次加法
#

标准 Kahan 循环可以写成下面这样。这里每一步加减都按 FP32 舍入,返回的是 running_sum:

1running_sum = FP32(0)
2rounding_residual = FP32(0)
3for input in inputs:
4    corrected_input = input - rounding_residual
5    next_sum = running_sum + corrected_input
6    rounding_residual = (next_sum - running_sum) - corrected_input
7    running_sum = next_sum
8return running_sum

running_sum 是目前保存的和,corrected_input 是当前输入减去上一轮的 rounding_residual,next_sum 是这次加法舍入后的结果。rounding_residual 记录这次加法中估计的舍入偏差,符号约定是“实际加上的量减去想加的量”:向下舍入时它为负,下一轮减去它,相当于把欠下的部分加回输入。

下图把一轮计算的输入和输出连起来:本轮保存的和与残差分别进入下一轮。

Kahan 一轮计算中和与残差的流向

比如先得到 running_sum = 1e8、rounding_residual = 0,再连续加入八个 1:

第几个 1corrected_input更新后的 running_sum更新后的 rounding_residual
11100000000-1
22100000000-2
33100000000-3
44100000000-4
551000000083
6-21000000082
7-11000000081
801000000080

前四次还没有跨过相邻数的中点;第四次恰好落在中点,按取偶规则仍舍入到 100000000。第五次的修正输入变成 5,和被舍入到 100000008,比想加的多了 3,所以残差变成正数。接下来几轮再把多加的部分扣回去。

因此,序列 [1e8, 1, 1, 1, 1, 1, 1, 1, 1, -1e8] 的普通 FP32 顺序累加得到 0,Kahan 得到 8,与精确和一致。这里补偿没有让每一步都精确,而是让之前的偏差有机会影响后续舍入。

补偿也可能被舍掉
#

回到只有两个 1 的序列:加完它们后,和仍是 1e8,残差是 -2。下一项是 -1e8,计算修正输入时要做 -1e8 - (-2);这个结果在 FP32 中又舍回 -1e8,补偿随之消失,最终仍得到 0。

[1e8, 1, -1e8] 也一样:Kahan 得到 0,精确和是 1。如果顺序换成 [1e8, -1e8, 1],先抵消大数,再加 1,普通求和和 Kahan 都得到 1。补偿减轻了部分舍入误差,但不能保证找回每个被舍掉的数,也不能消除输入顺序的影响。

这也解释了上一篇误差界的表述为什么不够准确。令精确和为 \(s=\sum_i x_i\),计算结果为 \(\hat{s}\),单位舍入误差为 \(u\)。在标准舍入、无溢出且适用标准浮点误差模型的条件下,忽略高阶项,Higham 的分析给出普通顺序求和与 Kahan 求和的绝对误差界分别近似为:

$$ |\hat{s}-s| \leq (N-1)u\sum_i |x_i| + O(u^2), \qquad |\hat{s}-s| \leq 2u\sum_i |x_i| + O(u^2). $$

改善的是乘在输入绝对值之和上的一阶系数;高阶项不能在任意长的序列中无条件忽略。如果正负数大量相消,\(|s|\) 远小于 \(\sum_i |x_i|\),即使绝对误差不大,相对于结果的误差仍可能很大;精确和为零时,通常的相对误差甚至没有定义。FP32 Kahan 也没有获得 FP64 的有效位数,不能承诺接近 FP64 的结果。

放到 GPU 上,归约顺序变了
#

串行 Kahan 的每一轮都依赖上一轮的和与残差。为了利用 GPU 并行度,一个具体方案是:每个线程对分配给自己的输入按固定顺序做 Kahan,得到一个局部和;然后用固定的树形归约合并这些局部和。这里树上的合并仍是普通 FP32 加法,局部残差不会自动变成全局补偿。

线程局部 Kahan 求和后,用固定树形归约合并局部和

这和对全部输入做一次串行 Kahan 并不等价:输入分组变了,局部和之间也会产生新的舍入误差。线程数、分块方式或树形结构变化,都可能改变结果。固定输入、分组、归约树及执行环境时,可以得到可重复的运行结果;这不是跨硬件、编译器或不同配置都逐位一致的保证。

如果改用 atomicAdd 汇总,原子操作能保证更新不互相覆盖,但不同线程到达的顺序可能变化,浮点加法又不满足结合律,因此结果也可能变化。NVIDIA 的浮点文档讨论了归约顺序与结果的关系。

还有一处实现细节不能只看伪代码:若编译器按实数代数规则重排 (next_sum - running_sum) - corrected_input,就可能把依赖舍入的补偿表达式消掉。具体实现需要检查编译选项和生成的代码,确认所需运算顺序及舍入行为被保留;CUDA 文档也指出重排和融合设置会影响浮点表达式的结果。

回到 alpha_common
#

对于约 5563 只股票的池化场景,我关心的是横截面统计量和后续排序最终偏离多少。Centering 和 Kahan 在这里处理的是不同环节:先围绕均值中心化,可以缓解用大数之差计算方差时的相消;Kahan 则针对求和过程中的舍入误差。均值本身和中心化后的运算仍会有误差,二者都不是精确计算的保证。

加权累加还有一层边界:如果 value * weight 已经在 FP32 中舍入,Kahan 看到的只是舍入后的乘积,无法恢复乘法丢掉的信息。输入量化带来的误差也需要单独看。

真正选方案时,我想在同一批有代表性的数据上比较 FP64、普通 FP32 归约,以及线程局部 Kahan 加固定树形归约,分别记录耗时和资源开销。用 FP64 Reference 对照绝对误差;对非零且远离零的参考值看相对误差,接近零时结合绝对误差判断。FP64 Reference 也有自身舍入误差,必要时还要用更高精度核对。

最后还要看下游的 Rank 和 TopK 有没有变化:两个数值结果的误差看似很小,如果候选之间的差距更小,排序仍可能改变。在这些测量完成之前,我不能断言局部 Kahan 的速度优势,也不能断言它在这组数据上足够接近 FP64。

相关文章

Numerical Stability in ML Systems:从浮点误差到 GPU 计算

起因:H20 上 FP64 只有 1 TFLOPS,但计算要的是双精度 # 写这篇笔记的直接原因是一块 H20。业务里有一块对数值精度敏感的计算,需要接近 FP64 的结果,但 H20 的 FP64 算力只有 1 TFLOPS。对照同一张卡的其他规格,这个数字有多别扭很直观:FP32 是 44 TFLOPS,FP16/BF16 Tensor Core 是 148 TFLOPS,FP8 是 296 TFLOPS,FP64 只有 1——不到 FP32 的四十分之一,而满血的 H100 上 FP64 是 34 TFLOPS。

从 Register Tiling 到 Cache Tiling:理解高性能计算中的 Data Reuse

最近在看 CMU 15-442 的 Hardware Acceleration。课件翻到 Register Tiling,一个 2×3 output tile 的例子。我盯着那页 slide 看了一会儿——Register Tiling 这个词不陌生,但要我说清楚它和 Cache Tiling 的区别,以及它们到底在优化什么,我发现自己的理解一直停在"把矩阵切成小块"这个表面。