Boucles Parallel.ForEach imbriquées dans la même liste?

Question

J'ai besoin de paralléliser une méthode qui effectue une comparaison par paire exhaustive sur les éléments d'une liste. L'implémentation en série est directe:

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

Dans ce cas, foo ne modifiera pas l'état de element1 ou element2. Je sais que ce n'est pas sûr simplement faire des déclarations de Parallel.ForEach imbriquées:

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

Quelle serait la meilleure façon de mettre en œuvre cette aide de la bibliothèque de tâches en parallèle?

Answer 1

Ne pourriez-vous pas avoir une boucle parallèle et une boucle normale? Donc, soit

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

ou

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

Si accélérer ainsi. De toute façon, il n'y aurait jamais de thread par cycle, donc cela serait probablement aussi rapide ou légèrement plus lent que les boucles parallèles imbriquées.

Answer 2

Au moins si vous exécutez le code sur une machine où le nombre de cœurs est au moins deux fois le nombre d'éléments dans la liste, je ne suis pas sûr que c'est une bonne idée de faire embarqué Parallel.ForEach s. En d'autres termes, si vous ciblez un quad-core et que la liste contient un millier d'éléments, il suffit de paralléliser la boucle parente. Paralléliser les deux boucles ne rendrait pas le code plus rapide, mais plutôt beaucoup, beaucoup plus lent, puisque les tâches parallèles ont un coût de performance.

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

A chaque itération, quelques millisecondes sera perdu par Parallel.ForEach pour déterminer quel thread doit exécuter l'itération suivante. Disons que vous avez un ensemble de 7 éléments. Si vous parallélisez la boucle parente, ces millisecondes seront perdues 7 fois. Si vous parallélisez les deux boucles, elles seront perdues 7 × 7 = 49 fois à la place. Plus l'ensemble est grand, plus la surchauffe est importante.

Answer 3

Les deux boucles imbriquées signifient essentiellement que vous voulez foo le produit cartessien de la liste avec lui-même. Vous pouvez paralléliser l'opération entière en créant d'abord toutes les paires dans une liste temporaire, puis en itérant sur cette liste avec Parallel.ForEach.

EDIT: Au lieu de créer une liste de toutes les combinaisons, vous pouvez utiliser un itérateur pour renvoyer un tuple à 2 éléments avec la combinaison. Parallel.ForEach continuera à paralléliser le traitement des tuples.

Le suivant imprime l'échantillon sur l'étape d'itération actuelle pour montrer que les résultats reviennent hors-ordre, comme on pouvait s'y attendre au cours du traitement parallèle:

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