矢量模乘法

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