c# - 并行化一个非常紧密的循环

Question

我已经为这个问题苦苦思索了几个小时，但我总是以线程争用结束我的循环并行化的任何性能改进。

我正在尝试计算 8 位灰度十亿像素图像的直方图。读过《CUDA by Example》这本书的人可能会知道这是从哪里来的(第 9 章)。

该方法非常非常简单(导致非常紧密的循环)。基本上就是

    private static void CalculateHistogram(uint[] histo, byte[] buffer) 
    {
        foreach (byte thisByte in buffer) 
        {
            // increment the histogram at the position
            // of the current array value
            histo[thisByte]++;
        }
    }

其中 buffer 是一个包含 1024^3 个元素的数组。

在较新的 Sandy Bridge-EX CPU 上构建 10 亿个元素的直方图需要在一个内核上运行 1 秒。

无论如何，我尝试通过在我的所有核心中分配循环来加快计算速度，并最终得到一个慢 50 倍的解决方案。

    private static void CalculateHistrogramParallel(byte[] buffer, ref int[] histo) 
    {
        // create a variable holding a reference to the histogram array
        int[] histocopy = histo;

        var parallelOptions = new ParallelOptions { MaxDegreeOfParallelism = Environment.ProcessorCount };

        // loop through the buffer array in parallel
        Parallel.ForEach(
            buffer,
            parallelOptions,
            thisByte => Interlocked.Increment(ref histocopy[thisByte]));
    }

很明显是因为原子增量对性能的影响。

无论我尝试了什么(例如范围分区器 [ http://msdn.microsoft.com/en-us/library/ff963547.aspx] 、并发集合 [ http://msdn.microsoft.com/en-us/library/dd997305(v=vs.110).aspx] 等等)，归根结底是我将 10 亿个元素减少到 256 个元素，而且我总是以在尝试访问我的直方图数组时处于竞争状态。

我最后一次尝试是使用范围分区器，例如

       var rangePartitioner = Partitioner.Create(0, buffer.Length);

        Parallel.ForEach(rangePartitioner, parallelOptions, range => 
        {
            var temp = new int[256];
            for (long i = range.Item1; i < range.Item2; i++) 
            {
                temp[buffer[i]]++;
            }
        });

计算子直方图。但最后，我仍然遇到必须合并所有这些子直方图的问题，然后再次发生线程争用。

我不相信没有办法通过并行化来加快速度，即使它是一个如此紧凑的循环。如果在 GPU 上可行，那么它在某种程度上也必须在 CPU 上可行。

除了放弃，还有什么可以尝试的？

我在 stackoverflow 和互联网上搜索了很多，但这似乎是并行性的边缘情况。

Answer 1

您应该使用 Parallel.ForEach 之一具有本地状态的循环。

并行循环的每个单独分区都有一个唯一的本地状态，这意味着它不需要同步。作为最终操作，您必须将每个本地状态聚合为最终值。此步骤需要同步，但每个分区只调用一次，而不是每次迭代调用一次。

代替

Parallel.ForEach(
    buffer,
    parallelOptions,
    thisByte => Interlocked.Increment(ref histocopy[thisByte]));

你可以使用

Parallel.ForEach(
    buffer,
    parallelOptions,
    () => new int[histocopy.Length], // initialize local histogram
    (thisByte, state, local) => local[thisByte]++, // increment local histogram
    local =>
    {
        lock(histocopy) // add local histogram to global
        {
            for (int idx = 0; idx < histocopy.Length; idx++)
            {
                histocopy[idx] += local[idx];
            }
        }
    }

---

从分区大小和并行选项的默认选项开始并从那里进行优化也可能是个好主意。