Wie kann ich ein rechenintensives C ++ Programm mit einem bekannten Engpass optimieren?

Wenn Sie die "Pause" -Technik verwenden, sollte Ihnen mehr als nur sagen, dass Sie in dieser Schleife sind. Es sollte Ihnen sagen, wo in der Schleife.

Errate nie, wann du es herausfinden kannst. Das heißt, hier ist meine Vermutung :-) Sie machen die gesamte Summierung in Gleitkommavariablen, aber die ursprünglichen Zahlen als ganzzahlige Zeichen, oder? Dann können Sie erwarten, dass die Konvertierung von "int" zu "double" einige Zeit in Anspruch nimmt, und wenn dies der Fall ist, sehen Sie, dass Ihre Pausen in diesen Anweisungen einen guten Teil der Zeit ausmachen. Also im Grunde frage ich mich, warum Sie nicht alles in Ganzzahlarithmetik tun.

Sie sagen, dass die Auslastung niemals über 25% hinausgeht. Könnte das sein, weil es nur einen der 4 Kerne verwendet?

Sie sagen, die Auslastung sinkt oft unter 25%. Das deutet darauf hin, dass der Thread blockiert, um Datei-I / O zu machen. Wenn dies der Fall ist, sollten Ihre Pausen es in der Tat erfassen und bestätigen. Wenn dies der Fall ist, können Sie möglicherweise die E / A beschleunigen, indem Sie größere Blöcke verwenden oder möglicherweise weniger häufig öffnen / schließen. Beachten Sie, dass Verbesserungen an Ihrer inneren Schleife die in dieser Schleife verbrachte Zeit verkürzen, die Zeit in I / O jedoch nicht schrumpfen wird. Daher erhöht sich der prozentuale Anteil der Zeit in I / O, was zu einem offensichtlichen Rückgang der Auslastung führt. , bis du auch das machst.

Die Nutzung ist eigentlich keine sehr nützliche Nummer. Es ist nur ein Indikator für den CPU / IO-Split und sagt Ihnen überhaupt nichts, wenn Sie zu viel von beiden machen.

Wie @renick gesagt hat, entferne die Adressberechnungen. Du solltest in der Lage sein, diese Schleife auf der Ebene der Assemblersprache zu durchlaufen und zu sehen, dass sie nichts mehr tut, als wenn du deinen "Guru" -Hut anziehst und die Versammlung selbst schreibst.

In jedem Fall könnte die Vektorisierung ein großer Gewinn sein.

Verschiedene Gedanken:

• Sie sagen, dass Sie nur eine CPU-Auslastung von etwa 25% erreichen. Ich kann mir zwei Gründe dafür vorstellen:
  1. Sie tauschen aus. Wie groß ist Ihre Matrize? Passen sie vollständig in das physische Gedächtnis? Sehen Sie sich die Speicherbelegung und Größe Ihres Arbeitssatzes an.
  2. Der Rest des Anwendungscodes blockiert auf E / A. Umfasst der Code, der Ihre Kernroutine umgibt, eine beliebige E / A? Es könnte dort für große Zeitspannen blockiert werden, aber natürlich sehen Sie das nicht mit der Technik "pause-when-busy-and-inspect", denn wenn der Prozess wieder freigibt, kehrt er direkt in Ihren rechenintensiven Kern zurück Routine.
• Sehen Sie sich den Assemblercode für Ihre Kernroutine an. Sieht es vernünftig aus?
• Müssen Sie tatsächlich diffsum innerhalb der Schleife berechnen? Es sieht so aus, als ob du diffsum=sumA-sumB einmal außerhalb der Schleife tun könntest - aber es kann numerische Überlegungen geben, die dich davon abhalten, dies zu tun.
• Wie Renick bereits bemerkt hat, scheint dies ein Hauptziel für die SSE-Optimierung zu sein. Auch hier sollten Sie sicherstellen, dass der Compiler sinnvollen Assembler-Code generiert (wenn Sie intrinsic verwenden und die Assembly nicht selbst schreiben).
• Wenn Sie SSE-Code nicht selbst schreiben wollen, stellen Sie sicher, dass das SSE-Flag Ihres Compilers gesetzt ist. Dies ermöglicht dem Compiler, die SSE-Einheit anstelle der FPU für skalare Fließkommaoperationen zu verwenden, was allein die Leistung verbessert, da die Stack-basierte FPU auf dem x86 notorisch schlecht für die Generierung von Compiler-Code geeignet ist.

Können Sie den Assembler-Code überprüfen, den diese Schleife generiert? Wenn Sie nur 25% Prozessor verwenden, kann es sein, dass diese Schleife speichergebunden ist. Es gibt dort ungefähr acht lokale Variablen und ich stelle mir vor, der Compiler ordnet sie nicht allen Registern zu, so dass in jeder Schleife viele Speicheroperationen ausgeführt werden. Eine Überlegung wäre, diese Schleife in Assembler zu schreiben.

Warum gehen Sie die Matrix Spalte für Spalte? Matrizen werden Zeile für Zeile im Speicher gespeichert. Wenn Sie also auf eine ganze Spalte in der inneren Schleife zugreifen, fordern Sie wahrscheinlich mehr Speicher auf Ihren verschiedenen Speicherebenen (Caches usw.).

Sie sollten auch versuchen, wenn Sie die Schleife nicht über eine einfache Konfiguration wie OpenMP multithread können. Die CPU-Auslastung von 25% klingt wie ein Quad-Core, der einen einzelnen Worker-Thread ausführt.

Sie sollten versuchen, Ihre Schleifen loszuwerden und stattdessen versuchen, die Operationen zu vektorisieren. Mit einer Bibliothek wie Eigen würde Ihr Code etwa so aussehen:

Speichern Sie Matrizen mit denselben Parametern außerhalb der Schleife? Ich denke, das sollte dir etwas ersparen.

"25% seiner Grenze, und mit relativ großen Oszillationen, wo ich eine stetige 100% Last erwarten würde, bis das Programm endet."

Sie haben erwähnt, dass die Funktion von einer ganzen Reihe von Bedingungen und Kontrollzweigen umgeben ist. Ich schätze deshalb, dass CPU-Pipelines geleert werden, anstatt effizient genutzt zu werden. Versuchen Sie, Ihre Software so umzuschreiben, dass keine großen Verzweigungen erforderlich sind.

Ich würde auch empfehlen, eine der mathematischen Bibliotheken wie Eigen , ATLAS oder GSL

TLDR: Optimieren Sie zunächst den Matrixmultiplikationsalgorithmus, beobachten Sie dann Ihre Anzahl von Provisorien und optimieren Sie dann Ihre Matrix-internen Zuordnungen.

Lange Antwort:

Ich denke, das Wichtigste ist die Optimierung Ihrer Matrizenmultiplikation. Die Multiplikation von Matrizen für den intuitivsten Algorithmus ist O (n ^ 3) (was selbst für kleine Matrizen sehr groß ist).

Um Ihnen ein Beispiel zu geben, haben Sie für 2x2 Matrix Multiplikation 16 Multiplikationen ("mo"). Für 3x3 Matrixmultiplikation haben Sie 27 mo und für 4x4 64 mo.

Ich bin mir nicht sicher, wie es in Ihrem Fall implementiert wird, aber wenn es der intuitive Algorithmus ist (als eine dreifache for -Schleife), ändern Sie das zur Matrixmultiplikation mit LU zerlegte Matrizen sollten Ihre Leistung drastisch erhöhen.

Dies liegt daran, dass Sie nach der Verwendung der zerlegten Matrizen den Multiplikationsalgorithmus stark optimieren können (keine sinnvolle Multiplikation von Zeilen und Spalten für die Nullelemente).

Ziehen Sie außerdem in Erwägung, zwischengespeicherte Werte zu verwenden, anstatt die Vorgänge zum Hinzufügen zu diffsumsq :

alter Code:

neuer Code:

Die zweite Variante ist dreimal schneller bei der Differenzberechnung (zwei for Zyklen - x * y Operationen werden nur einmal statt dreimal ausgeführt).

Sie können weiterhin nach der Anzahl der temporären Objekte suchen: Jede binäre Operation erstellt ein temporäres Objekt (was bedeutet, dass Sie eine andere x * y-Matrix im Speicher zuweisen und Werte kopieren). Zum Beispiel der Ausdruck:

erstellt eine temporäre für die Differenz in der ersten Paranthese, dann eine andere für die Differenz in der zweiten, dann eine andere für das Produkt.

In meinem obigen Beispiel schreibst du besser

statt

auf diese Weise vermeiden Sie die Zuweisung der temporären, die Diff (in der zweiten Variante) zugeordnet ist.

Eine andere Sache, die Sie beachten sollten, wäre Ihr Speicherverbrauch: da dieser sehr oft ausgeführt wird, könnten Sie entweder Speicher reservieren oder die verwendeten Matrizen zusammenfassen und Speicher wiederverwenden, anstatt neue Objekte zu erstellen.

Ich bin sicher, dass es noch andere Dinge zu beachten gibt.

Bearbeiten: Wie können Sie die Matrizen multiplizieren? Sie sollten sie durch Spalten x Zeilen übereinstimmen lassen. Das heißt, die Anzahl der Spalten in valA sollte der Anzahl der Zeilen in valB entsprechen (wenn ich mich an meine Matrixmultiplikationen erinnere).

Noch etwas:

  

Ich habe die Berechnungsroutine a gemacht   mehrzeiliges #define-Makro zum Erzwingen   seine Inlining und Funktion zu vermeiden   ruft auf und kehrt zurück.

Sie benötigen keine Makros zum Optimieren von C ++ - Code. Um Funktionsaufrufe und -rückgaben zu vermeiden, verwenden Sie inline d Funktionen. Makros haben ihre eigenen Probleme.