模乘的矢量化

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进行矢量化。

一个用于32x32 => 32-bit integer multiplication的SSE4.1实现。请注意，从FP返回整数的转换是用圆整到最近的；如果您希望使用C浮点->整数转换之类的语义，可以使用截断向零(cvttps_epi32)。

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_mullo_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_mullo_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_mullo_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_mullo_epi32(_e, _p));
        _mm256_storeu_si128((__m256i*)(c + i), _c);
    }            
}

Answer 2

实际上，有一个执行此操作的内在机制：_mm256_irem_epi32

epi32