Design Code in CPU Cache passen?

https://stackoverflow.com/questions/1822295

10-07-2019
|

Frage

Wenn Simulationen zu schreiben mein Kumpel sagt, dass er versuchen will, das Programm klein genug, um zu schreiben, in dem Cache passen. Hat dies keine wirkliche Bedeutung? Ich verstehe, dass Cache schneller als RAM und den Hauptspeicher. Ist es möglich, festzulegen, dass Sie das Programm wollen aus dem Cache laufen oder zumindest die Variablen in dem Cache geladen werden? Wir schreiben Simulationen so dass jede Leistung / Optimierung Gewinn ein großer Vorteil ist.

Wenn Sie von irgendwelchen guten Verbindungen kennen CPU-Caching zu erklären, zeigen Sie mich dann in dieser Richtung.

Lösung

Mindestens mit einem typischen Desktop-CPU, können Sie nicht wirklich viel geben über Cache-Nutzung direkt. Sie können nach wie vor versuchen, obwohl Cache freundlichen Code zu schreiben. Auf der Code auf dieser Seite bedeutet dies oft Abrollen Schleifen (für nur ein offensichtliches Beispiel) nur selten sinnvoll ist - den Code erweitert und eine moderne CPU minimiert normalerweise den Aufwand für das Looping. Sie können auf der Datenseite im Allgemeinen nicht mehr, Referenzlokalität zu verbessern, zum Schutz gegen falsche gemeinsame Nutzung (zB zwei häufig verwendete Teile der Daten, die den gleichen Teil des Cache verwendet werden versuchen, während andere Teile ungenutzt bleiben).

Edit (um ein paar Punkte machen ein bisschen mehr explizit):

Eine typische CPU hat eine Reihe von verschiedenen Caches. Ein moderner Desktop-Prozessor hat in der Regel mindestens 2 und oft 3 Cache-Ebene. Durch die (zumindest fast) allgemeine Übereinstimmung, „Ebene 1“ ist die Cache „am nächsten“ zu den Verarbeitungselementen, und die Zahlen steigen von dort (Stufe 2 ist nächste Stufe 3 danach, usw.)

In den meisten Fällen (zumindest) die Level 1-Cache in zwei Hälften geteilt ist: eine Befehls-Cache und ein Datum-Cache (das Intel 486 ist fast die einzige Ausnahme von der mir bewusst bin, mit einem einzigen Cache für beide Befehle und Daten -. aber es ist so gründlich überholt es wahrscheinlich nicht viel Gedanken nicht verdienen)

In den meisten Fällen wird ein Cache als eine Reihe von „Linien“ organisiert. Der Inhalt eines Cache wird normalerweise gelesen, geschrieben, und eine Zeile zu einer Zeit verfolgt. Mit anderen Worten, wenn die CPU von einem beliebigen Teil eines Cache-Line-Daten verwenden wird, dass gesamte Cache-Zeile aus der nächst niedrigeren Ebene der Speicher lesen. Cache-Speicher, die näher an der CPU sind in der Regel kleiner und haben kleinere Cache-Zeilen.

Diese grundlegende Architektur führt zu den meisten der Eigenschaften eines Cache, der in dem Schreiben von Code Rolle. So viel wie möglich, sollten Sie einmal etwas in der Cache lesen, alles tun, damit Sie zu gehen, dann auf etwas anderes zu bewegen.

Dies bedeutet, dass Sie Daten verarbeiten, es ist in der Regel besser, eine relativ kleine Menge an Daten (wenig genug im Cache passen) zu lesen, tun so viel Verarbeitung dieser Daten, wie Sie können, dann auf die weitergehen nächster Teil der Daten. Algorithmen wie Quicksort, die schnell große Mengen an Eingang in progressiv kleineren Stücke tut dies mehr oder weniger automatisch brechen, so dass sie neigen dazu, ziemlich Cache-freundlich, fast unabhängig von den genauen Details des Cache zu sein.

Dies hat auch Auswirkungen darauf, wie Sie Code schreiben. Wenn Sie eine Schleife wie:

for i = 0 to whatever
   step1(data);
   step2(data);
   step3(data);
end for

Sie sind im Allgemeinen besser als viele der Schritte Aneinanderreihung, wie Sie können bis zur Höhe , die im Cache passen. Die Minute, die Sie den Cache-Überlauf, Leistung kann / wird drastisch sinken. Wenn der Code für Schritt über 3 groß genug ist, dass es nicht in den Cache passen würde, würden Sie in der Regel besser dran, die Schleife in zwei Stücke wie diese zu brechen (wenn möglich):

for i = 0 to whatever
    step1(data);
    step2(data);
end for

for i = 0 to whatever
    step3(data);
end for

Schleifenentrollen ist ein ziemlich heiß umkämpften Thema. Auf der einen Seite ist es können führen zu Code, der viel mehr CPU-freundlich ist, reduziert den Aufwand von Anweisungen für die Schleife selbst ausgeführt. Zur gleichen Zeit, kann es (und in der Regel der Fall ist) erhöhen Codegröße, es ist also relativ Cache unfreundlich. Meine eigene Erfahrung ist, dass in synthetischem Benchmarks, die wirklich kleine Mengen an Verarbeitung auf wirklich großen Datenmengen zu tun, neigen dazu, dass Sie eine Menge von Schleifenentrollen zu gewinnen. In praktischem Code, wo Sie sind in der Regel der Verarbeitung auf einem einzelnes Stück von Daten haben, gewinnen Sie viel weniger - und zu einem ernsthaften Leistungsverlust die Cache überquell führt, ist überhaupt nicht besonders selten

Der Daten-Cache ist auch in der Größe begrenzt. Dies bedeutet, dass Sie in der Regel Ihre Daten gepackt wollen so dicht wie möglich, um so viele Daten wie möglich im Cache passen. Nur für ein offensichtliches Beispiel, eine Datenstruktur, die zusammen mit Zeigern verknüpft ist braucht ziemlich viel in Bezug auf die Rechenkomplexität zu gewinnen fo zu bildenr die Anzahl der Daten-Cache-Raum, der durch diesen Zeiger verwendet. Wenn Sie eine verknüpfte Datenstruktur verwenden werden, möchten Sie in der Regel zumindest um sicherzustellen, sind Sie miteinander verbindet relativ große Stücke von Daten.

In vielen Fällen jedoch habe ich festgestellt, dass Tricks, die ich ursprünglich für den Einbau von Daten in winzigen Mengen an Speicher in winzigen Prozessoren gelernt, die gewesen sind (meist) veraltet seit Jahrzehnten arbeitet auf modernen Prozessoren ziemlich gut aus. Die Absicht ist es nun mehr Daten im Cache anstelle des Hauptspeichers zu passen, aber der Effekt ist fast das gleiche. In ganz wenigen Fällen können Sie von CPU-Instruktionen denken als nahezu frei, und die Gesamtgeschwindigkeit der Ausführung wird durch die Bandbreite auf den Cache (oder den Hauptspeicher), so zusätzliche Verarbeitung auspacken Daten aus einem dichten Format ausarbeitet regiert in dein Gefallen. Dies gilt insbesondere, wenn Sie mit genügend Daten zu tun hat, dass es nicht alle in dem Cache passen überhaupt nicht mehr, so dass die Gesamtgeschwindigkeit durch die Bandbreite in dem Hauptspeicher geregelt. In diesem Fall können Sie ein Los von Anweisungen ausführen ein paar Speicher speichern lesen, und immer noch kommen voran.

Die Parallelverarbeitung kann dieses Problem noch verschärfen. In vielen Fällen Code umschreiben kann, damit eine parallele Verarbeitung zu praktisch keinen Gewinn in der Leistung führen, oder manchmal sogar ein Performance-Verlust. Wenn die Gesamtgeschwindigkeit durch die Bandbreite von der CPU auf dem Speicher verwaltet wird, mehr Kern für diese Bandbreite im Wettbewerb ist unwahrscheinlich, etwas Gutes zu tun (und kann erheblichen Schaden anrichten). Verwendung mehrerer Kerne in einem solchen Fall zur Verbesserung der Geschwindigkeit oft kommt unten noch mehr zu tun, die Daten dichter zu packen, und unter Ausnutzung von noch mehr Rechenleistung, die Daten zu entpacken, so dass die tatsächliche Geschwindigkeit Verstärkung ist von der Reduzierung der Bandbreite verbraucht und die zusätzlichen Kerne nur aus halter Zeit Auspacken die Daten aus dem dichteren Format zu verlieren.

Ein weiteres Cache-basiertes Problem, das parallel Codierung auftreten können teilt (und False Sharing) von Variablen. Wenn zwei (oder mehr) Kerne der gleichen Stelle im Speicher schreiben müssen, das Halten der Cache-Zeile, die Daten am Ende kann hin und her zwischen den Kernen pendelte jeden Kern Zugriff auf die gemeinsam genutzten Daten zu geben. Das Ergebnis ist oft Code, der parallel läuft langsamer als es in seriellem tat (d.h. auf einem einzigen Kern). Es gibt eine Variation dieses „False Sharing“ genannt wird, in dem der Code auf den verschiedenen Kernen wird das Schreiben von Daten zu trennen, und die Daten für die verschiedenen Kerne enden in der gleichen Cache-Zeile nach oben. Da die Cache-Kontrollen Daten rein in Bezug auf den gesamten Datenzeilen, werden die Daten gemischt hin und her zwischen den Kernen ohnehin, was zu genau dem gleichen Problem.

Andere Tipps

Hier ist ein Link zu einem wirklich guten Papier auf Caches rel="nofollow / Speicheroptimierung von Christer Ericsson (von God of War I / II / III Ruhm). Es ist ein paar Jahre alt, aber es ist immer noch sehr relevant.

Ein nützliches Papier, das Sie mehr erzählen, als Sie jemals über Caches wissen wollte, ist Was jeder Programmierer wissen sollten über Speicher von Ulrich Drepper. Hennessey deckt es sehr gründlich. Christer und Mike Acton haben ein paar gute Sachen darüber zu geschrieben.

Ich glaube, Sie mehr über Daten-Cache als Befehls-Cache sorgen sollte - nach meiner Erfahrung, dCache Misses sind häufiger, schmerzhafter und nützlicher fixiert.

UPDATE: 2014.01.13 Gemäß dieser älteren Chip-Designer sind jetzt Cache-Misses Die überwältigend dominierende Faktor in der Codeleistung, so dass wir im Grunde den ganzen Weg zurück in die Mitte der 80er Jahre und schnell 286 Chips in Bezug auf die relative Performance-Engpässe der Last, zu speichern, integer Arithmetik und Cache-Misses.

ein Crash-Kurs in der modernen Hardware von Cliff Klicken @ Azul . . . . .

--- wir jetzt kehren Sie zurück zu Ihrem regelmäßigen Programm ---

Manchmal ein Beispiel ist besser als eine Beschreibung, wie etwas zu tun. In diesem Sinne ist hier ein besonders erfolgreiches Beispiel dafür, wie ich einige Codes geändert, um besser auf Chip-Caches zu verwenden. Dies wurde vor einiger Zeit getan auf einem 486-CPU und diese mit einem 1. Generation Pentium CPU migriert. Die Auswirkungen auf die Leistung war ähnlich.

Beispiel: Subscript Mapping

Hier ist ein Beispiel für eine Technik, die ich Daten passen verwendet, um in die Cache des Chips, Allzweck-Dienstprogramm hat.

Ich hatte einen Doppel Schwimmer Vektor, die 1250 Elemente lang war, die eine Epidemiologie Kurve mit sehr langen Schwänzen war. Der „interessant“ Teil der Kurve hatte nur etwa 200 eindeutigen Wert, aber ich habe keine 2-seitig if () Test ein Chaos von der CPU-Pipeline (und damit den langen Schwanz machen will, die als die Indizes nutzen, um die extremsten Werte der Code Monte Carlo ausspucken würde), und ich brauchte im Code die Verzweigungsvorhersagelogik für ein Dutzend andere bedingte Tests innerhalb des „Hot-Spot“.

ich auf einem Schema angesiedelt, wo ich als Index in den Doppel-Vektor einen Vektor von 8-Bit-Ints verwendet, die ich auf 256 Elemente verkürzt. Die winzigen Ints hatten alle die gleichen Werte vor 128 vor Null und 128 nach Null, so mit Ausnahme der Mitte 256 Werte, sie alle zu spitz entweder der erste oder der letzte Wert im Doppelvektor.

Dies geschrumpft den Speicherbedarf für die Doppel bis 2k und 1250 Byte für die 8-Bit-Indizes. Diese geschrumpft 10.000 Bytes bis 3298. Da das Programm 90% ausgegeben oder mehr davon die Zeit in dieser inneren Schleife ist, die zwei Vektoren wurden nie aus dem 8k-Daten-Cache geschoben. Das Programm verdoppelt sofort seine Leistung. Dieser Code wurde getroffen ~ 100 Milliarden mal im Prozess für 1+ Millionen Hypothekendarlehen einen OAS Wert berechnet wird.

Da der Schwanz der Kurve selten berührt wurde, ist es durchaus möglich, dass nur die mittleren 200-300 Elemente des winzigen int-Vektor wurden tatsächlich im Cache gehalten, zusammen mit 160-240 Mitte verdoppelt repräsentiert 1 / 8ths von Prozent von Interesse . Es war eine bemerkenswerte Leistungssteigerung, an einem Nachmittag durchgeführt, auf einem Programm, das ich über ein Jahr Optimierung verbracht habe.

ich mit Jerry einverstanden ist, wie es auch meine Erfahrung gewesen, dass der Code auf der Befehls-Cache Kippen nicht annähernd so erfolgreich ist wie die Optimierung für die Daten-Cache / s. Dies ist ein Grund denke ich, AMDs gemeinsame Caches sind nicht so hilfreich wie Intel separater Daten- und Befehls-Cache-Speicher. IE: Sie wollen nicht, Anweisungen, um den Cache hogging up, wie es ist einfach nicht sehr hilfreich. Zum Teil ist dies, weil CISC-Befehlssätze ursprünglich für die große Differenz erzeugt wurden zwischen CPU und Speichergeschwindigkeiten zu bilden, und mit Ausnahme einer Aberration in den späten 80er Jahren, das ist so ziemlich immer wahr gewesen.

Eine weitere bevorzugte Technik verwende ich den Datencache, zu begünstigen und den Befehls-Cache Savage, ist durch eine Menge von Bit-Ints in Strukturdefinitionen verwenden und die kleinstmögliche Datengrößen im Allgemeinen. ein 4-Bit-int zu maskieren den Monat des Jahres, oder 9 Bits zu halten, den Tag des Jahres zu halten, etc, etc, benötigt die CPU-Nutzung Masken die Host-Zahlen die Bits verwenden, die die schrumpft zu maskieren Daten, erhöht effektiv Cache und Busgrößen, aber mehr Anweisungen erfordert. Während diese Technik erzeugt Code, der nicht auch auf synthetische Benchmarks nicht durchführt, auf stark befahrenen Systemen, in denen die Verwendungrs und Prozesse für Ressourcen konkurrieren, es funktioniert wunderbar.

Meist wird dies als Platzhalter dienen, bis ich Zeit habe dieses Thema gerecht zu werden, aber ich wollte teilen, was ich für eine wirklich bahnbrechenden Meilenstein sein - die Einführung von speziellen Bit-Manipulationsanweisungen in dem neuen Intel Hazwell Mikroprozessor.

Es wurde schmerzlich klar, als ich einige Codes hier auf Stackoverflow schrieb die Bits in einem 4096-Bit-Array zu ändern, dass mehr als 30 Jahre nach der Einführung des PCs, Mikroprozessoren einfach nicht viel Aufmerksamkeit und Ressourcen auf Bits widmen, und dass ich hoffe, dass wird sich ändern. Insbesondere würde ich für den Anfang, um zu sehen, die Liebe, der Bool Typ ein tatsächliches Bitdatentyp in C / C ++, anstelle der lächerlich verschwenderisch Byte es zur Zeit worden ist.

Hazwell die neuen Bit Manipulation Anweisungen

UPDATE: 2013.12.29

ich Gelegenheit hatte vor kurzem einen Ringpuffer zu optimieren, die in Millisekunden Granularität Spur von 512 unterschiedlichen Ressourcennutzer Anforderungen an ein System hält. Es gibt einen Timer, der jede Millisekunde ausgelöst, die die Summe der aktuellen Scheibe der Ressourcenanforderungen addiert und subtrahiert aus dem 1000. Anfragen der Zeitscheibe, mit Ressourcenanforderungen jetzt 1.000 Millisekunden alt.

Der Kopf, Schwanz Vektoren war direkt nebeneinander im Speicher, außer wenn zuerst den Kopf, und dann der Schwanz gewickelt und begann am Anfang des Feldes zurück. Die (Rollen) Zusammenfassung Scheibe war jedoch in einem festen, statisch zugewiesenen Array, das nicht besonders nahe an eine der beiden war, und wurde auch nicht von der Halde zugeordnet.

über das Denken, und studieren Sie den Code ein paar Angaben meine Aufmerksamkeit erregt.

Die Anforderungen, die in wurden in benachbarten Zeilen Code zueinander an den Leiter und die Zusammenfassung Scheibe zur gleichen Zeit, direkt neben hinzugefügt kamen.
Wenn der Timer abgefeuert wurde der Schwanz aus der Zusammenfassung Scheibe abgezogen, und die Ergebnisse wurden in der Zusammenfassung Scheibe links, wie man erwarten würde
Die zweite Funktion aufgerufen, wenn der Timer erweiterte alle Zeiger Wartung des Ring gebrannt. Speziell.... Der Leiter überschrieben den Schwanz, wodurch die gleiche Speicherstelle zu besetzen Der neue Heck belegt die nächsten 512 Speicherplätze oder gewickelt
Der Anwender mehr Flexibilität bei der Anzahl der Forderungen werden verwaltet wollte, 512-4098, oder vielleicht mehr. Ich spürte die robusteste, idiotensicher Weg, dies zu tun war, sowohl die 1000 Zeitscheiben und die Zusammenfassung Scheibe als alle zusammen zusammenhängenden Block von Speicher zuzuordnen, so dass es unmöglich wäre, für die Zusammenfassung Scheibe am Ende eine andere Länge ist bis als die anderen 1.000 Zeitscheiben.
Das führt zu dem, begann ich zu fragen, ob ich, wenn mehr Leistung bekommen könnte, anstatt die Zusammenfassung Scheibe mit an einem Ort bleiben, musste ich es „Roam“ zwischen dem Kopf und dem Schwanz, so war es immer direkt neben den Kopf für neue Anforderungen hinzufügen und direkt neben den Schwanz, wenn der Timer gefeuert und die Werte des Schwanzes hatten von der Zusammenfassung abgezogen werden.

Ich habe genau dieses, aber dann ein paar zusätzliche Optimierungen im Prozess gefunden. Ich änderte den Code, den die Roll Zusammenfassung berechnet, so dass es die Ergebnisse im Heck links, anstelle der Zusammenfassung in Scheiben schneiden. Warum? Da die nächste Funktion wurde eine memcpy () Durchführen der Zusammenfassung Scheibe in den Speicher durch den Schweif nur besetzt zu bewegen. (Komisch, aber wahr ist, führt der Schwanz mit dem Kopf bis zum Ende des Rings, wenn es wickelt). Durch Weglassen der Ergebnisse der Summierung im Schwanz, musste ich nicht die memcpy () durchführt, musste ich einfach PTAIL zu pSummary zuweisen.

In ähnlicher Weise belegte der neue Leiter der jetzt abgestanden Zusammenfassung Scheibe alten Speicherplatz, so wieder, ich habe gerade pSummary zu pHead zugewiesen, und auf Null gesetzt, alle ihre Werte mit einem memset auf Null zurück.

Den Weg bis zum Ende des Rings (wirklich eine Trommel, 512 Spuren breit) war der Schwanz, aber ich hatte nur zuVergleichen seines Zeigers gegen einen konstanten pEndOfRing Zeiger auf diesen Zustand zu erkennen. Alle anderen Zeiger könnte den Zeigerwert des Vektors nur vor ihm zugewiesen werden. IE: Ich brauchte nur einen bedingten Test für 1: 3 der Zeiger richtig um sie zu wickeln.

Der ursprüngliche Entwurf Byte Ints verwendet hatte Cache-Nutzung zu maximieren, jedoch konnte ich diese Einschränkung entspannen - Befriedigung der Benutzer pro Millisekunde pro Benutzer höhere Ressourcen zählt behandeln fordern - unsigned Shorts zu verwenden und STILL doppelte Leistung , denn auch mit 3 benachbarten Vektoren von 512 unsigned Shorts, die 32K-Datencache der L1-Cache leicht die erforderlichen 3.720 Bytes halten können, 2 / 3rds die an Orten waren nur verwendet. Erst wenn der Schwanz, Zusammenfassung oder gewickelte Kopf war 1 die 3 getrennt von einem signifikanten „Schritt“ in der 8MB L3cache.

Der Gesamtlaufzeit-Speicherplatzbedarf für diesen Code unter 2MB ist, so läuft es ganz aus On-Chip-Cache-Speicher, und sogar auf einem i7-Chip mit 4 Kernen, 4-Instanzen dieses Prozesses können ohne Verschlechterung ausgeführt werden in Leistung überhaupt, und der Gesamtdurchsatz steigt leicht mit 5 Prozesse laufen. Es ist ein Opus Magnum auf Cache-Nutzung.

Die meisten C / C ++ Compiler bevorzugt für Größe zu optimieren, anstatt für „Geschwindigkeit“. Das heißt, kleinerer Code ausführt Regel schneller als abgerollt Code, da der Cache-Effekte.

Wenn ich Sie wäre, würde ich sicherstellen, dass ich wissen, welche Teile des Codes sind Hotspots, die ich als

definieren

eine enge Schleife keine Funktionsaufrufe enthalten, denn wenn es irgendeine Funktion aufruft, dann wird der PC die meiste Zeit in dieser Funktion verbringen,
, die für einen signifikanten Anteil der Ausführungszeit-Konten (wie> = 10%), die Sie von einem Profiler bestimmen können. (I Probe nur den Stapel manuell).

Wenn Sie einen solchen Hotspot haben, dann sollte es in den Cache passen. Ich bin mir nicht sicher, wie Sie es sagen, das zu tun, aber ich vermute, es ist automatisch.

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow