并行化非常紧密的循环

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],等等)归结为我将十亿个元素减少到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和interwebs相当多,但这似乎是并行的边缘情况.

Answer 1

我没有任何经验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 个线程快一点。