SIMD指令用于指数运算的代码

Question

我将使用SIMD来计算快速指数运算的结果。我将与非SIMD代码进行时间比较。指数运算是使用平方乘法算法实现的。

普通（非SIMD）版本的代码：

b = 1;  
for (i=WPE-1; i>=0; --i){  
    ew = e[i];  
    for(j=0; j<BPW; ++j){  
        b = (b * b) % p;  
        if (ew & 0x80000000U)  b = (b * a) % p;  
        ew <<= 1;  
    }  
}  

SIMD版本：

   B.data[0] = B.data[1] = B.data[2] = B.data[3] = 1U;  
   P.data[0] = P.data[1] = P.data[2] = P.data[3] = p;  
   for (i=WPE-1; i>=0; --i) {  
      EW.data[0] = e1[i]; EW.data[1] = e2[i]; EW.data[2] = e3[i]; EW.data[3] = e4[i];  
      for (j=0; j<BPW;++j){  
         B.v *= B.v; B.v -= (B.v / P.v) * P.v;  
         EWV.v = _mm_srli_epi32(EW.v,31);  
         M.data[0] = (EWV.data[0]) ? a1 : 1U;  
         M.data[1] = (EWV.data[1]) ? a2 : 1U; 
         M.data[2] = (EWV.data[2]) ? a3 : 1U; 
         M.data[3] = (EWV.data[3]) ? a4 : 1U;  
         B.v *= M.v; B.v -= (B.v / P.v) * P.v;  
         EW.v = _mm_slli_epi32(EW.v,1);  
      }  
   } 

问题在于虽然计算是正确的，但 SIMD 版本比非 SIMD 版本花费更多的时间。

请帮我找出原因并提出任何有关 SIMD 编码的建议。

谢谢！
Anup

- anup

Answer 1

所有的for循环中的函数都应该是SIMD函数，而不仅仅是其中两个。为你的两个函数设置参数所花费的时间比原始示例（很可能已被编译器优化）要少得多，这种方式并不是最优的。

- BЈовић

---

+1：在标量代码和SIMD代码之间切换是昂贵的 - 对于任何给定的循环，SIMD优化需要是“全有或全无”的。 - Paul R

你的意思是我需要用SIMD（单指令多数据）替换赋值、乘法和除法操作吗？我正在使用SSE2。 我发现对于上面的示例，没有任何一种乘法函数可以一次计算4个32位数字的乘积。同样的情况也适用于除法。那么应该怎么办呢？ - anup

@anup 我看到你正在将一些数据从e1、e2、e3、e4数组复制到EW.data数组中。这是不好的。然后你对这些数据进行了一些操作。从SSE2函数中，你只使用了移位操作。如果SSE2没有你需要的功能，那么你就不能使用它。或者你必须做一些聪明的事情。 - BЈовић

我对SIMD还很陌生，因此我对它的知识不是很丰富，也不知道如何进行单个操作。你能否解释一下为什么这些赋值是不好的呢？ - anup

Answer 2

用于32位整数数据的SIMD循环通常如下所示：

for (i = 0; i < N; i += 4)
{
    // load input vector(s) with data at array index i..i+3
    __m128 va = _mm_load_si128(&A[i]);
    __m128 vb = _mm_load_si128(&B[i]);

    // process vectors using SIMD instructions (i.e. no scalar code)
    __m128 vc = _mm_add_epi32(va, vb);

    // store result vector(s) at array index i..i+3
    _mm_store_si128(&C[i], vc);
}

如果你发现需要在循环内部在标量代码和SIMD代码之间切换，那么你可能无法从SIMD优化中获得任何好处。

SIMD编程的许多技巧来自于找到使算法能够使用给定SIMD架构提供的有限指令和数据类型的方法。您通常需要利用对数据集的先验知识以获得最佳性能，例如，如果您确定您的32位整数值实际上具有适合16位范围的范围，则这将使您的算法的乘法部分更容易实现。

- Paul R