c# - 使用 .NET Core 的硬件内在函数将 64 位整数相乘

Question

我正在编写一些对性能敏感的代码，其中无符号 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 等吗？

Answer 1

SIMD 向量不是单宽整数。最大元素宽度为 64 位。它们用于并行处理多个元素。

x86 没有任何关于 64x64 => 128 位 SIMD 元素乘法的指令，即使是 AVX512DQ 也没有。(尽管它确实提供 SIMD 64x64 => 64 位乘法，对于 2 、4 或 8 个并联的元素。)

AVX512IFMA (在 Cascade Lake 中)有 52 位 high and low-half multiply-accumulate (double 的有效位宽度不是巧合；SIMD 整数乘法指​​令使用与 FP 相同的乘法硬件)。

---

因此，如果您想要 64x64 => 128 位 SIMD 乘法，则必须从 4x 32x32 => 64 位 vpmuludq 和一些加法(包括加宽进位)中合成它你必须再次从多条指令中合成。

对于乘法数组，这可能比标量 mul r64 慢，即使 AVX512 可用也是如此。只需要 4 个标量 mul 指令即可产生 512 位的乘法结果，而现代 x86 CPU 完全流水线化 mul，因此它们每个时钟可以产生一对结果。 (当然，在 IceLake/Sunny Cove 之前，每个时钟的存储吞吐量仅为 1，因此存储 64 位结果的两半是一个问题!但是将数据移动到 128 位存储的 XMM 寄存器会花费更多的 uops，并且还会遇到64 位/时钟瓶颈。)

如果您只需要 64x64 => 64 位乘法，您可以放弃 high32*high32 乘法。我在 Fastest way to multiply an array of int64_t? 中写了一个 C++ 版本它在使用 AVX2 的 Haswell 上仅比标量快，但在 Skylake 上快得多。无论哪种方式，如果没有 AVX2，它都不值得。

---

顺便说一句，您不需要 BMI2 来执行标量 64x64 => 128 位乘法。

这是 x86-64 的基线，使用单操作数 mul(无符号)或 imul(有符号)。如果 C# 公开了 BMI2 mulx 的内在函数，它肯定必须为普通未签名的 mul 公开一个并签署了imul这至少在大多数情况下是有效的(并且代码量更小)。