parallele Schleife über Paare

Question

Was ist der beste Weg in C++ 11, eine paarweise Berechnung in mehreren Threads durchzuführen? Was ich meine ist, ich habe eine vector von Elementen, und ich möchte eine Funktion für jedes Paar unterschiedlicher Elemente berechnen. Der Nachteil ist, dass ich nicht das gleiche Element in mehreren Threads gleichzeitig verwenden kann, z. Die Elemente haben Zustände, die sich während der Berechnung entwickeln, und die Berechnung beruht darauf.

Answer 1

Ein einfacher Weg wäre, die Paare nach Offsets zu gruppieren.

Wenn v ein Vektor ist, dann bilden die Elemente N auseinander (mod v.size()) zwei Paare von Paaren. Jede dieser Sammlungen von Paaren enthält keine Überlappungen in sich.

Untersuchen Sie einen Vektor mit 10 Elementen 0 1 2 3 4 5 6 7 8 9. Die Paare 1 voneinander entfernt sind:

0 1, 1 2, 2 3, 3 4, 4 5, 5 6, 6 7, 7 8, 8 9, 9 0 

, wenn Sie diese durch „Parität“ in zwei Sammlungen teilen wir bekommen:

0 1, 2 3, 4 5, 6 7, 8 9 
1 2, 3 4, 5 6, 7 8, 9 0 

Sie arbeiten können, parallel dazu, auf jeder der oben genannten Sammlungen. Wenn die Sammlung abgeschlossen ist, synchronisieren Sie sie und arbeiten Sie dann an der nächsten Sammlung.

Ähnliche Tricks funktionieren für 2 auseinander.

0 2, 1 3, 4 6, 5 7 
2 4, 3 5, 6 8, 7 9 

mit Resten:

8 0, 9 1 

Für Offset jeder von 1 bis n/2 gibt es gleich 2 "Sammlungen" und Speisereste.

ist hier von 4 Offset:

0 4, 1 5, 2 6, 3 7 
4 8, 5 9, 6 0, 7 1 

und Reste

8 2, 9 3 

(Ich denke, ganz naiv die Größe der Reste ist Vektorgröße mod Offset)

diese Sammlungen Berechnung (und die Reste) ist nicht schwer; Anordnen, um Threads anzuordnen und die richtigen Aufgaben effizient in den richtigen Threads zu bekommen, ist schwieriger.

Es gibt N wählen Sie 2 oder (n^2 + n)/2, Paare. Diese Aufteilung gibt Ihnen O (1.5n) Sammlungen und Reste, jede von der Größe höchstens n/2, und volle Parallelität innerhalb jeder Sammlung.

---

Wenn SieFormal eine Situation, wo einige Elemente wesentlich teurer ist als andere, und somit für jede Sammlung bis Ende wartenden Threads im Leerlauf zu viel, könnte man feinkörniges Synchronisation hinzuzufügen.

Pflegen Sie einen Vektor von atomaren Bools. Verwenden Sie das, um anzuzeigen, dass Sie gerade ein Element bearbeiten. Immer "sperren" (auf "true" setzen und prüfen, ob es falsch war, bevor Sie es auf "true" setzen), der niedrigere Index vor dem oberen.

Wenn Sie es schaffen, beide zu sperren, verarbeiten Sie weg. Dann lösche sie beide.

Wenn Sie Fehler haben, erinnern Sie sich an die Aufgabe für später und arbeiten Sie an anderen Aufgaben. Wenn Sie zu viele Aufgaben in der Warteschlange haben, warten Sie auf eine Bedingungsvariable und versuchen Sie, das Atom-Bool, das Sie sperren möchten, im Spin-Lambda zu überprüfen und festzulegen.

Wechseln Sie die Zustandsvariable in regelmäßigen Abständen, wenn Sie die Sperren löschen. Wie oft Sie dies tun, hängt vom Profiling ab. Sie können treten, ohne den Mutex-Maifisch zu erwerben (aber Sie müssen manchmal den Mutex erwerben, nachdem Sie die Bools gelöscht haben, um mit einer Race Condition fertig zu werden, die einen Thread verhungern könnte).

Die Aufgaben in der Reihenfolge aufreihen, die vom obigen Sammelsystem angegeben wird, da dies die Wahrscheinlichkeit von Kollisionen von Threads verringert. Aber mit diesem System kann die Arbeit auch dann weitergehen, wenn es eine Aufgabe gibt, die zurückfällt.

Es fügt Komplexität und Synchronisation, die es leicht langsamer als die reine Sammlung/Kohorte machen könnte.