Fletcher 校验和的快速计算能力

摘要

校验和广泛用于校验应用(如存储和网络)中的数据完整性。 我们提出在英特尔® 处理器上快速计算校验和的方法。 我们没有采用传统的线性方法来计算输入的校验和,而是采用了一种新方法,将数据划分为几个交叉的并行流,并行计算这些分区上的校验和,然后对这些流进行复合计算,使用各分区的校验和计算有效的校验和。

简介

Fletcher 校验和旨在提供一种错误检测功能,近似于 CRC,但是性能更高(在通用处理器上)。

它可执行许多加和计算,其中 C(0) 是对输入字加和,C(1) 是对 C(0) 加和进行加和计算等。一般情况下,和是对模 M 的运算。在某些情况下,M=2K,直接丢掉了高阶。 还有一些情况,M=2K-1。

ZFS 是一款常见的文件系统,由 Sun Microsystems 首创,采用开源形式。 该系统的一个特性是保护数据不被损坏。 为此,它广泛使用了基于 Fletcher 的校验和或 SHA-256 散列。 校验和的成本远低于加密散列函数(如 SHA-256),但是仍可从优化中获益。

ZFS 使用的 Fletcher 变量是在四个和(即 C(0)…C(3))的基础上处理 32 位输入数据块 (DWORDS) 并对模 264 进行加和得出。

虽然 Fletcher 的标量实施能够获得不错的性能,但是本文展示的方法能够利用英特尔处理器的矢量处理性能进一步提升性能。 该实施是专门针对 ZFS 中使用的 Fletcher 变量定制的,但是这种方法也适用于其他变量。

实施

如果将输入流当作一个 DWORDs(数据)阵列,而且校验和包含 4 个 QWORDS (A、B、C、D;初始化为 0),那么校验和可定义为:

for (i=0; i<end; i++) {
	A += data[i];
	B += A;
	C += B;
	D += C;
}

当尝试对其加速时,显然可以使用 SIMD 指令和注册器。 但是此外还一些其他的方法可以实现。

一种方法是将输入缓冲区分为 4 个连续块(即第一个四等分块,第二个四等分块等),分别计算每个块的校验和,然后将其整合起来。 这种方法存在两个问题。 除非缓冲区的大小固定,否则如果每个缓冲区的尺寸不同,那么各部分的组合方式就会不同。 此外,第一次相加需要一次集合运算,以收集 4 个输入值,而这会增加额外的开销。 这一开销可通过展开循环,从每个分块中读取多个 DWORDS,然后“转置”寄存器来实现。 但是,读取数据仍然会消耗大量的开销。

最有效的方法是采用简单的标量循环,将其实施到 SIMD 指令中,如

.sloop
	vpmovzxdq  data, [buf]	; loads DWORD data into QWORD lanes
	add	   buf, 16
	vpaddq	   a, a, data
	vpaddq	   b, b, a
	vpaddq	   c, c, b
	vpaddq	   d, d, c
	cmp	   buf, end
	jb	   .sloop

这可有效对缓冲区进行条带化处理,以便通道 j 能够在 DWORDS (4 i + j) 上计算校验和。 这种方法不会带来额外的开销(如尝试封送输入数据);但是,您需要通过这四个部分的校验和来计算实际的校验和。 所幸,在这种方法中,无需根据输入缓冲区的大小来计算。

如果 “a” 是 “a” ymm 寄存器等的值的 DWORD 指针,那么最后的校验和运算可简化为如下方式:

    A =    a[0] +    a[1] +    a[2] +    a[3];

    B =         -    a[1] -  2*a[2] -  3*a[3] 
      +  4*b[0] +  4*b[1] +  4*b[2] +  4*b[3];

    C =                        a[2] +  3*a[3] 
      -  6*b[0] - 10*b[1] - 14*b[2] - 18*b[3]
      + 16*c[0] + 16*c[1] + 16*c[2] + 16*c[3];

    D =                             -    a[3]
      +  4*b[0] + 10*b[1] + 20*b[2] + 34*b[3]
      - 48*c[0] - 64*c[1] - 80*c[2] - 96*c[3]
      + 64*d[0] + 64*d[1] + 64*d[2] + 64*d[3];

论证

让 Fi 充当处理 i DWORDS 后的校验和。

用一系列的 DWORDS 代表输入流:x1、x2、x3...

展开循环后,您可以看到 F 的元素就是输入 DWORDS 的加权和:

Figure 1

这非常不便,因为 X1(举例)的系数会因考虑的元素个数而异。 对输入进行重新编号会更方便,这样 y1 是最新处理的 DWORD,y2 是第二新,以此类推。也就是,如果我们处理了 n 个 DWORDS,那么 yi = xn+1-i

然后我们发现

Figure 2

或者,一般而言

Figure 3

这就是我们想要的运算结果。 但是,当我们使用 SIMD 指令时,将会每 4 个 DWORD 计算一次校验和。 如果我们考虑 3(对应 y1、y5 等),那么,我们实际的运算结果是:

Figure 4

而我们想要该部分和得出的是(用 (4i-3) 替换 i):

Figure 5

如果我们计算以下部分校验和的加权和:

Figure 6

结果显示,(A”3 B”3 C”3 D”3) 与 (A3 B3 C3 D3) 相同,对应的是上图中复合计算的粗体(通道 3)项。

您可以为其他三个通道执行相同的计算。

出色性能

本部分提供的结果是在英特尔® 酷睿™ i7-4770 处理器上测量得出的。 这些测试运行于单个内核,其中英特尔® 睿频加速技术关闭,英特尔® 超线程技术(英特尔® HT 技术)关闭并开启1。 这些测试运行于 16MB 缓冲区上,该缓冲区在高速缓存中进行了预热,这样复合计算的成本便会非常少。

本文中介绍的 SIMD 版本是与知名的标量实施相比,后者是基本的按系数 4 展开循环的标量实施。 结果(周期/DWORD)是2

 HT 关闭HT 开启
标量1.621.56
SIMD0.970.78

得益于处理器的超级标量特性,简单标量版本的性能很高。 由于每个 DWORD 的处理需要 4 次相加,所以每个周期的相加频率为 2.5 (不包括地址更新或比较)。

英特尔® 高级矢量扩展指令集(英特尔® AVX2)SIMD 版本以每周期约 4 次的相加频率运行。

SIMD 在英特尔 HT 技术下展现出更出色的标量计算性能,性能约可提升 24%,而标量版本仅提升 4%。

最后的合并操作需要增加几个周期,所以对于较小的缓冲区而言,标量方法更快;而对于较大的缓冲区,SIMD 方法则可更好地提升性能。 对于支持英特尔® 高级矢量扩展指令集 512(英特尔® AVX-512)的处理器,矢量宽度需要提升 1 倍,以处理 8 个并行操作。 对于较大数据缓冲区,相比英特尔 AVX2,这能够提升近 1 倍的性能。

结论

本文展示了提升校验和性能的方法。 通过利用处理器中的 SIMD 等架构特性和结合使用创新软件技术,能够显著提升性能。

作者

Jim Guilford 和 Vinodh Gopal 是英特尔数据中心事业部的架构师,主要关注领域为与加密和压缩相关的软硬件特性。

注释

1 英特尔技术可能要求激活支持的硬件、特定软件或服务。 实际性能会因您使用的具体系统配置的不同而有所差异。 请咨询您的系统制造商或零售商。

2 性能测试中使用的软件和工作负载可能仅在英特尔® 微处理器上针对性能进行了优化。 诸如 SYSmark* 和 MobileMark* 等测试均系基于特定计算机系统、硬件、软件、操作系统及功能。 上述任何要素的变动都有可能导致测试结果的变化。 请参考其它信息及性能测试(包括结合其它产品使用时的运行性能)以对目标产品进行全面评估。

有关编译器优化的更完整信息,请参阅优化通知