Могут ли длинные целые процедуры использовать SSE?

Я все еще работаю над подпрограммами для произвольных длинных целых чисел в С++. До сих пор я реализовал сложение/вычитание и умножение для 64-битных процессоров Intel.

Все работает отлично, но я задавался вопросом, могу ли я немного ускорить его с помощью SSE. Я просмотрел списки инструкций SSE и процессоров, но я не смог найти ничего, что, я думаю, могу использовать, и вот почему:

  • SSE имеет несколько целых инструкций, но большинство команд обрабатывают с плавающей запятой. Не похоже, что он был предназначен для использования с целыми числами (например, существует ли целочисленное сравнение для меньшего?)

  • Идея SSE - это SIMD (та же инструкция, несколько данных), поэтому она предоставляет инструкции для 2 или 4 независимых операций. Я, с другой стороны, хотел бы иметь что-то вроде 128-битного целочисленного add (128-битный ввод и вывод). Это, похоже, не существует. (Тем не менее? Возможно, в AVX2?)

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

Мой вопрос: моя оценка правильная или есть что-то, что я упустил? Могут ли длинные целые процедуры использовать SSE? В частности, могут ли они помочь мне написать более быструю процедуру добавления, sub или mul?

Ответы

Ответ 1

В прошлом ответ на этот вопрос был прочным, "нет". Но с 2017 года ситуация меняется.

Но прежде чем продолжить, время для некоторой фоновой терминологии:

  • Арифметика полного слова
  • Арифметика с частичным словом


Арифметика Full-Word:

Это стандартное представление, в котором число хранится в базе 2 32 или 2 64 используя массив из 32-разрядных или 64-разрядных целых чисел. В этом представлении используются многие библиотеки и приложения bignum (включая GMP).

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

Именно это перенос переноса делает арифметику бинума почти невозможной для векторизации.


Арифметика с частичным словом

Это менее используемое представление, в котором число использует базу меньше, чем размер аппаратного слова. Например, поместить только 60 бит в каждое 64-битное слово. Или используя base 1,000,000,000 с 32-разрядным размером слова для десятичной арифметики.

Авторы GMP называют это "гвозди", где "гвоздь" является неиспользуемой частью слова.

В прошлом использование арифметики с частичным словом в основном ограничивалось приложениями, работающими в недвоичных базах. Но в настоящее время он становится все более важным в том смысле, что позволяет переносить перенос переноса.

Проблемы с арифметикой Full-Word:

Векторизация полноразмерной арифметики исторически была потерянной причиной:

  • SSE/AVX2 не поддерживает перенос носителей.
  • SSE/AVX2 не имеет 128-битного add/sub.
  • SSE/AVX2 не имеет 64 x 64-битного целочисленного значения. *

* AVX512-DQ добавляет более короткое 64x64-битное умножение. Но до сих пор нет инструкции по началу.

Кроме того, x86/x64 имеет множество специализированных скалярных инструкций для bignums:

  • Add-with-Carry: adc, adcx, adox.
  • Double-word Multiply: Single-operand mul и mulx.

В свете этого, как бигнам-добавление, так и умножение бинума трудно для SIMD бить скаляр на x64. Определенно не с SSE или AVX.

С AVX2 SIMD почти конкурирует со скалярным умножением бинума, если вы переставляете данные, чтобы включить "вертикальную вектозацию" из 4 разных (и независимых) умножений одинаковой длины на каждой из 4 SIMD-полос.

AVX512 подскажет все больше в пользу SIMD, снова предполагая вертикальную вектологию.

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


Векторизация арифметики с частичным словом

С арифметикой с частичным словом дополнительные биты "гвоздя" позволяют задерживать перенос переноса.

До тех пор, пока вы не переполняете слово, SIMD add/sub можно сделать напрямую. Во многих реализациях представление с частичным словом использует целые числа со знаком, чтобы слова могли быть отрицательными.

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

Перенос по горизонтально-векторизованным бонусам по-прежнему дешев, поскольку вы просто перемещаете гвозди на следующую полосу. Полное выполнение, чтобы полностью очистить биты гвоздя и получить уникальное представление, обычно не требуется, если вам не нужно сравнивать два числа, которые почти одинаковы.

Умножение сложнее с арифметикой частичного слова, так как вам нужно иметь дело с битами гвоздя. Но, как и в случае с add/sub, все же возможно сделать это эффективно на горизонтально-векторизованных бонусах.

AVX512-IFMA (с процессорами Cannonlake) будет иметь инструкции, которые дают полные 104 бит 52 x 52-битного умножения (предположительно, используя оборудование FPU). Это очень хорошо сыграет с представлениями частичного слова, которые используют 52 бит на каждое слово.


Большое умножение с использованием БПФ

Для действительно больших бонусов умножение наиболее эффективно выполняется с помощью Fast-Fourier Transforms (FFTs).

БПФ полностью векционируемы, так как они работают на независимых double s. Это возможно, потому что в основном, представление, которое использует БПФ, частичное представление слов.

Подводя итог, возможна векторизация арифметики бигума. Но жертвы должны быть сделаны.

Если вы ожидаете, что SSE/AVX сможет ускорить работу какого-либо существующего кода bignum без существенных изменений в представлении и/или макете данных, это вряд ли произойдет.

Но тем не менее, арифметику бигума можно векторизовать.

Раскрытие информации:

Я автор y-cruncher, который делает много арифметики большого числа.