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

本文关键字：循环 非常 一个 并行化 | 更新日期: 2023-09-27 18:13:31

我已经为这个问题绞尽脑汁好几个小时了，结果总是线程争用耗尽了并行化循环所带来的性能改进。

我正试图计算8位灰度十亿像素图像的直方图。读过"CUDA示例"这本书的人可能会知道这是从哪里来的(第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和互联网相当多，但这似乎是并行的一个边缘情况

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

您应该使用具有本地状态的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];
            }
        }
    }

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

我没有Parallel的任何经验，但是我用手动线程进行了一个测试，它工作得很好。

private class Worker
{
    public Thread Thread;
    public int[] Accumulator = new int[256];
    public int Start, End;
    public byte[] Data;
    public Worker( int start, int end, byte[] buf )
    {
        this.Start = start;
        this.End = end;
        this.Data = buf;
        this.Thread = new Thread( Func );
        this.Thread.Start();
    }
    public void Func()
    {
        for( int i = Start; i < End; i++ )
            this.Accumulator[this.Data[i]]++;
    }
}
int NumThreads = 8;
int len = buf.Length / NumThreads;
var workers = new Worker[NumThreads];
for( int i = 0; i < NumThreads; i++ )
    workers[i] = new Worker( i * len, i * len + len, buf );
foreach( var w in workers )
    w.Thread.Join();
int[] accumulator = new int[256];
for( int i = 0; i < workers.Length; i++ )
    for( int j = 0; j < accumulator.Length; j++ )
        accumulator[j] += workers[i].Accumulator[j];

我的Q720手机i7的结果:

Single threaded time = 5.50s
4 threads = 1.90s
8 threads = 1.24s

看起来对我有用。有趣的是，尽管超线程内核共享一个缓存，但8个线程实际上比4个线程要快一些。

我不知道这是否会更快，但稍加观察;

如果对buffer[]中的所有元素进行排序会怎么样?这意味着不同的核心之间不再有交叉。如果性能合适，那么可以增加核心数，它应该是线性上升的。请注意，您确实需要更好地处理firstRange/secondRange拆分，因为您不希望两个元素在不同的范围内具有相同的值。

private static void CalculateHistogram(uint[] histo, byte[] buffer)
{
    Array.Sort(buffer); // so the indexes into histo play well with cache.   
    // todo; rewrite to handle edge-cases.
    var firstRange = new[] {0, buffer.Length/2}; // [inclusive, exclusive]
    var secondRange = new[] {buffer.Length/2, buffer.Length};
    // create two tasks for now ;o
    var tasks = new Task[2];
    var taskIdentifier = 0;
    foreach (var range in new[] {firstRange, secondRange})
    {
        var rangeFix = range; // lambda capture ;s
        tasks[taskIdentifier++] = Task.Factory.StartNew(() =>
        {
            for (var i = rangeFix[0]; i < rangeFix[1]; i++)
                ++histo[i];
        });
    }
    Task.WaitAll(tasks);
}

快速搜索显示你可以使用c# &GPU对数字进行进一步排序，这将导致大约3倍的性能提高，值得一试:http://adnanboz.wordpress.com/2011/07/27/faster-sorting-in-c-by-utilizing-gpu-with-nvidia-cuda/

还有一些技巧可以带来非常可观的性能提升:

1)记住虚假缓存共享的概念- http://msdn.microsoft.com/en-us/magazine/cc872851.aspx

2)尝试使用stackalloc关键字，并确保任何内存分配都是通过堆栈完成的。相信我——任何内存分配都非常慢，除非直接从堆栈中分配。我们讨论的是5倍的差异。

3)您可以使用c# MONO SIMD来尝试求和不同的数组(这是C版本，但这个概念适用于c# c++快速添加2个数组)

相关文章：