Векторизация модульной арифметики

Я пытаюсь написать достаточно быстрый код сложения векторов по компонентам. Я работаю с (подписанными, я полагаю) 64-битными целыми числами.

Функция

void addRq (int64_t* a, const int64_t* b, const int32_t dim, const int64_t q) {
    for(int i = 0; i < dim; i++) {
        a[i] = (a[i]+b[i])%q; // LINE1
    }
}

Я компилирую с помощью icc -std=gnu99 -O3 (icc, чтобы позже использовать SVML) на IvyBridge (SSE4.2 и AVX, но не AVX2).

Мой базовый уровень — удаление %q из LINE1. 100 (повторяющихся) вызовов функций с dim=11221184 занимают 1,6 секунды. ICC автоматически векторизует код для SSE; отличный.

Я действительно хочу сделать модульные дополнения, хотя. С %q ICC не выполняет автоматическую векторизацию кода и выполняется за 11,8 секунды (!). Даже если не учитывать автовекторизацию для предыдущей попытки, это все равно кажется чрезмерным.

Поскольку у меня нет AVX2, для векторизации с помощью SSE требуется SVML, возможно, поэтому ICC не выполняет автоматическую векторизацию. Во всяком случае, вот моя попытка векторизовать внутренний цикл:

__m128i qs = _mm_set1_epi64x(q);
for(int i = 0; i < dim; i+=2) {
    __m128i xs = _mm_load_si128((const __m128i*)(a+i));
    __m128i ys = _mm_load_si128((const __m128i*)(b+i));
    __m128i zs = _mm_add_epi64(xs,ys);
    zs = _mm_rem_epi64(zs,qs);
    _mm_store_si128((__m128i*)(a+i),zs);
}

Сборка для основного цикла:

..B3.4:                         # Preds ..B3.2 ..B3.12
    movdqa    (%r12,%r15,8), %xmm0                          #59.22
    movdqa    %xmm8, %xmm1                                  #60.14
    paddq     (%r14,%r15,8), %xmm0                          #59.22
    call      __svml_i64rem2                                #61.9
    movdqa    %xmm0, (%r12,%r15,8)                          #61.36
    addq      $2, %r15                                      #56.30
    cmpq      %r13, %r15                                    #56.24
    jl        ..B3.4        # Prob 82%                      #56.24

Таким образом, код векторизуется, как и ожидалось. Я знаю, что могу не получить 2-кратного ускорения из-за SVML, но код выполняется за 12,5 секунд, медленнее, чем без векторизации вообще! Это действительно лучшее, что здесь можно сделать?


c x86-64 assembly sse intrinsics
person crockeea    schedule 16.12.2013    source источник
comment
Вызов функции по модулю убивает производительность. Есть ли у вас априорные знания о возможных значениях q?   -  person Paul R    schedule 16.12.2013
comment
Если вы знаете, что входные данные полностью уменьшены, вам лучше использовать сравнение и условное вычитание.   -  person Mysticial    schedule 16.12.2013
comment
@PaulR q должен оставаться (в основном) постоянным во время выполнения, но это не будет известно во время компиляции. Как это может быть выгодно?   -  person crockeea    schedule 16.12.2013
comment
@Mysticial Интересно, что условное вычитание заняло всего 1,9 секунды, что может быть правдоподобно, но ICC не выполнила векторизацию. Я понятия не имею, как это так быстро.   -  person crockeea    schedule 16.12.2013
comment
@Eric Вы можете выполнять условные операции с SIMD. Инструкции сравнения возвращают вектор либо из всех нулей, либо из единиц, который затем можно объединить с другим значением и вычесть из целевого.   -  person Mysticial    schedule 16.12.2013
comment
@ Эрик, я добавил код SSE в свой ответ на основе комментария Mystical.   -  person Z boson    schedule 18.12.2013
comment
@Zboson К счастью, ICC автоматически векторизует код условного вычитания!   -  person crockeea    schedule 19.12.2013

Ответы (1)


arrow_upward
12
arrow_downward

Ни в SSE2, ни в AVX2 нет инструкций целочисленного деления. Intel неискренне называет встроенные функции SVML, поскольку многие из них являются сложными функциями, которые сопоставляются с несколькими инструкциями, а не только с несколькими.

Есть способ сделать более быстрое деление (и по модулю) с помощью SSE2 или AVX2. См. эту статью Улучшенное деление на инвариантные целые числа. В основном вы предварительно вычисляете делитель, а затем выполняете умножение. Предварительное вычисление делителя требует времени, но для некоторого значения dim в вашем коде оно должно победить. Я описал этот метод более подробно здесь целочисленное деление SSE? Я также успешно реализовал этот метод в простом числе finder Поиск списков простых чисел с помощью SIMD - SSE/AVX

Агнер Фог реализует 32-битное (но не 64-битное) разделение в своем Vector Class используя метод, описанный в этой статье. Это было бы хорошим местом для начала, если вам нужен какой-то код, но вам придется расширить его до 64-битной версии.

Редактировать: основываясь на комментариях Mysticial и предполагая, что входные данные уже уменьшены, я создал версию для SSE. Если это скомпилировано в MSVC, то оно должно быть в 64-битном режиме, поскольку 32-битный режим не поддерживает _mm_set1_epi64x. Это можно исправить для 32-битного режима, но я не хочу этого делать.

#ifdef _MSC_VER 
#include <intrin.h>
#endif
#include <nmmintrin.h>                 // SSE4.2
#include <stdint.h>
#include <stdio.h>

void addRq_SSE(int64_t* a, const int64_t* b, const int32_t dim, const int64_t q) {
    __m128i q2 = _mm_set1_epi64x(q);
    __m128i t2 = _mm_sub_epi64(q2,_mm_set1_epi64x(1));
    for(int i = 0; i < dim; i+=2) {
        __m128i a2 = _mm_loadu_si128((__m128i*)&a[i]);
        __m128i b2 = _mm_loadu_si128((__m128i*)&b[i]);
        __m128i c2 = _mm_add_epi64(a2,b2);
        __m128i cmp = _mm_cmpgt_epi64(c2, t2);
        c2 = _mm_sub_epi64(c2, _mm_and_si128(q2,cmp));
        _mm_storeu_si128((__m128i*)&a[i], c2);
    }
}

int main() {
    const int64_t dim = 20;
    int64_t a[dim];
    int64_t b[dim];
    int64_t q = 10;

    for(int i=0; i<dim; i++) {
        a[i] = i%q; b[i] = i%q;
    }
    addRq_SSE(a, b, dim, q);
    for(int i=0; i<dim; i++) {
        printf("%d\n", a[i]);
    }   
}
person Z boson    schedule 16.12.2013