13

我需要并行化一种方法,该方法对列表中的元素进行详尽的成对比较。串行实现很简单:

foreach (var element1 in list)
    foreach (var element2 in list)
        foo(element1, element2);

在这种情况下, foo 不会改变 element1 或 element2 的状态。我知道简单地做嵌套的 Parallel.ForEach 语句是不安全的:

Parallel.ForEach(list, delegate(A element1)
{
    Parallel.ForEach(list, delegate(A element2)
    {
        foo(element1, element2);
    });
});

使用并行任务库实现这一点的理想方法是什么?

4

3 回答 3

16

至少如果您在内核数至少是 list 中项目数的两倍的机器上执行代码,我不确定执行 embedded Parallel.ForEachs 是否是个好主意。

换句话说,如果您以四核为目标,并且列表有一千个项目,则只需并行化父循环即可。并行化两个循环不会使代码更快,而是慢得多,因为并行任务有性能成本。

替代文字 http://www.freeimagehosting.net/uploads/ca97f403f8.png

在每次迭代中,将丢失几毫秒Parallel.ForEach以确定哪个线程必须执行下一次迭代。假设您有一组 7 个项目。如果并行化父循环,这些毫秒将丢失 7 次。如果将两个循环并行化,它们将丢失 7×7=49 次。设备越大,过热越大。

于 2010-07-19T13:52:51.003 回答
12

你不能只有一个并行和一个正常循环吗?所以要么

Parallel.ForEach(list, delegate(A element1)
{
  foreach(列表中的元素 2)
    富(元素1,元素2)
});

或者

foreach(列表中的元素 1)
{
  Parallel.ForEach(list, delegate(A element2)
  {
    富(元素1,元素2);
  });
}

也应该加快速度。无论如何,每个周期永远不会有一个线程,因此这可能与嵌套并行循环一样快或稍慢。

于 2010-07-19T13:52:22.933 回答
1

这两个嵌套循环本质上意味着您想将列表的笛卡尔积与自身相匹配。您可以通过首先在临时列表中创建所有对,然后使用 Parallel.ForEach 迭代该列表来并行化整个操作。

编辑:您可以使用迭代器返回包含该组合的 2 元素元组,而不是创建所有组合的列表。Parallel.ForEach 仍将并行处理元组。

以下示例打印出当前迭代步骤,以显示结果乱序返回,正如在并行处理期间所预期的那样:

 const int SIZE = 10;
    static void Main(string[] args)
    {
        List<int> list = new List<int>(SIZE);
        for(int i=0;i<SIZE;i++)
        {
            list.Add(i);
        }


        Parallel.ForEach(GetCombinations(list),(t,state,l)=>
            Console.WriteLine("{0},{1},{2}",l,t.Item1,t.Item2));

    }

    static IEnumerable<Tuple<int,int>> GetCombinations(List<int> list)
    {
        for(int i=0;i<list.Count;i++)
            for(int j=0;j<list.Count;j++)
                yield return Tuple.Create(list[i],list[j]);
    }
于 2010-07-19T14:07:41.620 回答