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

Question

我需要对这个C模块实现SSE（vector operations），但是无法获得关于这个技术的足够信息，对此有什么线索或解决方案吗？
另外，如果你对这里的代码有什么建议，我也在听。

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];
    }
} 

}

Answer 1

您的总体方法可能是计算新元素的整个SIMD向量（或者并行计算多行的多个向量），而不是在继续之前尝试为一个元素执行所有操作。如果在局部变量（寄存器）中保持足够的加载量，则可以沿行进行适当的工作。可能将4行中的1行复制到临时缓冲区。
您可能应该使用int8_t元素来获得每个向量4倍于unsigned的数量，特别是如果您可以使用SSSE3_mm_shuffle_epi8或_mm_alignr_epi8，而不是仅使用SSE2_mm_shuffle_epi32或psrldq（字节移位）或未对齐的加载来获得多个偏移。
你只处理从-1到9的整数，所以这就是你所需要的。您可以使用0/-1作为您的真/假状态，这样您就可以直接使用SIMD比较结果，而不需要掩蔽来获得0/1。（用减法相加，即_mm_sub_epi8。或者只需添加then并对与之比较的常量求反即可）。
每个元素实际上只有1个有效位，但是能够在相同的向量宽度内将9个元素相加具有优势。SIMD比较get只有字节那么小。不过，半字节可以有效地解包，并且可以使数据密度加倍（将内存带宽减半）。
Dan Lemire发表了一个使用AVX2内部函数（blog post）的生命工作实现。他在他未指明的机器上得到了25倍的加速比标量C（当然是启用了优化）；我想我记得他在我谈论他的UTF-8验证器时说他有一个Haswell。
正如他指出的，3x3访问模式与许多图像处理卷积滤波器相同。看起来他不像你那样实现了圆形边界条件。您可以使SIMD循环的开始/结束1远离边界，并使用wrap-around对这些元素执行标量操作。
Hiscomputecounts8vec()athttps://github.com/lemire/SIMDgameoflife/blob/master/include/basicautomata.h#L94使用未对齐的加载来获取偏移向量。因此，x1+132字节的加载会使下一次迭代中的x1-1加载重载2字节。对于16字节向量，使用一些_mm_alignr_epi8从两个对齐的负载创建这些移动窗口可以节省未对齐的负载，这可能是一个好主意，但对于32字节向量（__m256i），车道内行为使其几乎不适合其原始用途。
一次计算两行或三行将允许更多的数据重用（一个输出行的中间行是下一个输出行的顶部源行）。甚至在下一行中重用low+mid sum作为mid+hi sum。
可能对一行或两行使用palignr策略，而对另两行使用未对齐的加载策略，在一次传递中执行的3行或4行的每个条带中。
我们不会从L1d获得通常的每时钟2个矢量的负载带宽，因为跨越缓存线边界会导致速度减慢。它仍然只有1个uop，但是它需要两次访问L1d。因此，在某种程度上用随机uop替换一些加载uop是很好的，特别是在AMD CPU上，在AMD CPU上，随机吞吐量更高，只有不需要额外的随机洗牌，32字节向量才值得。（与英特尔不同，它们在AMD上被分成两个16字节的操作。）
我想知道我们是否可以使用一种密度较小的编码，它可以在每个块中填充或重复一个元素，从而只允许加载一个向量并移动它来获得偏移量。
或者可能是一个更密集的编码，我们无论如何都必须扩展（像压缩位），所以我们有额外的数据加载。
代码审查
在C中使用新的变量名对那些还知道C++的程序员来说是非常有敌意的。我推荐另一个名字，所以这个代码也是有效的C++，用于在C++中实现C99 VLAS的编译器。另外，让调用者传入src和目标缓冲区，并使用unsigned *__restrict dst[h]，unsigned *__restrict src[h]以便编译器知道它们不会重叠。然后，您可以在两个缓冲区之间进行替换，而不是每次都执行复制和whatever+复制。
特别处理包装边界条件，而不是将(x1+w)%w放入最内部的循环。这很可能编译成硬件idiv指令，因为编译器可能不知道它只能包装一次，而且w不是编译时常量。（除非是在内联之后）这可能是标量代码中的主要瓶颈。