如何选择并实现高性能纠删码编码引擎（下)(2)

从上面的对比中,我们不难发现采用SIMD的新算法提高查表速度主要表现在两个方面：
减少了乘法表大小；
提高查表并行度(从1个字节到16甚至32个字节)
采用SIMD指令在大大降低了乘法表的规模的同时多了一次查表操作以及异或运算.由于新的乘法表每一部分只有16字节,我们可以顺利的将其放置于XMM寄存器中,从而利用SIMD指令集提供的指令来进行数据向量运算,将原先的逐字节查表改进为并行的对16字节进行查表,同时异或操作也是16字节并行的.除此之外,由于乘法表的总体规模的下降,在编码过程中的缓存污染也被大大减轻了,关于缓存的问题我们会在接下来的小节中进行更细致的分析.
以上的计算过程以单个字节作为例子,下面我们一同来分析利用SIMD技术对多个字节进行运算的过程.基本步骤如下：
拆分保存原始数据的XMM寄存器中的数据向量,分别存储于不同的XMM寄存器中
根据拆分后的数据向量对乘法表进行重排,即得到查表结果.我们可以将乘法表理解为按顺序排放的数组,数组长度为16,查表的过程可以理解为将拆分后的数据(数据范围为0-15)作为索引对乘法表数组进行重新排序.这样我们就可以通过排序指令完成查表操作了
将重排后的结果进行异或,得到最终的运算结果
以下是伪代码：

需要注意的是,要使用SIMD加速有限域运算,对CPU的最低要求是支持SSSE3扩展指令集.另外为了充分提高效率,我们应该事先对数据进行内存对齐操作,在SSSE3下我们需要将数据对齐到16Bytes,否则我们只能使用非对齐指令进行数据的读取和写入.在这一点上比较特殊的是Go语言,一方面Go支持直接调用汇编函数这为使用SIMD指令集提供了语言上的支持；但另外一方面Golang又隐藏了内存申请的细节,这使得指定内存对齐操作不可控,虽然我们也可以通过cgo或者汇编来实现,但这增加额外的负担.所幸,对于CPU来说一个Cacheline的大小为64byte,这在一定程度上可以帮助我们减少非对齐读写带来的惩罚.另外,根据Golang的内存对齐算法,对于较大的数据块,Golang是会自动对齐到32byte的,因此对齐或非对齐指令的执行效果是一致的.

2.2写缓存友好代码

缓存优化通过两方面进行,其一是减少缓存污染；其二是提高缓存命中率.在尝试做到这两点之前,我们先来分析缓存的基本工作原理.

CPU缓存的默认工作模式是Write-Back,即每一次读写内存数据都需要先写入缓存.上文提到的Cacheline即为缓存工作的基本单位,其大小为固定的64byte,也就说哪怕从内存中读取1字节的数据,CPU也会将其余的63字节带入缓存.这样设计的原因主要是为了提高缓存的时间局域性,因为所要执行的数据大小通常远远超过这个数字,提前将数据读取至缓存有利于接下来的数据在缓存中被命中.

2.2.1矩阵运算分块

矩阵运算的循环迭代中都用到了行与列,因此原始数据矩阵与编码矩阵的访问总有一方是非连续的,通过简单的循环交换并不能改善运算的空间局域性.因此我们通过分块的方法来提高时间局域性来减少缓存缺失.

分块算法不是对一个数组的整行或整列进行操作,而是对其子矩阵进行操作,目的是在缓存中的数据被替换之前,最大限度的利用它.

分块的尺寸不宜过大,太大的分块无法被装进缓存；另外也不能过小,太小的分块导致外部逻辑的调用次数大大上升,产生了不必要的函数调用开销,而且也不能充分利用缓存空间.

2.2.2减少缓存污染

不难发现的是,编码矩阵中的系数并不会完全覆盖整个GF(2^8),例如10+4的编码方案中,编码矩阵中校验矩阵大小为4×10,编码系数至多(可能会有重复)有10×4=40个.因此我们可以事先进行一个乘法表初始化的过程,比如生成一个新的二维数组来存储编码系数的乘法表.缩小表的范围可以在读取表的过程中对缓存的污染.

另外在定义方法集时需要注意的是避免结构体中的元素浪费.避免将不必要的参数扔进结构体中,如果每一个方法仅使用其中若干个元素,则其他元素白白侵占了缓存空间.

三指令级并行与数据级并行的深入优化

本节主要介绍如何利用AVX/AVX2指令集以及指令级并行优化来进一步提高性能表现.除此之外,我们还可以对汇编代码进行微调以取得微小的提升.比如,尽量避免使用R8-R15这8个寄存器,因为指令解码会比其他通用寄存器多一个字节.但很多汇编优化细节是和CPU架构设计相关的,书本上甚至Intel提供的手册也并不能提供最准确的指导(因为有滞后性),而且这些操作带来的效益并不显著,在这里就不做重点说明了.

3.1利用AVX2

在上文中我们已经知道如何将乘法表拆分成128bits的大小以适应XMM寄存器,那么对于AVX指令集来说,要充分发挥其作用,需要将乘法表复制到256bit的YMM寄存器.为了做到这一点,我们可以利用XMM寄存器为YMM寄存器的低位这一特性,仅使用一条指令来完成表的复制(Intel风格)：

vinserti128ymm0,ymm0,xmm0,1

这条指令作用是将xmm0寄存器中的数据拷贝到ymm0中,而剩余128位数据通过ymm0得到,其中立即数1表明xmm0拷贝的目的地是ymm0的高位.这条指令提供了两个sourceoperand(源操作数)以及一个destinationoperand(目标操作数),我们在这里使用ymm0寄存器同时作为源操作数和目标操作数来实现了表的复制操作.接下来我们便可以使用与SSSE3下同样的方式来进行单指令32byte的编码运算过程了.

（编辑：ASP站长网）