Возможен ли BigNum AVX/SSE?

Question

Регистры SSE/AVX можно рассматривать как большие числа с целыми числами или числами с плавающей запятой. То есть можно пренебречь тем, что полосы вообще существуют. Существует ли простой способ использовать эту точку зрения и использовать эти регистры в качестве BigNums по отдельности или в сочетании? Я спрашиваю, потому что из того, что я мало видел в библиотеках BigNum, они почти повсеместно хранят и выполняют арифметику с массивами, а не с регистрами SSE/AVX. Переносимость?

Пример:

Допустим, вы храните содержимое регистра SSE в качестве ключа в std::setВы можете сравнить это содержимое как BigNum.

Answer 1

Я думаю, что возможно реализовать 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-битных чисел одновременно. Но в XOP нет 64-битной беззнаковой инструкции шириной 256 бит. Вместо этого мы можем сделать следующее для 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

Answer 2

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

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

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

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

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

Answer 3

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

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

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