Ich arbeite an einer Hausaufgabe und habe stundenlang an meiner Lösung festgemacht. Das Problem, das wir bekommen haben, ist, den folgenden Code zu optimieren, so dass er schneller läuft, egal wie unordentlich er wird. Wir sollten Dinge wie das Ausnutzen von Cache-Blöcken und Schleifen-Abrollung verwenden.
Problem:
%Vor%Was ich bisher habe:
%Vor%Einige Ideen, bitte korrigieren Sie mich, wenn ich falsch liege:
Ich habe über Loop-Abrollung nachgedacht, aber ich denke nicht, dass das helfen würde, weil wir nicht wissen, ob die NxN-Matrix Primzahlen hat oder nicht. Wenn ich das überprüfen würde, würde das zu viele Berechnungen enthalten, die die Funktion verlangsamen würden.
Cache-Blöcke wären nicht sehr nützlich, denn egal, was wir tun, wir werden linear auf ein Array zugreifen (1,2,3,4), während wir auf das andere in Sprüngen von N zugreifen werden Funktion, um den Cache zu missbrauchen und schneller auf den src-Block zuzugreifen, es wird noch lange dauern, diese in die dst-Matrix zu plazieren.
Ich habe auch versucht, Zeiger anstelle von Array-Zugriffsmethoden zu verwenden, aber ich glaube nicht, dass das Programm tatsächlich in irgendeiner Weise beschleunigt.
Jede Hilfe würde sehr geschätzt werden.
Danke
Cache-Blockierung kann nützlich sein. Nehmen wir zum Beispiel an, dass wir eine Cache-Zeilengröße von 64 Bytes haben (was x86 an diesen Tagen verwendet). Für eine Matrix, die groß genug ist, um größer zu sein als die Cachegröße, passen wir also, wenn wir einen 16x16-Block transponieren (seit sizeof (int) == 4, also 16 ints in eine Cachezeile) ) Wir müssen 32 laden (16 von der Quellmatrix, 16 von der Zielmatrix, bevor wir sie verschmutzen können), Zeilen aus dem Speicher zwischenspeichern und weitere 16 Zeilen speichern (auch wenn die Speicher nicht sequentiell sind). Im Gegensatz dazu erfordert das Transponieren der äquivalenten 16 · 16 Elemente ohne Cachespeicherblock das Laden von 16 Cachezeilen aus der Quellenmatrix, aber 16 · 16 = 256 Cachezeilen, die geladen und dann für die Zielmatrix gespeichert werden.
Das Abrollen ist nützlich für große Matrizen.
Sie benötigen etwas Code, um mit überschüssigen Elementen umzugehen, wenn die Matrixgröße nicht ein Vielfaches der Zeiten ist, die Sie ausrollen. Aber dies wird außerhalb der kritischsten Schleife sein, so dass es sich für eine große Matrix lohnt.
In Bezug auf die Richtung der Zugriffe - es kann besser sein, linear zu lesen und in Sprüngen von N zu schreiben, als umgekehrt. Dies liegt daran, dass Leseoperationen die CPU blockieren, während Schreiboperationen dies nicht tun (bis zu einem bestimmten Grenzwert).
Weitere Vorschläge:
1. Können Sie die Parallelisierung verwenden? OpenMP kann helfen (obwohl, wenn Sie erwartet werden, Single-CPU-Leistung zu liefern, ist es nicht gut).
2. Zerlegen Sie die Funktion und lesen Sie sie, wobei Sie sich auf die innerste Schleife konzentrieren. Sie können Dinge finden, die Sie im C-Code nicht bemerken würden.
3. Das Verwenden von absteigenden Zählern (Anhalten bei 0) ist möglicherweise etwas effizienter als das Erhöhen von Zählern.
4. Der Compiler muss davon ausgehen, dass src und dst Aliasnamen haben (auf denselben oder überlappenden Speicher zeigen), was seine Optimierungsmöglichkeiten einschränkt. Wenn Sie dem Compiler irgendwie sagen könnten, dass sie sich nicht überschneiden können, könnte das eine große Hilfe sein. Ich bin mir jedoch nicht sicher, wie das geht (vielleicht verwende ich den restrict Qualifier).
Unordnung ist kein Problem, also: Ich würde jeder Matrix eine transposed -Flag hinzufügen. Dieses Flag zeigt an, ob das gespeicherte Datenfeld einer Matrix in normaler oder transponierter Reihenfolge interpretiert werden soll.
Alle Matrixoperationen sollten diese neuen Flags zusätzlich zu jedem Matrixparameter erhalten. Innerhalb jeder Operation implementieren Sie den Code für alle möglichen Kombinationen von Flags. Vielleicht können Makros hier überflüssiges Schreiben sparen.
In dieser neuen Implementierung schaltet die Matrixtransposition einfach das Flag um: Der für die Transponieroperation benötigte Raum und die Zeit sind konstant.
Tags und Links optimization c loops caching matrix