Ich muss ein Array (writeArray) mit einem anderen Array (readArray) berechnen, aber das Problem ist, dass die Index-Zuordnung zwischen Arrays nicht identisch ist (Wert am Index x von writeArray muss mit Wert am Index y von readArray berechnet werden) Es ist nicht sehr Cache freundlich.
Allerdings kann ich wählen, ob die Schleife sequenziell sequenziell readArray oder sequentiell writeArray durchsucht.
Also hier ist ein vereinfachter Code:
%Vor%Ich dachte, dass Cache-Lese-Misses langsamer war als Schreib-Fehlschläge (weil CPU warten muss, bevor das Lesen abgeschlossen ist, wenn der nächste Befehl von gelesenen Daten abhängt, aber zum Schreiben nicht auf die Verarbeitung des nächsten Befehls warten muss) Beim Profiling scheint Version 1 schneller zu sein als Version 2 (Version 2 ist ungefähr 50% langsamer als Version 1).
Ich habe es auch versucht:
%Vor%Da ich die Werte von writeArray nicht lesen muss, gibt es keinen Grund, den Cache mit geschriebenen Werten zu belasten, aber diese Version ist langsamer als andere Versionen (6700% langsamer als Version 1).
Warum schreibe Fräulein ist langsamer als Fräulein lesen? Warum ist das Umgehen des Caches zum Schreiben langsamer als die Verwendung, selbst wenn wir diese geschriebenen Daten nicht nachlesen?
Beginnen wir mit der letzten Version - was Sie getan haben ist Streaming-Speicher für nicht sequentielle (kein Stream) Zugriffsmuster. Sie greifen zufällig auf Ganzzahlen zu, was bedeutet, dass Sie partielle Schreibvorgänge (int-Größe) in vollständige Cache-Zeilen durchführen. Bei normalen Schreibvorgängen sollte dies keine Rolle spielen, da der Kern die Zeile in den Cache zieht und einfach den notwendigen Chunk modifiziert (dem später das Schreiben folgt, wenn Sie den Speicher für etwas anderes benötigen), aber da Sie ihn danach fragen vermeiden Sie Caching, Sie müssen tatsächlich diese teilweise Zusammenführung im Speicher tun, die sehr teuer ist und blockiert. Streaming-Speicher sind nur dann nützlich, wenn Sie garantiert die gesamte Zeile ändern (z. B. indem Sie das Array sequenziell durchlaufen).
Wie für die zweite Version - Ihre Annahme ist richtig, wenn es Datenabhängigkeit durch die Lasten gab, auf die Sie warten mussten, aber es gibt hier keine echte Abhängigkeitskette. Sie haben nur eine Menge von Lasten mit einer 2-Level-Abhängigkeit, aber keine gegenseitige Abhängigkeit zwischen ihnen, um eine Serialisierung über Iterationen hinweg zu verursachen (dh Iteration n == 2 und n == 3 kann auch beginnen, bevor n == 1 die erste Ladung ausgeführt wird ).
Wenn Sie davon ausgehen, dass Ihre CPU N ausstehende Zugriffe aushält (abhängig von der Größe und dem Cache-Level), starten Sie die ersten N Referenzen auf refArray parallel (vorausgesetzt die Indexberechnung ist schnell), gefolgt von den ersten N Referenzen zu readArray und dann zum nächsten Stapel und so weiter.
Jetzt, da es keine Datenabhängigkeit gibt, wird es eine Frage der Bandbreite. In diesem Fall sind die Ladevorgänge für den Prozessor in der Regel aufgrund ihrer Out-of-order-Beschaffenheit viel einfacher - Sie können sie parallel und außer Betrieb starten, sobald Sie die Adresse kennen (die nur von der schnellen Indexberechnung abhängt). . Speicher müssen andererseits in der Programmreihenfolge beobachtet werden (um die Speicherkonsistenz beizubehalten), wodurch sie fast serialisiert werden (es gibt einige mögliche CPU-Tricks, abhängig von Ihrer genauen Mikroarchitektur, aber sie werden nicht die großen verändern) Bild).
Bearbeiten: Eine weitere Einschränkung in Version 2 (die meiner Meinung nach noch kritischer ist), ist die Disambiguierung von Speichern. Der Prozessor muss die Lasten berechnen und Adressen speichern, um zu wissen, ob es eine Kollision gibt (wir wissen, dass es keine gibt, aber der Prozessor nicht ...). Wenn eine Last von einem Geschäft abhängt, muss sie gesperrt werden, falls die neuen Daten weitergeleitet werden müssen. Jetzt, da Lasten in einer OOO-Maschine früh gestartet werden, ist es wichtig, die Adressen für alle Filialen so früh wie möglich zu kennen, um Kollisionen zu vermeiden (oder schlimmer - Spekulationen, die scheitern und Massenflushes verursachen).
Tags und Links c++ performance caching cpu-cache