矢量模乘法

Question

的我有一个函数：

void Func(const int * a, const int * b, size_t size, int p, int * c) 
{ 
    for (size_t i = 0; i < size; ++i) 
     c[i] = (a[i]*b[i])%p; 
} 

执行该功能为整数的数组许多模乘法。 所有整数都是正数。 而且我需要改善它的表现。

我想到了SSE和AVX。但他们没有将模乘法向量化的操作。 或者我错了？

也许任何人都知道任何可能性来解决这个问题？

Answer 1

起初我想指出模操作可以使用浮点数字来实现：

d % p = d - int(float(d)/float(p))*p. 

虽然操作的右侧部分的量大然后在左边这部分是可取的，因为它可以使用SSE/AVX进行矢量化。

使用SSE4.1的实现：

void Func(const int * a, const int * b, size_t size, int p, int * c) 
{ 
    __m128 _k = _mm_set1_ps(1.0f/p); 
    __m128i _p = _mm_set1_epi32(p); 
    for (size_t i = 0; i < size; i += 4) 
    { 
     __m128i _a = _mm_loadu_si128((__m128i*)(a + i)); 
     __m128i _b = _mm_loadu_si128((__m128i*)(b + i)); 
     __m128i _d = _mm_mul_epi32(_a, _b); 
     __m128i _e = _mm_cvtps_epi32(_mm_mul_ps(_mm_cvtepi32_ps(_d), _k)); // e = int(float(d)/float(p)); 
     __m128i _c = _mm_sub_epi32(_d, _mm_mul_epi32(_e, _p)); 
     _mm_storeu_si128((__m128i*)(c + i), _c); 
    }    
} 

使用AVX的实现：

void Func(const int * a, const int * b, size_t size, int p, int * c) 
{ 
    __m256 _k = _mm256_set1_ps(1.0f/p); 
    __m256i _p = _mm256_set1_epi32(p); 
    for (size_t i = 0; i < size; i += 8) 
    { 
     __m256i _a = _mm256_loadu_si128((__m256i*)(a + i)); 
     __m256i _b = _mm256_loadu_si128((__m256i*)(b + i)); 
     __m256i _d = _mm256_mul_epi32(_a, _b); 
     __m256i _e = _mm256_cvtps_epi32(_mm256_mul_ps(_mm256_cvtepi32_ps(_d), _k)); // e = int(float(d)/float(p)); 
     __m256i _c = _mm256_sub_epi32(_d, _mm256_mul_epi32(_e, _p)); 
     _mm256_storeu_si128((__m256i*)(c + i), _c); 
    }    
}