Умножьте 64-битные целые числа, используя аппаратные свойства .NET Core - PullRequest
Новая
       30

Умножьте 64-битные целые числа, используя аппаратные свойства .NET Core

4 голосов
/ 07 мая 2019

Я пишу некоторый чувствительный к производительности код, в котором умножение беззнаковых 64-разрядных целых чисел (ulong) является узким местом.

.NET Core 3.0 получает доступ к аппаратным встроенным функциям с пространством имен System.Runtime.Intrinsics, что просто фантастично.

В настоящее время я использую переносимую реализацию, которая возвращает набор старших и младших бит 128-битного результата: 

[MethodImpl(MethodImplOptions.AggressiveInlining)]
internal static unsafe (ulong Hi, ulong Lo) Multiply64(ulong x, ulong y)
{
    ulong hi;
    ulong lo;

    lo = x * y;

    ulong x0 = (uint)x;
    ulong x1 = x >> 32;

    ulong y0 = (uint)y;
    ulong y1 = y >> 32;

    ulong p11 = x1 * y1;
    ulong p01 = x0 * y1;
    ulong p10 = x1 * y0;
    ulong p00 = x0 * y0;

    // 64-bit product + two 32-bit values
    ulong middle = p10 + (p00 >> 32) + (uint)p01;

    // 64-bit product + two 32-bit values
    hi = p11 + (middle >> 32) + (p01 >> 32);

    return (hi, lo);
}

Я хочу сделать это быстрее, используя встроенные функции. Я понимаю, как использовать BMI2, когда он доступен (это примерно на 50% быстрее, чем в переносной версии): 

ulong lo;
ulong hi = System.Runtime.Intrinsics.X86.Bmi2.X64.MultiplyNoFlags(x, y, &lo);
return (hi, lo);

Мне совершенно неясно, как использовать другие имеющиеся встроенные функции; похоже, все они полагаются на тип Vector<128>, и ни один из них не имеет отношения к типу ulong.

Как я могу реализовать умножение ulong с использованием SSE, AVX и т. Д.?

1 Ответ

2 голосов
/ 07 мая 2019

SIMD-векторы не являются простыми целыми числами.Максимальная ширина элемента составляет 64 бита.Они предназначены для параллельной обработки нескольких элементов.

x86 не имеет никаких инструкций для умножения 64x64 => 128-битных SIMD-элементов, даже с AVX512DQ. (Это обеспечивает SIMD 64x64 => 64-битное умножение, хотя, для 2, 4 или 8 элементов параллельно.)

AVX512IFMA (в Каскадном озере) имеет 52-битное высокая и низкая половина умножить-накопить (это не совпадение, это значение и ширина double; SIMD-команды целочисленного умножения используют то же оборудование умножения, что и FP).

Итакесли бы вы хотели умножить 64x64 => 128-битное SIMD, вам нужно было бы синтезировать его из 4x 32x32 => 64-битного vpmuludq и некоторых дополнений, включая перенос ширины добавления, который вам снова пришлось бы синтезировать изнесколько инструкций.

Вероятно, это будет медленнее, чем скалярное mul r64 для массива умножений даже при наличии AVX512.Для получения 512 битов результатов умножения требуется всего 4 скалярных mul инструкции, а современные процессоры x86 полностью конвейеризуют mul, поэтому они могут выдавать 1 пару результатов за такт.(Конечно, пропускная способность хранилища составляет только 1 за такт до IceLake / Sunny Cove, поэтому получение обеих половин 64-битного сохраненного результата является проблемой! Но перемещение данных в регистры XMM для 128-битных хранилищ стоит больше мопов, а такжеУзкое место на 64-битной частоте.)

Если вам нужно только 64x64 => 64-битное умножение, вы можете опустить умножение high32*high32.Я написал эту версию на C ++ Самый быстрый способ умножения массива int64_t? , и он чуть быстрее, чем скалярный на Haswell с AVX2, но значительно быстрее на Skylake.В любом случае, без AVX2 это ни к чему не стоило бы.

И, кстати, вам не нужен BMI2 для скалярного умножения 64x64 => 128-битных умножений .

Это базовый показатель для x86-64, с одним операндом mul (без знака) или imul (со знаком).Если C # выставляет внутреннюю для BMI2 mulx, она, безусловно, должна выставлять ее для простых беззнаковых mul и подписанных imul, которые по крайней мере какэффективен в большинстве случаев (и меньший размер кода).

...