我尝试实现性能提升,并在 SIMD 方面取得了一些良好的经验。到目前为止,我正在使用 OMP,并希望使用内在函数进一步提高我的技能。
在下面的场景中,由于元素 n+1 测试所需的 last_value 的数据依赖性,我未能改进(甚至矢量化)。
环境是具有 AVX2 的 x64,因此想要找到一种方法来矢量化和 SIMDfy 这样的函数。
inline static size_t get_indices_branched(size_t* _vResultIndices, size_t _size, const int8_t* _data) {
size_t index = 0;
int8_t last_value = 0;
for (size_t i = 0; i < _size; ++i) {
if ((_data[i] != 0) && (_data[i] != last_value)) {
// add to _vResultIndices
_vResultIndices[index] = i;
last_value = _data[i];
++index;
}
}
return index;
}
输入是有符号 1 字节值的数组。每个元素都是之一。
输出是输入值(或指针)的索引数组,表示更改为 1 或 -1。
输入/输出示例
in: { 0,0,1,0,1,1,-1,1, 0,-1,-1,1,0,0,1,1, 1,0,-1,0,0,0,0,0, 0,1,1,1,-1,-1,0,0, ... }
out { 2,6,7,9,11,18,25,28, ... }
我的第一次尝试是尝试各种无分支版本,并通过比较汇编输出来查看自动矢量化或 OMP 是否能够将其转换为 SIMDish 代码。
尝试示例
int8_t* rgLast = (int8_t*)alloca((_size + 1) * sizeof(int8_t));
rgLast[0] = 0;
#pragma omp simd safelen(1)
for (size_t i = 0; i < _size; ++i) {
bool b = (_data[i] != 0) & (_data[i] != rgLast[i]);
_vResultIndices[index] = i;
rgLast[i + 1] = (b * _data[i]) + (!b * rgLast[i]);
index += b;
}
由于没有实验产生 SIMD 输出,因此我开始尝试内在函数,目标是将条件部分转换为掩码。
对于 != 0 部分来说非常简单:
__m256i* vData = (__m256i*)(_data);
__m256i vHasSignal = _mm256_cmpeq_epi8(vData[i], _mm256_set1_epi8(0)); // elmiminate 0's
我还没有找到一种方法来测试“最后一次翻转”的条件方面。
为了解决以下输出打包问题,我假设AVX2基于面具打包剩下的最有效的方法是什么?可以工作。
Update 1
深入研究这个主题就会发现,分离 1/-1 并去掉 0 是有益的。
幸运的是,就我而言,我可以直接从预处理中获取它并使用以下命令跳过处理到 _mm256_xor_si256
例如,有 2 个输入向量分隔为 gt0(全 1)和 lt0(全 -1)。这还允许将数据打包得更紧 4 倍。
I might want to end up with a process like this
The challenge now is how to create the transition mask based on gt0 and lt0 masks.
Update 2
显然,一种将 1 和 -1 分成 2 个流的方法(参见答案如何),在访问元素以进行交替扫描时引入了依赖:如何有效地扫描每次迭代交替的 2 位掩码
创建一个过渡掩码,如 @aqrit 使用
transition mask = ((~lt + gt) & lt) | ((~gt + lt) & gt)
是可能的。尽管这增加了相当多的指令,但它似乎是消除数据依赖性的有益权衡。我假设寄存器越大增益就会增加(可能取决于芯片)。
Update 3
通过矢量化transition mask = ((~lt + gt) & lt) | ((~gt + lt) & gt)
我可以编译这个输出
vmovdqu ymm5,ymmword ptr transition_mask[rax]
vmovdqu ymm4,ymm5
vpandn ymm0,ymm5,ymm6
vpaddb ymm1,ymm0,ymm5
vpand ymm3,ymm1,ymm5
vpandn ymm2,ymm5,ymm6
vpaddb ymm0,ymm2,ymm5
vpand ymm1,ymm0,ymm5
vpor ymm3,ymm1,ymm3
vmovdqu ymmword ptr transition_mask[rax],ymm3
乍一看,与潜在条件相关的后处理陷阱(垂直扫描 + 附加到输出)相比,它显得高效,尽管处理 2 个流而不是 1 个流似乎是正确且符合逻辑的。
这缺乏在每个周期生成初始状态的能力(从 0 转换到 1 或 -1)。
不确定是否有办法增强transition_mask生成“位旋转”,或者使用auto initial _tzcnt_u32(mask0) > _tzcnt_u32(mask1)
正如 Sons 在这里使用的那样:https://stackoverflow.com/a/70890642/18030502其中似乎包括一个分支。
结论
@aqrit 分享的方法使用了改进的bit-twiddling
针对每个块加载来查找转换的解决方案被证明是运行时性能最高的。这热内循环仅 9 个 asm 指令长(每 2 个找到的项目与其他方法进行比较)使用tzcnt
and blsr
像这样
tzcnt rax,rcx
mov qword ptr [rbx+rdx*8],rax
blsr rcx,rcx
tzcnt rax,rcx
mov qword ptr [rbx+rdx*8+8],rax
blsr rcx,rcx
add rdx,2
cmp rdx,r8
jl main+2580h (...)