Параллельные биномиальные коэффициенты с использованием инструкций SIMD

Question

Фон

Недавно я взял старый код (~ 1998 г.) и переписал его, чтобы улучшить производительность. Раньше в базовых структурах данных c для состояния я хранил элементы в нескольких массивах, а теперь я использую необработанные биты (для случаев, когда требуется менее 64 бит). То есть, раньше у меня был массив из b элементов, а теперь у меня b битов, установленных в одном 64-битном целом числе, которые указывают, является ли это значение частью моего состояния.

Использование встроенных функций, таких как _pext_u64 и _pdep_u64 Мне удалось выполнить все операции в 5-10 раз быстрее. Я работаю над последней операцией, которая связана с вычислением идеальной функции ha sh.

Точные детали функции ha sh не слишком важны, но все сводится к вычислению биномиальные коэффициенты (n choose k - n!/((n-k)!k!) для различных n и k. В моем текущем коде для этого используется большая таблица поиска, которую, вероятно, трудно значительно ускорить самостоятельно (за исключением возможных промахов кеша в таблицу, которую я не измерял).

Но я подумал, что с помощью инструкций SIMD я смогу напрямую вычислить их для нескольких состояний параллельно и, таким образом, увидеть общий прирост производительности.

Некоторые ограничения:

• В каждом 64-битном состоянии всегда установлено ровно b бит (представляющих небольшие числа).
• Значение k в биномиальных коэффициентах относится к b и изменяется равномерно в процессе вычислений. Эти значения небольшие (в большинстве случаев <= 5). </li>
• Окончательное значение ha sh будет <15 миллионов ( легко помещается в 32 бита). </li>

Итак, я могу довольно легко выписать математику для выполнения этого параллельно и для сохранения всех операций в виде целочисленного множественного / деления без остатков, сохраняя при этом 32 бита. Общий поток:

1. Извлечь биты в значения, подходящие для инструкций SIMD.
2. Выполнить вычисление n choose k таким образом, чтобы избежать переполнения.
3. Извлечь выводит окончательное значение ha sh из каждой записи

Но я не писал код SIMD раньше, поэтому я все еще в курсе всех доступных функций и их недостатков / эффективности .

Пример:

Раньше у меня были бы данные в массиве, если бы всегда было 5 элементов:

[3 7 19 31 38]

Теперь я использую для этого одно 64-битное значение:

0x880080088

Это делает многие другие операции очень эффективными. Для идеального ha sh мне нужно эффективно вычислить что-то вроде этого (используя c для выбора):

(50c5)-(38c5) + (37c4)-(31c4) + (30c3)-(19c3) + ...

Но на практике у меня есть куча из них, чтобы вычислить, только с немного разными значениями:

(50c5)-(Xc5) + ((X-1)c4)-(Yc4) + ((Y-1)c3)-(Zc3) + ...

Все X / Y / Z ... будут разными, но форма расчета идентична для каждого.

Вопросы:

1. Разумна ли моя интуиция по поводу повышения эффективности за счет преобразования в операции SIMD? ( Некоторые источники предлагают «нет» , но это проблема вычисления одного коэффициента, а не выполнения нескольких параллельно.)

2. Есть ли что-то более эффективное, чем повторение _tzcnt_u64 вызывает извлечение битов в структуры данных для операций SIMD? (Например, я мог бы временно разбить свое 64-битное представление состояния на 32-битные фрагменты, если бы это помогло, но тогда мне не гарантировалось бы, что в каждом элементе будет установлено одинаковое количество битов.)

3. Каковы лучшие встроенные функции для вычисления нескольких последовательных операций умножения / деления для биномиальных коэффициентов, когда я знаю, что переполнения не будет. (Когда я просматриваю ссылки Intel, у меня возникают проблемы с быстрой интерпретацией наименования при просмотре всех вариантов - неясно, доступно ли то, что я хочу.)

4. Если прямое вычисление коэффициентов вряд ли будет эффективным, можно ли использовать инструкции SIMD для параллельного поиска в моей предыдущей таблице поиска коэффициентов?

несколько вопросов вместе, но, учитывая конкретный c контекст, я подумал, что было бы лучше объединить их в один.)

Answer 1

Вот одно из возможных решений, которое выполняет вычисления из таблицы поиска, используя одно состояние за раз. Вероятно, будет более эффективно делать это параллельно в нескольких состояниях вместо использования одного состояния. Примечание. Это жестко запрограммировано для фиксированного случая получения комбинаций из 6 элементов.

int64_t GetPerfectHash2(State &s)
{
    // 6 values will be used
    __m256i offsetsm1 = _mm256_setr_epi32(6*boardSize-1,5*boardSize-1,
                                          4*boardSize-1,3*boardSize-1,
                                          2*boardSize-1,1*boardSize-1,0,0);
    __m256i offsetsm2 = _mm256_setr_epi32(6*boardSize-2,5*boardSize-2,
                                          4*boardSize-2,3*boardSize-2,
                                          2*boardSize-2,1*boardSize-2,0,0);
    int32_t index[9];
    uint64_t value = _pext_u64(s.index2, ~s.index1);
    index[0] = boardSize-numItemsSet+1;
    for (int x = 1; x < 7; x++)
    {
        index[x] = boardSize-numItemsSet-_tzcnt_u64(value);
        value = _blsr_u64(value);
    }
    index[8] = index[7] = 0;

    // Load values and get index in table
    __m256i firstLookup = _mm256_add_epi32(_mm256_loadu_si256((const __m256i*)&index[0]), offsetsm2);
    __m256i secondLookup = _mm256_add_epi32(_mm256_loadu_si256((const __m256i*)&index[1]), offsetsm1);
    // Lookup in table
    __m256i values1 = _mm256_i32gather_epi32(combinations, firstLookup, 4);
    __m256i values2 = _mm256_i32gather_epi32(combinations, secondLookup, 4);
    // Subtract the terms
    __m256i finalValues = _mm256_sub_epi32(values1, values2);
    _mm256_storeu_si256((__m256i*)index, finalValues);

    // Extract out final sum
    int64_t result = 0;
    for (int x = 0; x < 6; x++)
    {
        result += index[x];
    }
    return result;  
}

Обратите внимание, что на самом деле у меня есть два похожих случая. В первом случае мне не нужен _pext_u64, и этот код примерно в 3 раза медленнее, чем мой существующий код. Во втором случае он мне нужен, и он на 25% быстрее.