Ich habe einen cpu-konsumierenden Code, wo einige Funktionen mit einer Schleife viele mal ausgeführt werden. Jede Optimierung in dieser Schleife bringt eine merkliche Leistungssteigerung. Frage: Wie würden Sie diese Schleife optimieren (es gibt nicht viel mehr zu optimieren, aber ...)?
%Vor%Ich habe ein paar Dinge ausprobiert, z. Ich ersetzte Arrays mit Zeigern, die in jeder Schleife inkrementiert wurden, aber (überraschend) verlor ich etwas Leistung anstatt zu gewinnen ...
Bearbeiten:
itsMaximums , error) int64_t , also sind negativ und positiv N ist zur Kompilierzeit unbekannt _m128i , das Ausführen und Zurückspeichern war höher als bei der SSE-Geschwindigkeit. Ich bin kein Experte für SSE, also vielleicht hatte ich einen schlechten Code) Ergebnisse:
Ich habe eine Loop-Entfaltung hinzugefügt, und einen netten Hack von Alex'es Post. Unten füge ich einige Ergebnisse ein:
strage, dass 4) ist nicht schneller als 3) und 4). Unter dem Code für 4):
%Vor%
# Ankündigung siehe chatHallo Jakub, was würdest du sagen, wenn ich eine Version gefunden habe, die eine heuristische Optimierung verwendet, die bei gleichmäßig verteilten Zufallsdaten zu ~ 3.2x Geschwindigkeitszunahme für
int64_tführt (10.56x effektiv mitfloats)?Ich muss noch die Zeit finden, um den Beitrag zu aktualisieren, aber die Erklärung und der Code können durch den Chat gefunden werden.
Ich habe den gleichen Code für das Testbett verwendet (siehe unten), um zu verifizieren, dass die Ergebnisse korrekt sind und exakt mit der ursprünglichen Implementierung aus Ihrem OP übereinstimmen Bearbeiten : Ironischerweise hatte dieses Testbed einen fatalen Fehler, der die Ergebnisse ungültig machte: Die heuristische Version übersprang tatsächlich Teile der Eingabe, aber da die vorhandene Ausgabe nicht gelöscht wurde, erschien sie um die richtige Ausgabe zu haben ... (immer noch editieren ...)
Ok, ich habe einen Benchmark veröffentlicht, der auf Ihren Code-Versionen basiert, und auch meine vorgeschlagene Verwendung von partial_sum .
Hier finden Sie den gesamten Code Ссылка
Für eine Standardkonfiguration von
%Vor%Es wird ( siehe Ausgabefragment hier ) ):
int64_t ) Es gibt eine Reihe von (überraschenden oder nicht überraschenden) Ergebnissen:
Es gibt keinen signifikanten Leistungsunterschied zwischen den Algorithmen ( für Integer-Daten ), vorausgesetzt, Sie kompilieren mit aktivierten Optimierungen. (Siehe Makefile ; mein Bogen ist 64bit, Intel Core Q9550 mit gcc-4.6.1)
Die Algorithmen sind nicht äquivalent (die Hash-Summen unterscheiden sich): Insbesondere die von Alex vorgeschlagene Bitgeige behandelt den Integer-Überlauf nicht ganz genau (dies kann mit begrenzt die Eingabedaten, so dass keine Überläufe auftreten; Beachten Sie, dass die Vielleicht ist es für Ihren Zweck in Ordnung?) partial_sum_incorrect -Version äquivalente C ++ - nicht bitweise_arithmetische Operationen zeigt, die zu denselben verschiedenen Ergebnissen führen:
Überraschenderweise Es ist nicht teurer, beide Definitionen des max-Algorithmus auf einmal zu berechnen. Sie können sehen, dass dies in partial_sum_correct gemacht wird: es berechnet beide 'Formeln' von max in der gleichen Schleife; Das ist wirklich nicht mehr als ein Triva hier, denn keine der beiden Methoden ist wesentlich schneller ...
Noch überraschender ist ein großer Leistungsschub , wenn Sie float anstelle von int64_t verwenden können. Ein schneller und schmutziger Hack kann auf den Benchmark angewendet werden
zeigt, dass der STL-basierte Algorithmus ( partial_sum_incorrect ) bei Verwendung von float anstelle von int64_t (!!!) ungefähr 2,5x schneller ausführt.
Hinweis:
partial_sum_incorrect sich nur auf Integer-Überlauf bezieht, was nicht für Floats gilt; Das kann daran gesehen werden, dass die Hashes übereinstimmen, also ist es _partial_sum_float_correct_:) partial_sum_correct doppelte Arbeit leistet, die dazu führt, dass sie im Gleitkomma-Modus schlecht abschneidet. Sehen Sie bullet 3.
(Und da war dieser Off-by-1-Bug in der Loop-entrollten Version von dem OP, den ich vorher erwähnt habe)
Für Ihr Interesse sieht die Partialsummenanwendung in C ++ 11 so aus:
%Vor%Zuerst müssen Sie sich die generierte Assembly ansehen. Andernfalls haben Sie keine Möglichkeit zu wissen, was tatsächlich passiert , wenn diese Schleife ausgeführt wird.
Nun: läuft dieser Code auf einer 64-Bit-Maschine? Wenn nicht, könnten diese 64-Bit-Ergänzungen ein bisschen weh tun.
Diese Schleife scheint ein offensichtlicher Kandidat für die Verwendung von SIMD-Anweisungen zu sein. SSE2 unterstützt eine Reihe von SIMD-Anweisungen für Integer-Arithmetik, wobei einschließlich einige, die auf zwei 64-Bit-Werten arbeiten, sind.
Sehen Sie außerdem nach, ob der Compiler die Schleife ordnungsgemäß entrollt, und wenn nicht, tun Sie dies selbst. Rollen Sie ein paar Iterationen der Schleife aus und ordnen Sie dann die Reihenfolge neu an. Setzen Sie alle Speicherlasten an den Anfang der Schleife, damit sie so früh wie möglich gestartet werden können.
Überprüfen Sie für die Zeile if , ob der Compiler eine bedingte Verschiebung statt einer Verzweigung generiert.
Sehen Sie abschließend, ob Ihr Compiler etwas wie das restrict / __restrict -Schlüsselwort unterstützt. Es ist kein Standard in C ++, aber es ist sehr nützlich, um dem Compiler anzuzeigen, dass in und out nicht auf die gleichen Adressen zeigen.
Ist die Größe ( N ) zur Kompilierzeit bekannt? Wenn ja, machen Sie es zu einem Template-Parameter (und versuchen Sie dann, in und out als Referenzen auf Arrays mit richtiger Größe zu übergeben, da dies auch dem Compiler mit Aliasing-Analyse helfen kann)
Nur ein paar Gedanken von meinem Kopf. Aber noch einmal, studieren Sie die Demontage. Sie müssen wissen, was der Compiler für Sie tut und vor allem, was nicht für Sie tut.
Bearbeiten
mit Ihrer Bearbeitung:
%Vor%Was mir auffällt ist, dass Sie eine große Abhängigkeitskette hinzugefügt haben. Bevor das Ergebnis berechnet werden kann, muss max negiert werden, das Ergebnis muss verschoben werden, das Ergebnis von das muss und zusammen mit seinem ursprünglichen Wert und dem Ergebnis sein das muss zu einer anderen Variablen hinzugefügt werden.
Mit anderen Worten, alle diese Operationen müssen serialisiert werden. Sie können einen von ihnen nicht starten, bevor der vorherige beendet ist. Das ist nicht unbedingt eine Beschleunigung. Moderne Pipeline-Out-of-Order-CPUs können viele Dinge parallel ausführen. Es mit einer einzigen langen Kette abhängiger Anweisungen zu binden, ist eines der lähmendsten Dinge, die man tun kann. (Natürlich, wenn es mit anderen Iterationen verschachtelt werden kann, könnte es besser funktionieren. Aber mein Bauchgefühl ist, dass ein einfacher bedingter Bewegungsbefehl vorzuziehen wäre)
Manchmal musst du einen Schritt zurückgehen und nochmal darüber nachsehen. Die erste Frage ist offensichtlich, brauchst du das? Könnte es einen alternativen Algorithmus geben, der eine bessere Leistung bringt?
Wenn das gesagt wird, und angenommen, dass Sie sich wegen dieser Frage bereits auf diesen Algorithmus festgelegt haben, können wir versuchen, darüber nachzudenken, was wir tatsächlich haben.
Disclaimer: Die Methode, die ich beschreibe, ist inspiriert von der erfolgreichen Methode, die Tim Peters verwendet hat, um die traditionelle Introsort-Implementierung zu verbessern, was zu TimSort . Also bitte bitte mit mir;)
1. Extrahieren von Eigenschaften
Das Hauptproblem, das ich sehen kann, ist die Abhängigkeit zwischen Iterationen, die viele der möglichen Optimierungen verhindern und viele Parallelisierungsversuche vereiteln.
%Vor%Lassen Sie uns diesen Code auf funktionale Weise überarbeiten:
%Vor%Wo:
%Vor%Oder eher eine vereinfachte Version (Überlauf aufheben, da sie undefiniert ist):
%Vor% Bemerken Sie den Tipppunkt? Das Verhalten ändert sich, je nachdem, ob das schlecht benannte (*) max positiv oder negativ ist.
Dieser Tipping-Punkt macht es interessant, die Werte in in näher zu betrachten, insbesondere je nachdem, welchen Effekt sie auf max haben könnten:
max < 0 und in[i] < 0 dann out[i] = in[i] < 0
max < 0 und in[i] > 0 dann out[i] = in[i] > 0
max > 0 und in[i] < 0 dann out[i] = (max + in[i]) ?? 0
max > 0 und in[i] > 0 dann out[i] = (max + in[i]) > 0
(*) schlecht benannt, weil es auch ein Akkumulator ist, den der Name verbirgt. Ich habe jedoch keinen besseren Vorschlag.
2. Operationen optimieren
Dies führt uns dazu, interessante Fälle zu entdecken:
[i, j) des Arrays haben, die nur negative Werte enthält (was wir negative Scheibe nennen), dann könnten wir eine std::copy(in + i, in + j, out + i) und max = out[j-1] machen
[i, j) des Arrays haben, das nur positive Werte enthält, dann ist es ein reiner Akkumulationscode (der leicht entrollt werden kann) max wird positiv, sobald in[i] positiv ist Daher könnte es interessant sein (aber vielleicht nicht, ich verspreche es nicht), ein Profil des Inputs zu erstellen, bevor ich mit ihm arbeite. Beachten Sie, dass das Profil für große Eingaben Chunk für Chunk erstellt werden könnte, z. B. die Chunk-Größe basierend auf der Cache-Zeilengröße anpassen.
Für Referenzen, die 3 Routinen:
%Vor%Wenn wir nun annehmen, dass wir die Eingabe irgendwie mit einer einfachen Struktur charakterisieren können:
%Vor%Nun, es sei denn, Introsort ist die Arbeit in der Schleife minimal, also könnte die Berechnung der Eigenschaften zu kostspielig sein, wie es ist ... aber es führt sich selbst gut zur Parallelisierung .
3. Einfache Parallelisierung
Beachten Sie, dass die Charakterisierung eine reine Funktion der Eingabe ist. Unter der Voraussetzung, dass Sie in einem Stück pro Stück arbeiten, könnte es möglich sein, parallel zu haben:
Slice::Type -Wert berechnet Selbst wenn die Eingabe im Wesentlichen zufällig ist, kann es, wenn der Chunk klein genug ist (z. B. eine CPU L1 Cache-Zeile), Chunks geben, für die er funktioniert. Die Synchronisierung zwischen den beiden Threads kann mit einer einfachen Thread-sicheren Warteschlange von Slice (Producer / Consumer) und einem bool last -Attribut durchgeführt werden, um den Verbrauch zu stoppen oder indem Slice in einem Vektor mit einem Unknown -Typ erstellt wird und den Verbraucher blockieren lassen, bis er bekannt ist (mit Atomics).
Hinweis: Da die Charakterisierung rein ist, ist es peinlich parallel.
4. Mehr Parallelisierung: Spekulative Arbeit
Merken Sie sich diese unschuldige Bemerkung: max wird positiv, sobald in[i] positiv ist .
Angenommen, wir können (zuverlässig) erraten, dass Slice[j-1] einen max -Wert erzeugt, der negativ ist, dann ist die Berechnung für Slice[j] unabhängig von dem, was ihnen vorausgegangen ist, und wir können jetzt mit der Arbeit beginnen!
Natürlich ist es eine Vermutung, also könnten wir uns irren ... aber sobald wir alle Slices vollständig charakterisiert haben, haben wir freie Cores, also können wir sie auch für spekulative Arbeit verwenden! Und wenn wir falsch liegen? Nun, der Consumer-Thread wird unseren Fehler einfach sanft löschen und durch den korrekten Wert ersetzen.
Die Heuristik zur spekulativen Berechnung von Slice sollte einfach sein und muss angepasst werden. Es kann auch adaptiv sein ... aber das könnte schwieriger sein!
Fazit
Analysieren Sie Ihr Dataset und versuchen Sie herauszufinden, ob Abhängigkeiten aufgehoben werden können. Wenn es ist, können Sie wahrscheinlich davon profitieren, auch ohne Multi-Thread.
Wenn die Werte von max und in[] weit entfernt von 64 Bit min / max sind (sagen wir, sie sind immer zwischen -2 61 und +2 61 ), können Sie eine Schleife ohne die bedingte Verzweigung versuchen, die möglicherweise eine Verschlechterung der Leistung verursacht:
Theoretisch kann der Compiler auch einen ähnlichen Trick machen, aber ohne die Disassemblierung zu sehen, ist es schwer zu sagen, ob es das tut.
Der Code erscheint schon ziemlich schnell. Abhängig von der Art des in-Arrays könnten Sie ein spezielles Casing ausprobieren. Wenn Sie beispielsweise wissen, dass in einer bestimmten Invokation alle Eingabezahlen positiv sind, ist out [i] gleich der kumulativen Summe, ohne dass dies erforderlich ist ein if-Zweig.
Zuerst müssen Sie sich die generierte Assembly ansehen. Andernfalls haben Sie keine Möglichkeit zu wissen, was tatsächlich passiert , wenn diese Schleife ausgeführt wird.
Nun: läuft dieser Code auf einer 64-Bit-Maschine? Wenn nicht, könnten diese 64-Bit-Ergänzungen ein bisschen weh tun.
Diese Schleife scheint ein offensichtlicher Kandidat für die Verwendung von SIMD-Anweisungen zu sein. SSE2 unterstützt eine Reihe von SIMD-Anweisungen für Integer-Arithmetik, wobei einschließlich einige, die auf zwei 64-Bit-Werten arbeiten, sind.
Sehen Sie außerdem nach, ob der Compiler die Schleife ordnungsgemäß entrollt, und wenn nicht, tun Sie dies selbst. Rollen Sie ein paar Iterationen der Schleife aus und ordnen Sie dann die Reihenfolge neu an. Setzen Sie alle Speicherlasten an den Anfang der Schleife, damit sie so früh wie möglich gestartet werden können.
Überprüfen Sie für die Zeile %code% , ob der Compiler eine bedingte Verschiebung statt einer Verzweigung generiert.
Sehen Sie abschließend, ob Ihr Compiler etwas wie das %code% / %code% -Schlüsselwort unterstützt. Es ist kein Standard in C ++, aber es ist sehr nützlich, um dem Compiler anzuzeigen, dass %code% und %code% nicht auf die gleichen Adressen zeigen.
Ist die Größe ( %code% ) zur Kompilierzeit bekannt? Wenn ja, machen Sie es zu einem Template-Parameter (und versuchen Sie dann, %code% und %code% als Referenzen auf Arrays mit richtiger Größe zu übergeben, da dies auch dem Compiler mit Aliasing-Analyse helfen kann)
Nur ein paar Gedanken von meinem Kopf. Aber noch einmal, studieren Sie die Demontage. Sie müssen wissen, was der Compiler für Sie tut und vor allem, was nicht für Sie tut.
Bearbeiten
mit Ihrer Bearbeitung:
%Vor%Was mir auffällt ist, dass Sie eine große Abhängigkeitskette hinzugefügt haben. Bevor das Ergebnis berechnet werden kann, muss max negiert werden, das Ergebnis muss verschoben werden, das Ergebnis von das muss und zusammen mit seinem ursprünglichen Wert und dem Ergebnis sein das muss zu einer anderen Variablen hinzugefügt werden.
Mit anderen Worten, alle diese Operationen müssen serialisiert werden. Sie können einen von ihnen nicht starten, bevor der vorherige beendet ist. Das ist nicht unbedingt eine Beschleunigung. Moderne Pipeline-Out-of-Order-CPUs können viele Dinge parallel ausführen. Es mit einer einzigen langen Kette abhängiger Anweisungen zu binden, ist eines der lähmendsten Dinge, die man tun kann. (Natürlich, wenn es mit anderen Iterationen verschachtelt werden kann, könnte es besser funktionieren. Aber mein Bauchgefühl ist, dass ein einfacher bedingter Bewegungsbefehl vorzuziehen wäre)
Ich habe einen cpu-konsumierenden Code, wo einige Funktionen mit einer Schleife viele mal ausgeführt werden. Jede Optimierung in dieser Schleife bringt eine merkliche Leistungssteigerung. Frage: Wie würden Sie diese Schleife optimieren (es gibt nicht viel mehr zu optimieren, aber ...)?
%Vor%Ich habe ein paar Dinge ausprobiert, z. Ich ersetzte Arrays mit Zeigern, die in jeder Schleife inkrementiert wurden, aber (überraschend) verlor ich etwas Leistung anstatt zu gewinnen ...
Bearbeiten:
Ergebnisse:
Ich habe eine Loop-Entfaltung hinzugefügt, und einen netten Hack von Alex'es Post. Unten füge ich einige Ergebnisse ein:
strage, dass 4) ist nicht schneller als 3) und 4). Unter dem Code für 4):
%Vor%Wenn die Werte von %code% und %code% weit entfernt von 64 Bit min / max sind (sagen wir, sie sind immer zwischen -2 61 und +2 61 ), können Sie eine Schleife ohne die bedingte Verzweigung versuchen, die möglicherweise eine Verschlechterung der Leistung verursacht:
%Vor%Theoretisch kann der Compiler auch einen ähnlichen Trick machen, aber ohne die Disassemblierung zu sehen, ist es schwer zu sagen, ob es das tut.
Sicherstellung der Methode ist nicht virtuell , Inline , _ Attribut _ ((always_inline)) und -Funroll-loops scheinen gute Optionen zu sein, um sie zu erkunden.
Nur wenn Sie ein Benchmarking durchführen, können wir feststellen, ob es sich bei Ihrem größeren Programm um sinnvolle Optimierungen handelt.
Der Code erscheint schon ziemlich schnell. Abhängig von der Art des in-Arrays könnten Sie ein spezielles Casing ausprobieren. Wenn Sie beispielsweise wissen, dass in einer bestimmten Invokation alle Eingabezahlen positiv sind, ist out [i] gleich der kumulativen Summe, ohne dass dies erforderlich ist ein if-Zweig.
Das einzige, was einem einfällt, dass vielleicht helfen kann, ist die Verwendung von Zeigern anstelle von Array-Indizes in Ihrer Schleife, etwa
%Vor%Hier wird angenommen, dass ein Index in ein Array so kompiliert werden kann, dass er die Basisadresse des Arrays übernimmt, die Größe des Elements mit dem Index multipliziert und das Ergebnis addiert, um die Elementadresse zu erhalten. Laufende Zeiger zu halten vermeidet dies. Ich nehme an, dass ein guter optimierender Compiler das schon tut, also müssten Sie die aktuelle Assembler-Ausgabe studieren.
# Ankündigung siehe chatHallo Jakub, was würdest du sagen, wenn ich eine Version gefunden habe, die eine heuristische Optimierung verwendet, die bei gleichmäßig verteilten Zufallsdaten zu ~ 3.2x Geschwindigkeitszunahme für %code% führt (10.56x effektiv mit %code% s)?
Ich muss noch die Zeit finden, um den Beitrag zu aktualisieren, aber die Erklärung und der Code können durch den Chat gefunden werden.
Ich habe den gleichen Code für das Testbett verwendet (siehe unten), um zu verifizieren, dass die Ergebnisse korrekt sind und exakt mit der ursprünglichen Implementierung aus Ihrem OP übereinstimmen Bearbeiten : Ironischerweise hatte dieses Testbed einen fatalen Fehler, der die Ergebnisse ungültig machte: Die heuristische Version übersprang tatsächlich Teile der Eingabe, aber da die vorhandene Ausgabe nicht gelöscht wurde, erschien sie um die richtige Ausgabe zu haben ... (immer noch editieren ...)
Ok, ich habe einen Benchmark veröffentlicht, der auf Ihren Code-Versionen basiert, und auch meine vorgeschlagene Verwendung von %code% .
Hier finden Sie den gesamten Code Ссылка
Für eine Standardkonfiguration von
%Vor%Es wird ( siehe Ausgabefragment hier ) ):
Es gibt eine Reihe von (überraschenden oder nicht überraschenden) Ergebnissen:
Es gibt keinen signifikanten Leistungsunterschied zwischen den Algorithmen ( für Integer-Daten ), vorausgesetzt, Sie kompilieren mit aktivierten Optimierungen. (Siehe Makefile ; mein Bogen ist 64bit, Intel Core Q9550 mit gcc-4.6.1)
Die Algorithmen sind nicht äquivalent (die Hash-Summen unterscheiden sich): Insbesondere die von Alex vorgeschlagene Bitgeige behandelt den Integer-Überlauf nicht ganz genau (dies kann mit begrenzt die Eingabedaten, so dass keine Überläufe auftreten; Beachten Sie, dass die %code% -Version äquivalente C ++ - nicht bitweise_arithmetische Operationen zeigt, die zu denselben verschiedenen Ergebnissen führen: Vielleicht ist es für Ihren Zweck in Ordnung?)
Überraschenderweise Es ist nicht teurer, beide Definitionen des max-Algorithmus auf einmal zu berechnen. Sie können sehen, dass dies in %code% gemacht wird: es berechnet beide 'Formeln' von max in der gleichen Schleife; Das ist wirklich nicht mehr als ein Triva hier, denn keine der beiden Methoden ist wesentlich schneller ...
Noch überraschender ist ein großer Leistungsschub , wenn Sie %code% anstelle von %code% verwenden können. Ein schneller und schmutziger Hack kann auf den Benchmark angewendet werden
%Vor% zeigt, dass der STL-basierte Algorithmus ( %code% ) bei Verwendung von %code% anstelle von %code% (!!!) ungefähr 2,5x schneller ausführt.
Hinweis:
(Und da war dieser Off-by-1-Bug in der Loop-entrollten Version von dem OP, den ich vorher erwähnt habe)
Für Ihr Interesse sieht die Partialsummenanwendung in C ++ 11 so aus:
%Vor%Manchmal musst du einen Schritt zurückgehen und nochmal darüber nachsehen. Die erste Frage ist offensichtlich, brauchst du das? Könnte es einen alternativen Algorithmus geben, der eine bessere Leistung bringt?
Wenn das gesagt wird, und angenommen, dass Sie sich wegen dieser Frage bereits auf diesen Algorithmus festgelegt haben, können wir versuchen, darüber nachzudenken, was wir tatsächlich haben.
Disclaimer: Die Methode, die ich beschreibe, ist inspiriert von der erfolgreichen Methode, die Tim Peters verwendet hat, um die traditionelle Introsort-Implementierung zu verbessern, was zu TimSort . Also bitte bitte mit mir;)
1. Extrahieren von Eigenschaften
Das Hauptproblem, das ich sehen kann, ist die Abhängigkeit zwischen Iterationen, die viele der möglichen Optimierungen verhindern und viele Parallelisierungsversuche vereiteln.
%Vor%Lassen Sie uns diesen Code auf funktionale Weise überarbeiten:
%Vor%Wo:
%Vor%Oder eher eine vereinfachte Version (Überlauf aufheben, da sie undefiniert ist):
%Vor%Bemerken Sie den Tipppunkt? Das Verhalten ändert sich, je nachdem, ob das schlecht benannte (*) %code% positiv oder negativ ist.
Dieser Tipping-Punkt macht es interessant, die Werte in %code% näher zu betrachten, insbesondere je nachdem, welchen Effekt sie auf %code% haben könnten:
(*) schlecht benannt, weil es auch ein Akkumulator ist, den der Name verbirgt. Ich habe jedoch keinen besseren Vorschlag.
2. Operationen optimieren
Dies führt uns dazu, interessante Fälle zu entdecken:
Daher könnte es interessant sein (aber vielleicht nicht, ich verspreche es nicht), ein Profil des Inputs zu erstellen, bevor ich mit ihm arbeite. Beachten Sie, dass das Profil für große Eingaben Chunk für Chunk erstellt werden könnte, z. B. die Chunk-Größe basierend auf der Cache-Zeilengröße anpassen.
Für Referenzen, die 3 Routinen:
%Vor%Wenn wir nun annehmen, dass wir die Eingabe irgendwie mit einer einfachen Struktur charakterisieren können:
%Vor%Nun, es sei denn, Introsort ist die Arbeit in der Schleife minimal, also könnte die Berechnung der Eigenschaften zu kostspielig sein, wie es ist ... aber es führt sich selbst gut zur Parallelisierung .
3. Einfache Parallelisierung
Beachten Sie, dass die Charakterisierung eine reine Funktion der Eingabe ist. Unter der Voraussetzung, dass Sie in einem Stück pro Stück arbeiten, könnte es möglich sein, parallel zu haben:
Selbst wenn die Eingabe im Wesentlichen zufällig ist, kann es, wenn der Chunk klein genug ist (z. B. eine CPU L1 Cache-Zeile), Chunks geben, für die er funktioniert. Die Synchronisierung zwischen den beiden Threads kann mit einer einfachen Thread-sicheren Warteschlange von %code% (Producer / Consumer) und einem %code% -Attribut durchgeführt werden, um den Verbrauch zu stoppen oder indem %code% in einem Vektor mit einem %code% -Typ erstellt wird und den Verbraucher blockieren lassen, bis er bekannt ist (mit Atomics).
Hinweis: Da die Charakterisierung rein ist, ist es peinlich parallel.
4. Mehr Parallelisierung: Spekulative Arbeit
Merken Sie sich diese unschuldige Bemerkung: %code% wird positiv, sobald %code% positiv ist .
Angenommen, wir können (zuverlässig) erraten, dass %code% einen %code% -Wert erzeugt, der negativ ist, dann ist die Berechnung für %code% unabhängig von dem, was ihnen vorausgegangen ist, und wir können jetzt mit der Arbeit beginnen!
Natürlich ist es eine Vermutung, also könnten wir uns irren ... aber sobald wir alle Slices vollständig charakterisiert haben, haben wir freie Cores, also können wir sie auch für spekulative Arbeit verwenden! Und wenn wir falsch liegen? Nun, der Consumer-Thread wird unseren Fehler einfach sanft löschen und durch den korrekten Wert ersetzen.
Die Heuristik zur spekulativen Berechnung von %code% sollte einfach sein und muss angepasst werden. Es kann auch adaptiv sein ... aber das könnte schwieriger sein!
Fazit
Analysieren Sie Ihr Dataset und versuchen Sie herauszufinden, ob Abhängigkeiten aufgehoben werden können. Wenn es ist, können Sie wahrscheinlich davon profitieren, auch ohne Multi-Thread.
Das einzige, was einem einfällt, dass vielleicht helfen kann, ist die Verwendung von Zeigern anstelle von Array-Indizes in Ihrer Schleife, etwa
%Vor%Hier wird angenommen, dass ein Index in ein Array so kompiliert werden kann, dass er die Basisadresse des Arrays übernimmt, die Größe des Elements mit dem Index multipliziert und das Ergebnis addiert, um die Elementadresse zu erhalten. Laufende Zeiger zu halten vermeidet dies. Ich nehme an, dass ein guter optimierender Compiler das schon tut, also müssten Sie die aktuelle Assembler-Ausgabe studieren.
Tags und Links optimization c++ performance g++