为什么大数组的C#SIMD性能增益比小数组低？

Question

我一直在研究一个深度学习库，自己写作。在矩阵运算中，获得最佳性能对我来说是一个关键。我一直在研究编程语言及其对数字运算的性能。过了一段时间，我发现C#SIMD具有与C++SIMD非常相似的性能。所以，我决定用C#编写这个库。

首先，我测试了C#SIMD（我测试了很多东西，但是这里不写了）。我注意到，当使用较小的数组时，它的工作效果要好得多。当使用较大的数组时，效率不高。我觉得很可笑。通常情况下，当事情越大，效率就越快。

我的问题是“为什么在C#中使用较大的数组时，向量化的工作速度较慢？”

Program.Size = 10

| Method |      Mean |     Error |    StdDev |
|------- |----------:|----------:|----------:|
|     P1 |  28.02 ns | 0.5225 ns | 0.4888 ns |
|     P2 | 154.15 ns | 1.1220 ns | 0.9946 ns |
|     P3 | 100.88 ns | 0.8863 ns | 0.8291 ns |

Program.Size = 10000

| Method |     Mean |    Error |   StdDev |   Median |
|------- |---------:|---------:|---------:|---------:|
|     P1 | 142.0 ms | 3.065 ms | 8.989 ms | 139.5 ms |
|     P2 | 170.3 ms | 3.365 ms | 5.981 ms | 170.1 ms |
|     P3 | 103.3 ms | 2.400 ms | 2.245 ms | 102.8 ms |

public sealed class Matrix1
{
    public float[] Array;
    public int D1, D2;
    const int size = 110000000;
    private static ArrayPool<float> sizeAwarePool = ArrayPool<float>.Create(size, 100);

    public Matrix1(int d1, int d2)
    {
        D1 = d1;
        D2 = d2;
        if(D1*D2 > size)
        { throw new Exception("Size!"); }
        Array = sizeAwarePool.Rent(D1 * D2);
    }

    bool Deleted = false;
    public void Dispose()
    {
        sizeAwarePool.Return(Array);
        Deleted = true;
    }

    ~Matrix1()
    {
        if(!Deleted)
        {
            throw new Exception("Error!");
        }
    }

    public float this[int x, int y]
    {
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        get
        {
            return Array[x * D2 + y];
        }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        set
        {
            Array[x * D2 + y] = value;
        }
    }
}

程序类：

public class Program
{
    const int Size = 10000;

    [Benchmark]
    public void P1()
    {
        Matrix1 a = Program.a, b = Program.b, c = Program.c;
        int sz = Vector<float>.Count;
        for (int i = 0; i < Size * Size; i += sz)
        {
            var v1 = new Vector<float>(a.Array, i);
            var v2 = new Vector<float>(b.Array, i);
            var v3 = v1 + v2;
            v3.CopyTo(c.Array, i);
        }

    }

    [Benchmark]
    public void P2()
    {
        Matrix1 a = Program.a, b = Program.b, c = Program.c;
        for (int i = 0; i < Size; i++)
            for (int j = 0; j < Size; j++)
                c[i, j] = a[i, j] + b[i, j];
    }
    [Benchmark]
    public void P3()
    {
        Matrix1 a = Program.a;
        for (int i = 0; i < Size; i++)
            for (int j = 0; j < Size; j++)
                a[i, j] = i + j - j; 
                //could have written a.Array[i*size + j] = i + j
                //but it would have made no difference in terms of performance.
                //so leave it that way
    }


    public static Matrix1 a = new Matrix1(Size, Size);
    public static Matrix1 b = new Matrix1(Size, Size);
    public static Matrix1 c = new Matrix1(Size, Size);

    static void Main(string[] args)
    {
        for (int i = 0; i < Size; i++)
            for (int j = 0; j < Size; j++)
                a[i, j] = i;
        for (int i = 0; i < Size; i++)
            for (int j = 0; j < Size; j++)
                b[i, j] = j;
        for (int i = 0; i < Size; i++)  
            for (int j = 0; j < Size; j++)
                c[i, j] = 0;

        var summary = BenchmarkRunner.Run<Program>();
        a.Dispose();
        b.Dispose();
        c.Dispose();
    }
}     

我向您保证x[I,j]不会影响性能。与使用x.array[i*size+j]相同

Answer 1

这可能不是故事的全部：OP在评论中报告说，他们使用锯齿数组将P1从140毫秒加速到120毫秒。

所以也许有什么额外的东西阻碍了它在大箱子里。我会使用性能计数器来调查和检查LD_Blocks_partial.address_alias(4K aliasing->false dependency of loads on store）。和/或查看从C#分配器获得的内存地址，看看它们是否接近但不完全相同的对齐方式相对于4K边界。

我不认为在同一组中需要3个热缓存线会是一个问题；L1d在任何CPU上都是8路关联的，使用AVX（即使用256位加载/存储和ALUs）可以提供>4倍的加速。但是，如果所有数组相对于4K边界具有相同的对齐方式，那么当您访问相同的索引时，它们将在32KIB的L1d缓存中使用相同的别名。

检查dtlb_load_misses.miss_causes_a_walk和/或dtlb_load_misses.stlb_hit的性能计数器事件。有TLB预取，所以让它们交错可以允许TLB预取在一个或两个并行工作，而不是一次被击中所有3个页面行走。

SIMD并没有增加可用的内存带宽，只是可以以多快的速度将数据放入/放出缓存。它增加了您在大多数时间实际上可以使用的内存带宽。不过，用更少的指令做同样的工作可以帮助OoO执行人员看得更远，并更快地检测TLB未命中。

大数组的加速是有限的，因为标量已经接近内存带宽的瓶颈。您的c[i]=a[i]+b[i]访问模式是流sum访问模式，一个ALU操作的最大内存访问。(1D与2D索引是不相关的，您仍然只是读/写连续内存，并执行纯垂直SIMDfloat加法。在P1的情况下显式地执行。）

实际上，对于小矩阵情况，154.15/28.02=~5.5。

实际的缓存限制显然排除了这一点，例如，Intel的优化手册为Skylake的L1d缓存列出了大约81字节/时钟周期的典型持续加载+存储带宽。但是使用GP-integer Load+stores，Skylake可以支持32位操作数大小的每个循环的2个Load+1个store。因此，除了加载/存储uop吞吐量之外，还有某种微架构限制会在一定程度上减缓向量加载/存储。

你没说你有什么硬件，但我猜是英特尔Haswell或更晚。“只有”5.5倍的加速可能是由于每个调用只执行12或13个循环迭代的基准开销。