Действительно ли эффективно использовать алгоритм Карацубы в 64-битном х 64-битном умножении?
Я работаю на AVX2 и мне нужно рассчитать 64-битное x64-битное -> 128-битное умножение с расширением и получить 64-битную старшую часть самым быстрым способом. Поскольку у AVX2 нет такой инструкции, разумно ли мне использовать алгоритм Карацубы для повышения эффективности и увеличения скорости?
Решение
Нет. На современных архитектурах пересечение, при котором Карацуба превосходит умножение учебников, обычно составляет от 8 до 24 машинных слов (например, от 512 до 1536 бит на x86_64). Для фиксированных размеров порог находится на меньшем конце этого диапазона, и новые инструкции ADCX / ADOX, вероятно, привносят его в скалярный код несколько дальше, но 64×64 все еще слишком мала, чтобы извлечь выгоду из Карацубы.
Другие решения
Маловероятно, что AVX2 победит mulx инструкция который делает 64bx64b до 128b в одной инструкции. Есть одно исключение, о котором я знаю большие умножения с использованием БПФ с плавающей точкой.
Тем не менее, если вам не нужно точно 64bx64b до 128b, вы можете рассмотреть
53bx53b до 106b с использованием двойная двойная арифметика.
Умножить четыре 53-битных числа a а также b Чтобы получить четыре 106-битных номера, нужны только две инструкции:
__m256 p = _mm256_mul_pd(a,b);
__m256 e = _mm256_fmsub_pd(a,b,p);
Это дает четыре 106-разрядных числа в двух инструкциях по сравнению с одним 128-разрядным числом в одной инструкции, используя mulx,
Трудно сказать, не пытаясь, но я мог бы быстрее использовать инструкцию AMD64 MUL, которая поддерживает 64×64 = 128 с той же пропускной способностью, что и большинство инструкций AVX2 (но не векторизовано). Недостатком является то, что вам нужно загружать в обычные регистры, если операнды были в регистрах YMM. Это дало бы что-то вроде LOAD + MUL + STORE для одного 64х64 = 128.
Если вы можете векторизовать Карацубу в AVX2, попробуйте оба AVX2 и MUL и посмотрим, что быстрее. Если вы не можете векторизовать, один MUL вероятно будет быстрее. Если вы можете снять нагрузку и сохранить в обычные регистры, один MUL будет определенно быстрее.
И то и другое MUL и инструкции AVX2 могут иметь операнд в памяти с одинаковой пропускной способностью, и это может помочь удалить одну загрузку для MUL,
detector