时间戳

首页 > 解决方案 > SSE 操作在 2D 数组上实现循环，其中每个输出取决于包含它的 3x3 正方形（生命游戏）

c - SSE 操作在 2D 数组上实现循环，其中每个输出取决于包含它的 3x3 正方形（生命游戏）

问题描述

我需要对这个 C 模块实现 SSE（向量操作），但无法获得足够的技术信息，有什么线索或解决方案吗？

另外，如果您对此处的代码有任何提示，我正在听。

void evolution(void *u, int w, int h){

//check_args(c, v);

unsigned (*univ)[w] = u;
unsigned new[h][w];
int itis = args.ITERATIONS;
int actualIteration = 0;

while(itis>0){

    int thisGenerationSeeds = 0;

    for(int y=0;y<h;y++){
        for(int x=0;x<w;x++){
           int n = 0;
           for(int y1=y-1;y1<=y+1;y1++){
               for(int x1=x-1;x1<=x+1;x1++){
                   if(univ[(y1+h)%h][(x1+w)%w]){
                       n++;
                       thisGenerationSeeds++;
                   }
               }
           }
           if(univ[y][x]==1){
               n--;
           }
           new[y][x] = (n==3 || (n==2 && univ[y][x]));
           //thisGenerationSeeds++ = (n==3 || (n==2 && univ[y][x]));

        }
    }   
    itis--;
    actualIteration++;

    printf("\nIteration:_%d, \n Sec Living Seeds:_%d,\n Par Living Seeds:,\n Vec Living Seeds%d",actualIteration, thisGeneration
}
for(int y=0;y<h;y++){
    for(int x=0;x<w;x++){
     univ[y][x] = new[y][x];
    }
}

}

标签： cvectorizationssesimd

解决方案

您的总体方法可能应该是计算新元素的整个 SIMD 向量（或并行计算多行的多个向量），而不是在继续之前尝试为一个元素做所有事情。如果您在局部变量（寄存器）中保留了足够的负载，您可能能够沿行就地工作。也许将 4 行中的 1 行复制到临时缓冲区。

您可能应该使用int8_t元素来获得每个向量的 4 倍与 . 相比unsigned，特别是如果您可以使用 SSSE3_mm_shuffle_epi8或_mm_alignr_epi8，而不仅仅是 SSE2_mm_shuffle_epi32或psrldq（字节移位）或未对齐的负载来获得多个偏移量。

您只需要处理从 -1 到 9 的整数，这就是 _mm_cmpgt_epi8 所需要的全部内容。您可以使用 0 / -1 作为您的真/假状态，因此您可以直接使用 SIMD 比较结果，而无需屏蔽以获得 0 / 1。（通过减法将它们相加，即_mm_sub_epi8。或者只是添加 then 并否定您比较的常数和）。

每个元素实际上只有 1 个有效位，但是能够在相同向量宽度内将 9 个元素相加具有优势。SIMD 比较只得到字节那么小。尽管如此，半字节可以有效地解包，并使您的数据密度加倍（将您的内存带宽减半）。

Dan Lemire 发布了一个使用 AVX2 内在函数的 Life 的工作实现（博客文章。他在他未指定的机器上获得了 25 倍的加速比标量 C（当然启用了优化）；我想我记得当我说话时他说他有一个 Haswell关于他的 UTF-8 验证器。

正如他所指出的，3x3 访问模式与许多图像处理卷积过滤器相同。看起来他不像你那样实现了圆形边界条件。你可以让你的 SIMD 循环开始/结束 1 远离边界，并用环绕来做这些元素的标量。

他computecounts8vec()在https://github.com/lemire/SIMDgameoflife/blob/master/include/basicautomata.h#L94使用 unaligned-loads 来获取偏移向量。所以x1+132 字节的x1-1加载使下一次迭代中的加载超载了 2 个字节。使用 16 字节向量，使用一些_mm_alignr_epi8从两个对齐的负载创建这些移位的窗口可以节省未对齐的负载，这可能是一个好主意，但对于 32 字节向量 ( __m256i)，通道内行为使其几乎无用最初的目的。

一次计算两到三行将允许更多的数据重用（一个输出行的中间行是下一个输出行的顶部源行）。 甚至将低+中和作为下一行中的中+高和重用。

也许palignr对一到两行使用策略，在你一次完成的 3 或 4 行的每个条带中使用其他两行的未对齐加载策略。
我们不会从 L1d 获得通常的 2-vectors-per-clock 负载带宽与未对齐的负载，因为跨越缓存线边界的速度变慢。它仍然只有 1 uop，但需要两次访问 L1d。因此，用 shuffle uop 替换一些负载 uop 在一定程度上是好的，尤其是在 AMD CPU 上，shuffle 吞吐量更高，并且只有在不需要额外的 shuffle 的情况下才值得 32 字节向量。（与 Intel 不同，它们在 AMD 上被分成两个 16 字节的操作。）

我想知道我们是否可以使用具有填充或重复每个块的元素的不太密集的编码，以允许仅加载单个向量并移动它以获得偏移量。

或者可能是我们必须扩展的更密集的编码（如打包位），因此我们加载了额外的数据。

代码审查

在 C 中使用 new 作为变量名对同样了解 C++ 的程序员来说是非常不利的。对于在 C++ 中实现 C99 VLA 的编译器，我建议使用另一个名称，以便此代码也是有效的 C++。此外，让调用者传入 src 和目标缓冲区，并使用unsigned *__restrict dst[h]，unsigned *__restrict src[h]因此编译器知道它们不会重叠。然后，您可以在两个缓冲区之间交替，而不是每次都进行复制和复制 + 复制回。

特殊处理包装边界条件，而不是放入(x1+w)%w最内层循环。这很可能会编译为硬件idiv指令，因为编译器可能不知道它只能包装一次，并且w不是编译时常量。（除非是在内联之后。）这可能是标量代码的主要瓶颈。

推荐阅读