Вложенная Параллель. Циклы foreach в том же списке?
Я должен параллелизировать метод, который делает исчерпывающее попарное сравнение на элементах в списке. Последовательная реализация проста:
foreach (var element1 in list)
foreach (var element2 in list)
foo(element1, element2);
В этом случае нечто не изменит состояние element1 или element2. Я знаю, что не безопасно просто сделать вложенную Параллель. Операторы ForEach:
Parallel.ForEach(list, delegate(A element1)
{
Parallel.ForEach(list, delegate(A element2)
{
foo(element1, element2);
});
});
Каков был бы идеальный способ реализовать это пользующееся параллельной библиотекой задач?
3 ответа
Нельзя ли просто иметь один параллельный и один обычный цикл? Так что либо
Parallel.ForEach(list, delegate(A element1)
{
foreach(A element2 in list)
foo(element1, element2)
});
либо
foreach(A element1 in list)
{
Parallel.ForEach(list, delegate(A element2)
{
foo(element1, element2);
});
}
Должно ускорить это также. В любом случае, на один цикл никогда не будет приходиться один поток, так что это, вероятно, будет так же быстро или чуть медленнее, чем вложенные параллельные циклы.
По крайней мере, если вы выполняете код на машине, где количество ядер как минимум вдвое превышает количество элементов в списке , я не уверен, что делать встроенные Parallel.ForEach s.
Другими словами, если вы нацеливаетесь на четырехъядерный процессор, а в списке одна тысяча элементов, просто распараллеливайте родительский цикл. Распараллеливание обоих циклов не сделало бы код быстрее, а скорее намного, намного медленнее , поскольку параллельные задачи требуют производительности.
alt text http://www.freeimagehosting.net/uploads/ca97f403f8.png
На каждой итерации Parallel.ForEach будет терять несколько миллисекунд, чтобы определить, какой поток должен выполнить следующая итерация. Допустим, у вас есть набор из 7 предметов. Если вы распараллеливаете родительский цикл, эти миллисекунды будут потеряны 7 раз. Если вы распараллелите оба цикла, они будут потеряны 7 × 7 = 49 раз. Чем больше набор, тем больше перегрев.
Два вложенных цикла по существу означают, что вы хотите foo декартово произведение списка на себя. Вы можете распараллелить всю операцию, сначала создав все пары во временном списке, а затем перебирая этот список с помощью Parallel.ForEach.
РЕДАКТИРОВАТЬ : вместо создания списка всех комбинаций вы можете использовать итератор для возврата двухэлементного кортежа с комбинацией. 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]);
}