В прошлом ответ на этот вопрос был твердым «нет». Но по состоянию на 2017 год ситуация меняется.
Но прежде чем я продолжу, время для некоторой базовой терминологии:
- Полная арифметика слов
- Арифметика с частичными словами
Арифметика полного слова:
Это стандартное представление, в котором число хранится в базе 2 32 или 2 64 с использованием массива 32-битных или 64-битных целых чисел. Многие библиотеки и приложения bignum (включая GMP) используют это представление.
В представлении полного слова каждое целое число имеет уникальное представление. Такие операции, как сравнения, просты. Но такие вещи, как сложение, сложнее из-за необходимости распространения переноса.
Именно это распространение переноса делает почти невозможным векторизацию большой арифметики.
Арифметика с неполным словом
Это менее используемое представление, в котором число использует основание меньше аппаратного размера слова. Например, в каждое 64-битное слово помещается только 60 бит. Или используйте базу 1,000,000,000 с 32-битным размером слова для десятичной арифметики.
Авторы GMP называют это «гвоздями», где «гвоздь» - неиспользованная часть слова.
В прошлом использование арифметики с частичными словами в основном ограничивалось приложениями, работающими с небинарными основами. Но в настоящее время это становится более важным, поскольку позволяет задерживать распространение переноса.
Проблемы с арифметикой полного слова:
Векторизация полнословной арифметики исторически была безнадежным делом:
- SSE / AVX2 не поддерживает распространение переноса.
- SSE / AVX2 не имеет 128-битного добавления / подпрограммы.
- SSE / AVX2 не поддерживает 64 x 64-битное целочисленное умножение. *
* AVX512-DQ добавляет нижнюю половину 64x64-битного умножения. Но инструкции в верхней половине по-прежнему нет.
Кроме того, в x86 / x64 есть множество специализированных скалярных инструкций для больших чисел:
- Надстройка с переносом:
adc, adcx, adox.
- Умножение на двойное слово: одинарные операнды
mul и mulx.
В свете этого, для SIMD трудно превзойти скаляр на x64 как с bignum-add, так и с bignum-multiply. Определенно не с SSE или AVX.
В AVX2 SIMD почти конкурирует со скалярным bignum-умножением, если вы переупорядочиваете данные, чтобы включить «вертикальную векторизацию» 4 различных (и независимых) умножений одинаковой длины на каждой из 4 дорожек SIMD.
AVX512 еще больше склоняется в пользу SIMD, снова предполагая вертикальную векторизацию.
Но по большей части «горизонтальная векторизация» бигнумов остается безнадежным делом, если у вас их много (одинакового размера) и вы не можете позволить себе стоимость их транспонирования, чтобы сделать их «вертикальными».
Векторизация арифметики с частичными словами
В арифметике с частичным словом дополнительные биты «гвоздя» позволяют задерживать распространение переноса.
Итак, пока вы не переполняете слово, добавление / добавление SIMD можно выполнить напрямую. Во многих реализациях представление частичного слова использует целые числа со знаком, чтобы слова были отрицательными.
Поскольку (обычно) нет необходимости выполнять перенос, добавление / добавление SIMD для частичных слов может быть выполнено одинаково эффективно как для вертикально, так и для горизонтально векторизованных больших значений.
Выполнение горизонтально-векторизованных бигнумов по-прежнему дешево, поскольку вы просто перекладываете гвозди на следующую полосу. Полный перенос, чтобы полностью очистить кусочки гвоздя и получить уникальное представление, обычно не требуется, если вам не нужно сравнивать два почти одинаковых числа.
Умножение сложнее с арифметикой с частичными словами, поскольку вам нужно иметь дело с кусочками гвоздя. Но, как и в случае с add / sub, тем не менее, это можно эффективно сделать на горизонтально-векторизованных больших изображениях.
AVX512-IFMA (идущий с процессорами Cannonlake) будет иметь инструкции, которые дают полные 104 бита умножения 52 x 52 бита (предположительно с использованием аппаратного обеспечения FPU). Это будет очень хорошо работать с представлениями частичных слов, которые используют 52 бита на слово.
Большое умножение с использованием БПФ
Для действительно больших больших чисел умножение наиболее эффективно выполняется с помощью быстрых преобразований Фурье (БПФ) < / а>.
БПФ полностью векторизуемы, поскольку они работают с независимыми double. Это возможно, потому что, по сути, представление, которое использует БПФ, является частичным представлением слов.
Подводя итог, можно сказать, что векторизация арифметики bignum возможна. Но нужно приносить жертвы.
Если вы ожидаете, что SSE / AVX сможет ускорить некоторый существующий код bignum без фундаментальных изменений в представлении и / или макете данных, это вряд ли произойдет.
Но, тем не менее, большую арифметику можно векторизовать.
Раскрытие:
Я автор y-cruncher, который выполняет множество арифметических операций с большими числами.
person
Mysticial
schedule
15.01.2012
