Geschachtelte Parallel.ForEach Loops auf der gleichen Liste?

Question

Ich muss eine Methode parallelisieren, die einen erschöpfenden paarweisen Vergleich von Elementen in einer Liste durchführt. Die serielle Implementierung ist straight-forward:

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

In diesem Fall foo wird den Zustand von element1 oder element2 nicht verändern. Ich weiß es einfach tun verschachtelte Parallel.ForEach Aussagen nicht sicher ist:

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

Was wäre der ideale Weg, dies die parallelen Aufgaben-Bibliothek zu implementieren?

Answer 1

Könnten Sie nicht nur eine parallele und eine normale Schleife haben? Also entweder

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

oder

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

Sollte es auch beschleunigen. Es würde sowieso nie einen Thread pro Zyklus geben, also wäre dieser wahrscheinlich genauso schnell oder etwas langsamer als verschachtelte parallele Schleifen.

Answer 2

Zumindest, wenn Sie auf einem Computer den Code ausführen, wo die Anzahl der Kerne mindestens zweimal die Anzahl der Elemente in der Liste ist, ich bin nicht sicher, ob es eine gute Idee ist Parallel.ForEach s zu tun eingebettet.

Mit anderen Worten, wenn Sie ein Quad-Core-Ziel und die Liste hat tausend Elemente, parallelisieren Sie einfach die Elternschleife. Die Parallelisierung beider Schleifen würde den Code nicht schneller machen, sondern viel, viel langsamer, da parallele Aufgaben Leistungskosten haben.

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

Bei jeder Iteration wird ein paar Millisekunden durch Parallel.ForEach verloren, welcher Thread zu bestimmen, muss die nächste Iteration auszuführen. Nehmen wir an, Sie haben ein Set von 7 Elementen. Wenn Sie die Elternschleife parallelisieren, gehen diese Millisekunden sieben Mal verloren. Wenn Sie beide Schleifen parallelisieren, gehen sie stattdessen 7 × 7 = 49 Mal verloren. Größer ist das Set, größer ist die Überhitzung.

Answer 3

Die beiden verschachtelten Schleifen im Wesentlichen bedeuten, dass Sie foo das Produkt Cartessian der Liste mit sich selbst wollen. Sie können die gesamte Operation parallelisieren, indem Sie zuerst alle Paare in einer temporären Liste erstellen und dann mit Parallel.ForEach über diese Liste iterieren.

BEARBEITEN: Anstatt eine Liste aller Kombinationen zu erstellen, können Sie einen Iterator verwenden, um ein 2-Element-Tupel mit der Kombination zurückzugeben. Parallel.ForEach wird weiterhin die Verarbeitung der Tupel parallelisieren.

Das folgende Beispiel druckt den aktuellen Iterationsschritt zu zeigen, dass die Ergebnisse kommen zurück out-of-order, wie bei der Parallelverarbeitung zu erwarten wäre:

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