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

Question

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

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

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

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

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

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

Answer 1

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

Но прежде чем я продолжу, давайте немного ознакомимся с терминологией:

1. Полная арифметика слова
2. Частичная арифметика слова

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

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

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

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

Частичная арифметика

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

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

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

---

Проблемы с арифметикой полного слова:

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

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

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

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

• Надстройка с-Карри: adc, adcx, adox,
• Умножение двойного слова: один операнд mul а также mulx,

В свете этого SIMD трудно превзойти скалярные значения на x64 для bignum-add и bignum-multiply. Определенно не с SSE или AVX.

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

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

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

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

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

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

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

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

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

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

Большое Умножение, используя БПФ

Для действительно больших чисел умножение наиболее эффективно выполняется с использованием быстрых преобразований Фурье (БПФ).

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

---

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

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

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

---

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

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