В прошлом ответ на этот вопрос был твердым, «нет». Но с 2017 года ситуация меняется.
Но, прежде чем я продолжу, давайте немного ознакомимся с терминологией:
- Арифметика полного слова
- Частичная арифметика слов
Арифметика полного слова:
Это стандартное представление, где число хранится в базе 2 32 или 2 64 с использованием массива 32-битных или 64-битных целых чисел.
Многие библиотеки и приложения bignum (включая GMP) используют это представление.
В представлении с полным словом каждое целое число имеет уникальное представление. Операции, такие как сравнения, просты. Но такие вещи, как сложение, сложнее из-за необходимости распространения переноса.
Именно это распространение переноса делает арифметику Бигнума практически невозможной векторизацией.
Частичная арифметика
Это менее используемое представление, где число использует основание меньше, чем аппаратный размер слова. Например, поместив только 60 бит в каждое 64-битное слово. Или используйте base 1,000,000,000 с 32-битным размером слова для десятичной арифметики.
Авторы GMP называют это «гвоздями», где «гвоздь» - это неиспользованная часть слова.
В прошлом использование арифметики частичных слов в основном ограничивалось приложениями, работающими в недвоичных основах. Но в настоящее время это становится все более важным, поскольку позволяет задерживать распространение переноса.
Проблемы с арифметикой полного слова:
Векторизация полных слов арифметики исторически была безнадежной причиной:
- SSE / AVX2 не поддерживает перенос переноса.
- SSE / AVX2 не имеет 128-битного добавления / саб.
- SSE / AVX2 не имеет 64 x 64-разрядного целочисленного умножения. *
* AVX512-DQ добавляет нижнюю половину 64x64-битного умножения. Но верхней инструкции все еще нет.
Кроме того, x86 / x64 имеет множество специализированных скалярных инструкций для bignums:
- Add-with-Carry:
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 бита на слово.
Большое умножение с использованием БПФ
Для действительно больших чисел умножение наиболееэффективно выполняется с использованием быстрых преобразований Фурье (БПФ) .
БПФ полностью векторизуемы, так как они работают на независимых double с.Это возможно, потому что принципиально, представление, которое используют БПФ , представляет собой частичное представление слова.
Подводя итог, возможна векторизация арифметики Бигнума.Но жертвы должны быть принесены.
Если вы ожидаете, что SSE / AVX сможет ускорить некоторый существующий код bignum без фундаментальных изменений в представлении и / или расположении данных, это вряд ли произойдет.
Но тем не менее, арифметику bignum можно векторизовать.
Раскрытие информации:
Я автор y-cruncher , который делает много большого числаarihmetic.