Nested Parallel.ForEach Loops en la misma lista?

Question

Necesito paralelizar un método que hace una comparación por pares exhaustiva de los elementos en una lista. La implementación en serie es sencilla:

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

En este caso, foo no modificará el estado de element1 o element2. Yo sé que no es seguro es simplemente hacer declaraciones Parallel.ForEach anidados:

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

¿Cuál puede ser la forma ideal para poner en práctica esta usando la biblioteca de tareas en paralelo?

Answer 1

no Podrías tener un puerto paralelo y un bucle normal? Así que, o

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

o

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

En caso de acelerarlo también. De todos modos, nunca habría un hilo por ciclo, por lo que probablemente sea tan rápido o ligeramente más lento que los bucles paralelos anidados.

Answer 2

Al menos si se está ejecutando el código en una máquina en el número de núcleos es al menos dos veces el número de elementos de la lista, no estoy seguro de que es una buena idea hacer incrustado Parallel.ForEach s.

En otras palabras, si la orientación es de cuatro núcleos, y la lista tiene un millar de artículos, simplemente paralelizar el bucle padres. La paralelización de ambos bucles no haría el código más rápido, sino más bien mucho, mucho más lento, ya que las tareas paralelas tienen un costo de rendimiento.

alt text http://www.freeimagehosting.net/uploads/ca97f403f8.png

En cada iteración, unos pocos milisegundos se perderán por Parallel.ForEach para determinar qué subproceso debe ejecutar la siguiente iteración. Digamos que tienes un conjunto de 7 elementos. Si paraleliza el ciclo padre, esos milisegundos se perderán 7 veces. Si paralelas ambos bucles, se perderán 7 × 7 = 49 veces en su lugar. Más grande es el conjunto, más grande es el sobrecalentamiento.

Answer 3

Los dos bucles anidados significan esencialmente que desea foo el producto cartessian de la lista consigo mismo. Puede poner en paralelo toda la operación creando primero todos los pares en una lista temporal, luego iterando sobre esa lista con Parallel.ForEach.

EDIT: En lugar de crear una lista de todas las combinaciones, puede usar un iterador para devolver una tupla de 2 elementos con la combinación. Parallel.ForEach seguirá paralelizando el procesamiento de las tuplas.

La siguiente ejemplos de impresión de la etapa de iteración actual para mostrar que los resultados vuelven fuera de orden, como era de esperar durante el procesamiento en paralelo:

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]); 
    }