数组内的分段聚合

Question

我有一大堆原始价值类型.该阵列实际上是一维的,但在逻辑上代表一个二维场.当您从左向右阅读时,值需要变为(当前单元格的原始值)+(在左侧单元格中计算的结果).显然除了每行的第一个元素外,它只是原始值.

我已经有了一个实现它的实现,但是在整个数组上完全迭代,对于大型(1M +元素)数组来说非常慢.

给出以下示例数组,

0 0 1 0 0
2 0 0 0 3
0 4 1 1 0
0 1 0 4 1

变

0 0 1 1 1
2 2 2 2 5
0 4 5 6 6
0 1 1 5 6

等等,直到有问题的尺寸(1024x1024)

需要更新阵列(理想情况下),但必要时可以使用另一个阵列.内存占用空间不是问题,但性能至关重要,因为这些阵列具有数百万个元素,每秒必须处理数百次.

单个单元格计算似乎不可并行化,因为它们依赖于从左侧开始的值,因此GPU加速似乎是不可能的.我已经研究过PLINQ,但索引的必要条件使得它很难实现.

是否有另一种方法来构建数据以使其更快地处理？

如果使用创新的技术可以实现高效的GPU处理,那么这将是非常可取的,因为这是当前必须从视频卡中拉出并推回到视频卡的纹理数据.

Answer 1

正确的编码和对 .NET 如何了解东西的一些了解也会有所帮助:-)

适用于这种情况的一些经验法则：

1. 如果您可以提示 JIT 索引永远不会超出数组的范围，它将删除额外的分支。
2. 如果它真的很慢（例如 >1 秒），您应该仅在多个线程中对其进行矢量化。否则，任务切换、缓存刷新等可能只会消耗增加的速度，结果会更糟。
3. 如果可能的话，使内存访问可预测，甚至是顺序的。如果您需要另一个数组，那就这样吧——如果不需要，那就更喜欢它。
4. 如果您想要速度，请尽可能少地使用 IL 指令。一般来说，这似乎有效。
5. 测试多次迭代。一次迭代可能还不够好。

使用这些规则，您可以制作一个小测试用例，如下所示。请注意，我已将赌注提高到 4Kx4K，因为 1K 太快了，您无法测量它:-)

public static void Main(string[] args)
{
    int width = 4096;
    int height = 4096;

    int[] ar = new int[width * height];
    Random rnd = new Random(213);
    for (int i = 0; i < ar.Length; ++i)
    {
        ar[i] = rnd.Next(0, 120);
    }

    // (5)...
    for (int j = 0; j < 10; ++j)
    {
        Stopwatch sw = Stopwatch.StartNew();

        int sum = 0;
        for (int i = 0; i < ar.Length; ++i)  // (3) sequential access
        {
            if ((i % width) == 0)
            {
                sum = 0;
            }

            // (1) --> the JIT will notice this won't go out of bounds because [0<=i<ar.Length]
            // (5) --> '+=' is an expression generating a 'dup'; this creates less IL.
            ar[i] = (sum += ar[i]); 
        }

        Console.WriteLine("This took {0:0.0000}s", sw.Elapsed.TotalSeconds);
    }
    Console.ReadLine();
}

其中一次迭代将花费大约 0.0174 秒，因为这大约是您描述的最坏情况的 16 倍，所以我认为您的性能问题已经解决。

如果你真的想并行化它以使其更快，我认为这是可能的，即使你会失去 JIT 中的一些优化（具体来说：（1））。但是，如果您像大多数人一样拥有多核系统，那么好处可能会超过以下这些：

for (int j = 0; j < 10; ++j)
{
    Stopwatch sw = Stopwatch.StartNew();
    Parallel.For(0, height, (a) =>
    {
        int sum = 0;
        for (var i = width * a + 1; i < width * (a + 1); i++)
        {
            ar[i] = (sum += ar[i]);
        }
    });
    Console.WriteLine("This took {0:0.0000}s", sw.Elapsed.TotalSeconds);
}

如果您确实非常需要性能，可以将其编译为 C++ 并使用 P/Invoke。即使您不使用 GPU，我认为 SSE/AVX 指令可能已经为您带来了 .NET/C# 无法获得的显着性能提升。我还想指出，英特尔 C++ 编译器可以自动矢量化您的代码 - 甚至是 Xeon PHI 的代码。无需付出太多努力，这可能会给您带来性能上的大幅提升。