并行化非常紧密的循环-Java 学习之路

我在这个问题上已经敲了好几个小时，而且我总是因为线程争用而吃掉了并行化循环的性能改进 .

我正在尝试计算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相当多，但这似乎是并行性的边缘情况 .

3 回答

我对 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快一点 .

回复于 2024-04-27T10:12:10+08:00

3
我不知道如果这会更快，但有点观察;

如果你对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/

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

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

2）尝试使用stackalloc关键字并确保通过堆栈完成任何内存分配 . 相信我 - 除非直接来自堆栈，否则任何内存分配都会很慢 . 我们正在谈论5倍的差异 .

3）您可以使用C＃MONO SIMD尝试SUM不同的数组（这是C版本，但这个概念适用于C＃C++ Adding 2 arrays together quickly）
回复于 2024-04-27T10:12:10+08:00

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

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

回复于 2024-04-27T10:12:10+08:00

并行化非常紧密的循环

3 回答

相关问题