Ich habe vor kurzem ein kleines Programm geschrieben, das im Grunde genommen über ein N-dimensionales Gitter läuft und an jedem Punkt Berechnungen durchführt.
%Vor%Es hat gut funktioniert, yadda yadda yadda, schöne Graphen sind entstanden ;-) Aber dann dachte ich, ich habe zwei Kerne auf meinem Computer, warum mache ich dieses Programm nicht Multithread, damit ich es doppelt so schnell ausführen kann?
Nun, meine Schleifen laufen ungefähr, sagen wir, ungefähr eine Milliarde Berechnungen, und ich brauche eine Möglichkeit, sie unter Threads aufzuteilen. Ich denke, ich sollte die Berechnungen in "Aufgaben" gruppieren - sagen wir, dass jede Wiederholung der äußersten Schleife eine Aufgabe ist - und die Aufgaben an Threads verteilen. Ich habe darüber nachgedacht
i1 % nthreads == n - im Wesentlichen vorherbestimmend, welche Aufgaben zu welchen Threads i1 in diesem Fall) der nächsten auszuführenden Aufgabe enthält - dynamische Zuweisung von Aufgaben an Threads Welche Gründe gibt es, um einen Ansatz gegenüber dem anderen zu wählen? Oder ein anderer Ansatz, an den ich nicht gedacht habe? Ist es überhaupt wichtig?
Übrigens habe ich dieses spezielle Programm in C geschrieben, aber ich stelle mir vor, dass ich dasselbe in anderen Sprachen noch einmal machen werde, also müssen die Antworten nicht C-spezifisch sein. (Wenn irgendjemand eine C-Bibliothek für Linux kennt, die das tut, würde ich es gerne wissen)
EDIT : In diesem Fall ist bin_index eine deterministische Funktion, die nichts außer ihren eigenen lokalen Variablen ändert. Etwas wie das:
(obwohl ich alle Kommentare schätze, auch diejenigen, die nicht für einen deterministischen bin_index gelten)
Der erste Ansatz ist einfach. Es ist auch ausreichend, wenn Sie erwarten, dass die Belastung gleichmäßig über die Gewinde verteilt wird. In einigen Fällen, insbesondere wenn die Komplexität von bin_index stark von den Parameterwerten abhängt, könnte einer der Threads mit einer viel schwereren Aufgabe enden als der Rest. Denken Sie daran: Die Aufgabe ist beendet, wenn die letzten Threads beendet sind.
Der zweite Ansatz ist etwas komplizierter, gleicht die Last jedoch gleichmäßiger aus, wenn die Tasks ausreichend fein genug sind (die Anzahl der Tasks ist viel größer als die Anzahl der Threads).
Beachten Sie, dass Sie möglicherweise Probleme haben, die Berechnungen in separate Threads zu stellen. Stellen Sie sicher, dass bin_index korrekt funktioniert, wenn mehrere Threads gleichzeitig ausgeführt werden. Vorsicht vor der Verwendung von globalen oder statischen Variablen für Zwischenergebnisse.
Außerdem könnte "Histogramm [bin_index (i1, i2, i3, i4)] + = 1" von einem anderen Thread unterbrochen werden, was zu einem falschen Ergebnis führt (wenn die Zuweisung den Wert holt, inkrementiert und speichert den resultierenden Wert) Wert im Array). Sie können für jeden Thread ein lokales Histogramm erstellen und die Ergebnisse zu einem einzigen Histogramm kombinieren, wenn alle Threads beendet sind. Sie können auch sicherstellen, dass nur ein Thread das Histogramm gleichzeitig ändert, aber das kann dazu führen, dass sich die Threads die meiste Zeit gegenseitig blockieren.
Der erste Ansatz ist genug. Keine Notwendigkeit für Komplikationen hier. Wenn Sie anfangen, mit Mutexen zu spielen, riskieren Sie, Fehler zu entdecken.
Beginne nicht zu komplizieren, es sei denn, du siehst wirklich, dass du das brauchst. Synchronisierungsprobleme (besonders bei vielen Threads anstelle von vielen Prozessen) können sehr schmerzhaft sein.
Wie ich es verstehe, OpenMP wurde nur für das gemacht, was Sie versuchen zu tun, obwohl ich zugeben muss habe es noch nicht selbst benutzt. Im Grunde scheint es, als würde man nur einen Header hinzufügen und eine Pragma-Klausel hinzufügen.
Sie könnten wahrscheinlich auch die Thread Building Blocks Bibliothek von Intel verwenden.
Wenn Sie nie eine Multithread-Anwendung programmiert haben, entblöße ich Sie, um mit OpenMP zu beginnen:
In Ihrem Beispiel sollten Sie nur dieses Pragma hinzufügen:
%Vor% Mit diesem Pragma fügt der Compiler einige Anweisungen hinzu, um Threads zu erstellen, sie zu starten, einige Mutexe um Zugriffe auf die histogram Variable usw. hinzuzufügen ... Es gibt viele Optionen, aber ein gut definiertes Pragma erledigt die ganze Arbeit für dich. Grundsätzlich hängt die Einfachheit von der Datenabhängigkeit ab.
Natürlich sollte das Ergebnis nicht optimal sein, als ob Sie alles von Hand codiert hätten. Aber wenn Sie kein Lastverteilungsproblem haben, könnten Sie sich vielleicht einer zweifachen Geschwindigkeit nähern. Eigentlich ist das nur in Matrix geschrieben, ohne räumliche Abhängigkeit.
Wenn Sie es jemals in .NET machen, verwenden Sie die parallelen Erweiterungen .
Wenn Sie Multithreading-Code schreiben wollen (und Sie werden in Zukunft eine Menge davon machen), würde ich vorschlagen, dass Sie sich eine funktionale Sprache wie OCaml oder Haskell anschauen.
Wegen des Mangels an Nebenwirkungen und des Fehlens eines gemeinsamen Zustands in funktionalen Sprachen (naja, meistens) macht es Ihren Code viel einfacher, über mehrere Threads hinweg zu laufen. Außerdem werden Sie wahrscheinlich feststellen, dass Sie viel weniger Code haben.
Ich stimme Sharptooth zu, dass Ihre erste Herangehensweise als die einzig plausible erscheint.
Ihre Single-Thread-App weist ständig Speicher zu. Um eine Beschleunigung zu erreichen, müssten Ihre verschiedenen Threads auch ständig dem Speicher zugewiesen werden. Wenn nur ein Thread auf einmal zuweist, würden Sie überhaupt keine Beschleunigung erhalten. Wenn also Ihre Aufgaben überwacht werden, würde die gesamte Übung fehlschlagen.
Dies wäre ein gefährlicher Ansatz, da Sie Shared Memory ohne Guard zuweisen. Aber es scheint die Gefahr wert zu sein (wenn eine x2 Beschleunigung zählt). Wenn Sie sicher sein können, dass alle Werte von bin_index (i1, i2, i3, i4) in Ihrer Division der Schleife unterschiedlich sind, sollte es funktionieren, da die Array-Zuweisung zu verschiedenen Speicherorten in Ihrem Shared Memory erfolgen würde. Dennoch sollte man solche Ansätze immer genau beobachten.
Ich nehme an, Sie würden auch eine Testroutine erstellen, um die Ergebnisse der beiden Versionen zu vergleichen.
Mit Blick auf Ihren bin_index (i1, i2, i3, i4) vermute ich, dass Ihr Prozess nicht ohne großen Aufwand parallelisiert werden konnte.
Die einzige Möglichkeit, die Berechnungsarbeit in Ihrer Schleife aufzuteilen, ist wiederum, dass Ihre Threads auf die gleichen Bereiche im Speicher zugreifen. Es sieht jedoch so aus, als würde bin_index (i1, i2, i3, i4) wahrscheinlich Werte ziemlich oft wiederholen. Sie können die Iteration in die Bedingungen aufteilen, in denen bin_index höher als ein Cutoff ist und wo sie niedriger als ein Cut-off ist. Oder Sie können es beliebig teilen und sehen, ob das Inkrement atomar implementiert ist. Es ist jedoch unwahrscheinlich, dass ein komplexer Threading-Ansatz eine Verbesserung bringt, wenn Sie nur mit zwei Kernen arbeiten können, um damit zu beginnen.
Tags und Links multithreading loops