Оптимизация программы Numeri c с SIMD - PullRequest
Новая
       83

Оптимизация программы Numeri c с SIMD

0 голосов
/ 28 мая 2020

Я пытаюсь оптимизировать производительность следующей наивной программы без изменения алгоритма: 

naive (int n, const int *a, const int *b, int *c)
//a,b are two array with given size n;
{
  for (int k = 0; k < n; k++)
    for (int i = 0; i < n - k; ++i)
      c[k] += a[i + k] * b[i];
}

Моя идея такова: сначала я использую OpenMP для внешнего l oop. Для внутреннего l oop, поскольку он несбалансирован, я указываю n-k, чтобы определить, использовать ли AXV2 SIMD intrinsi c или просто уменьшить . И, наконец, я обнаружил, что он имеет ускорение на 40, когда n приближается к 3E7.

Есть ли какие-либо предложения, которые могли бы заставить его работать быстрее ?

Мой код следующий: 

static int n_zero = 0;
static int MAX_CORE = omp_get_max_threads();
void naive(int n, const int *a, const int *b, int *c)
{
    omp_set_num_threads(MAX_CORE);

#pragma omp parallel for schedule(dynamic)
    for (int k = 0; k < n; k++)
    {
        if ((n - k) < MAX_CORE)
        {
            for (int i = 0; i < (n - k); i++)
            {
                c[k] += a[i + k] * b[i];
            }
        }
        else
        {
            __m256i partial_sums = _mm256_set1_epi32(n_zero);
            for (int i = 0; i < (n - k) / 32 * 32; i += 32)
            {

                __m256i vec_a_1 = _mm256_loadu_si256((__m256i *)(a + i + k));
                __m256i vec_b_1 = _mm256_loadu_si256((__m256i *)(b + i));
                __m256i partial_pd = _mm256_mullo_epi32(vec_a_1, vec_b_1);
                partial_sums = _mm256_add_epi32(partial_pd, partial_sums);

                vec_a_1 = _mm256_loadu_si256((__m256i *)(a + i + k + 8));
                vec_b_1 = _mm256_loadu_si256((__m256i *)(b + i + 8));
                partial_pd = _mm256_mullo_epi32(vec_a_1, vec_b_1);
                partial_sums = _mm256_add_epi32(partial_pd, partial_sums);

                vec_a_1 = _mm256_loadu_si256((__m256i *)(a + i + k + 16));
                vec_b_1 = _mm256_loadu_si256((__m256i *)(b + i + 16));
                partial_pd = _mm256_mullo_epi32(vec_a_1, vec_b_1);
                partial_sums = _mm256_add_epi32(partial_pd, partial_sums);

                vec_a_1 = _mm256_loadu_si256((__m256i *)(a + i + k + 24));
                vec_b_1 = _mm256_loadu_si256((__m256i *)(b + i + 24));

                partial_pd = _mm256_mullo_epi32(vec_a_1, vec_b_1);
                partial_sums = _mm256_add_epi32(partial_pd, partial_sums);
            }

            int arr[] = {0, 0, 0, 0, 0, 0, 0, 0};
            _mm256_storeu_si256(((__m256i *)arr), partial_sums);
            for (int i = 0; i < 8; i++)
            {
                c[k] += arr[i];
            }

            for (int i = (n - k) / 32 * 32 + k; i < n; i++)
            {
                c[k] += a[i] * b[i - k];
            }
        }
    }
}
...