Практичный BigNum AVX / SSE возможен?

Я думаю, что возможно эффективно реализовать BigNum с SIMD, но не так, как вы предлагаете.

Вместо реализации одного BigNum с использованием регистра SIMD (или с массивом регистров SIMD) вы должны обрабатывать несколько BigNum одновременно.

Рассмотрим 128-битное сложение. Пусть 128-битные целые числа определяются парой высоких и младших 64-битных значений, и предположим, что мы хотим добавить 128-битное целое число (y_low, y_high) к 128-битному целому числу (x_low, x_high). Со скалярными 64-битными регистрами для этого требуется всего две инструкции

add rax, rdi // x_low  += y_low;
adc rdx, rsi // x_high += y_high + (x_low < y_low);

С SSE / AVX проблема, как объясняют другие, заключается в том, что нет флагов переноса SIMD. Флаг переноса должен быть рассчитан и затем добавлен. Для этого требуется 64-битное сравнение без знака. Единственный реальный вариант для этого с SSE - из инструкции AMD XOP vpcomgtuq

vpaddq      xmm2, xmm0, xmm2 // x_low  += y_low;
vpcomgtuq   xmm0, xmm0, xmm2 // x_low  <  y_low
vpaddq      xmm1, xmm1, xmm3 // x_high += y_high
vpsubq      xmm0, xmm1, xmm0 // x_high += xmm0

При этом используются четыре инструкции для сложения двух пар 128-битных чисел. Для скалярных 64-битных регистров для этого также требуются четыре инструкции (две add и две adc).

С AVX2 мы можем добавить сразу четыре пары 128-битных чисел. Но нет 256-битной 64-битной беззнаковой инструкции от XOP. Вместо этого мы можем сделать следующее для a<b:

__m256i sign64 = _mm256_set1_epi64x(0x8000000000000000L);
__m256i aflip = _mm256_xor_si256(a, sign64);
__m256i bflip = _mm256_xor_si256(b, sign64);
__m256i cmp = _mm256_cmpgt_epi64(aflip,bflip);

Регистр sign64 может быть вычислен заранее, поэтому действительно необходимы только три инструкции. Следовательно, сложение четырех пар 128-битных чисел с помощью AVX2 может быть выполнено с помощью шести инструкций.

vpaddq
vpaddq
vpxor
vpxor
vpcmpgtq 
vpsubq

тогда как скалярным регистрам требуется восемь инструкций.

AVX512 имеет единственную инструкцию для выполнения 64-битного сравнения без знака vpcmpuq. Следовательно, должно быть возможно сложить восемь пар 128-битных чисел, используя только четыре инструкции.

vpaddq
vpaddq
vpcmpuq
vpsubq

Со скалярным регистром потребовалось бы 16 инструкций для сложения восьми пар 128-битных чисел.

Вот таблица со сводкой количества инструкций SIMD (называемых nSIMD) и количества скалярных инструкций (называемых nscalar), необходимых для добавления ряда пар (называемых npairs) 128-битных чисел.

              nSIMD      nscalar     npairs
SSE2 + XOP        4           4           2
AVX2              6           8           4
AVX2 + XOP2       4           8           4
AVX-512           4          16           8

Обратите внимание, что XOP2 еще не существует, и я только предполагаю, что он может существовать в какой-то момент.

Также обратите внимание, что для того, чтобы сделать это эффективно, массивы BigNum должны храниться в форме массива структуры массива (AoSoA). Например, при использовании l для обозначения младших 64-битных и h для обозначения старших 64-битных массив 128-битных целых чисел хранится как массив структур, подобных этой

lhlhlhlhlhlhlhlh

вместо этого следует хранить с использованием AoSoA, подобного этому

SSE2:   llhhllhhllhhllhh
AVX2:   llllhhhhllllhhhh
AVX512: llllllllhhhhhhhh

Перемещено из комментария выше

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

Для простой задачи добавления тривиально использовать флаг переноса регистра x86 EFLAGS / RFLAGS для распространения переносов сложения с самого нижнего «участка» вверх (чтобы использовать терминология GMP) и перебрать произвольное количество конечностей, уложенных в массив.

Напротив, дорожки регистров SSE / AVX не имеют флагов переноса, что означает, что переполнение должно обнаруживаться другим способом, включая сравнения для обнаружения циклического перехода, что требует больших вычислительных затрат. Более того, если переполнение обнаружено в одной конечности, оно должно быть распространено некрасивым перетасованием «вверх», а затем добавлено, и это добавление может вызвать еще одно переполнение и перенос, до N-1 раз для N-конечности. бигнум. Затем, как только сумма дает bignum за пределами 128 бит / 256 бит (или за пределами 128 бит x # регистров), вам все равно придется переместить ее в массив.

Следовательно, потребуется много кода особого случая, и он не будет быстрее (на самом деле, намного медленнее), просто для добавления. Представьте, что потребуется для умножения? или вздох, разделение?

Это возможно, но непрактично.

Как я сказал в другом ответе, в AVX / SSE нет флага переноса, поэтому невозможно эффективно выполнять сложение и вычитание. А чтобы выполнить умножение, вам понадобится много перетасовки, чтобы получить результат умножения с расширением в желаемой позиции.

Если вам разрешено работать с новой микроархитектурой Haswell / Broadwell, решением будет MULX в BMI2 и ADOX, ADCX в ADX. Вы можете прочитать о них здесь.