Techniken zur Erhaltung der Daten im cache, Lokalität?
Für eine ultra-schnelle code ist es wichtig, dass wir halten die Lokalität der Referenz - halten, wie viel von den Daten, die eng zusammen verwendet, in der CPU-cache:
http://en.wikipedia.org/wiki/Locality_of_reference
Was sind die Techniken, dies zu erreichen? Könnte Leute geben Beispiele?
Ich daran interessiert Java und C/C++ - Beispiele. Interessant zu wissen, von Möglichkeiten, die Menschen benutzen, um zu stoppen viel cache tauschen.
Grüße
- Sehen Sie diese Sprache unabhängige Frage Wie schreibt man code, der am besten nutzt den CPU-cache, um die Leistung zu verbessern
- Sie nähern kann es von zwei Seiten: das Mischen der Daten im Speicher, ist ein Ansatz, mischen der Verarbeitung in der Zeit ist eine andere.
- aber setzen 0.5 MB Daten in den RAM nicht garantieren, es wird alles in den cache an der gleichen Zeit?
- Gut es könnten auch andere Prozesse, die auf andere CPU-Kerne, die im Wettbewerb für den cache. Aber wenn die CPU-cache ist groß genug für Sie und die anderen Prozesse, dann die 512 kB werden im cache. Um Sie im RAM, die CPU durch den cache, und da wir vermuteten, dass eine große-genug-cache der cache nicht verwerfen die Daten.
- Wenn die Leute reden über die Lokalität, die größte Sorge ist, zu helfen, den Prozessor laden Sie den cache, wie der Prozess ausgeführt wird. Das ist, das problem zu lösen ist, was passiert, wenn der Speicher eigentlich nicht in den cache (einen anderen Prozess wurde ausgeführt, es passt nicht in Ihre L1, L2 oder L3-cache... Wenn die Datenmenge sehr klein ist, können Sie davon ausgehen, dass es in den cache, und erwarten Sie nicht zu viele Probleme haben (Hinweis: nehmen Sie an, und viele sind nicht garantiert).
- also für SEHR schnelle Finanz-software, die Sie neu schreiben den Linux-OS, weil jeder einzelne OS-Prozess auftreten, die im hintergrund könnte potential kick aus der wertvollen Algorithmus Daten aus dem cache, und ersetzen Sie es mit.... <eine kleine Linux-OS Prozess Stück von Daten>?
- Ich weiß nicht, wo Sie zu diesem Schluss gekommen aus... ich war noch nie auf den Handel, aber im Allgemeinen, wenn Sie haben ein Gerät, wo Sie brauchen Leistung, die Sie zwicken die OS. In meinem vorherigen Projekt, der kernel-scheduler wurde überarbeitet, und die box war sehr begrenzt, Dinge, die installiert und ausgeführt werden. Die Kernprozesse wurden an einen bestimmten Prozessor mit einer hohen Priorität, so dass einige spezifische Kerne frei zu gewinnen für andere Prozesse.
Schreibe einen Kommentar
Du musst angemeldet sein, um einen Kommentar abzugeben.
Dies ist wahrscheinlich zu allgemein, um klare Antwort. Die Ansätze, die in C oder C++ im Vergleich zu Java unterscheiden sich durchaus ein bisschen (die Art, die Sprache, legt die Objekte unterscheiden).
Die grundlegende wäre, halten die Daten, die Zugriff in engen Schleifen zusammen. Wenn deine Schleife arbeitet auf Typ T, und es hat Mitglieder m1...mN, aber nur m1...m4 sind in dem kritischen Pfad, empfiehlt sich die Aufteilung von T in T1, enthält m1...m4 und T2 enthält m4...mN. Möglicherweise möchten Sie auch zu T1 einen Zeiger, bezieht sich das auf T2. Versuchen Sie zu vermeiden Objekte, die nicht mit Bezug auf cache-Grenzen (sehr Plattform abhängig).
Zusammenhängender Container (plain old array in C, vector in C++) und versuchen, zu verwalten, Iterationen, um nach oben oder unten gehen, aber nicht zufällig, springen alle auf den container. Verknüpfte Listen sind Killer für die Lokalität, die zwei aufeinander folgende Knoten in einer Liste mit möglicherweise völlig anderen zufällig ausgewählten Standorten.
Objekt-Container (und generics) in Java sind auch ein killer, während Sie in einem Vektor der Verweise sind zusammenhängende, die eigentlichen Objekte werden nicht (es ist eine zusätzliche Ebene der Dereferenzierung). In Java gibt es eine Menge von zusätzlichen Variablen (wenn Sie
newzwei Objekte, eines nach dem anderen, die Objekte werden wahrscheinlich am Ende in fast zusammenhängende Speicherbereiche, auch wenn es einige zusätzliche Informationen (in der Regel zwei oder drei Zeiger) der Object management Daten zwischen. GC Objekte verschieben, aber hoffentlich nicht mehr machen Dinge viel schlimmer aus als es war, bevor es ausgeführt wird.Wenn man sich konzentriert, in Java erstellen, kompakte Datenstrukturen, wenn Sie haben ein Objekt, das eine position hat, und das ist, auf die zugegriffen werden, die in einer engen Schleife, prüfen, halten ein
xundyprimitiven Typen in Ihrem Objekt, anstatt einPointund hält eine Referenz darauf. Referenztypen werden müssen, newed, und das bedeutet, dass eine andere Aufteilung, eine zusätzliche Dereferenzierung und weniger Lokalität.Zwei gemeinsame Techniken sind:
Beispiel für Minimalismus: In ray tracing (3d-Grafik-rendering-Paradigma), ist es, einen gemeinsamen Ansatz zu verwenden 8 byte Kd-Bäume zum speichern von statischen Daten einer Szene. Die traversal Algorithmus passt in nur ein paar Zeilen code. Dann, die Kd-Baum wird oft zusammengestellt in einer Weise, die minimalizes die Anzahl der traversal-Schritten durch große, leere Knoten auf der Spitze des Baumes ("Surface Area Heuristics" von Havran).
Mispredictions haben in der Regel eine Wahrscheinlichkeit von 50%, aber das sind geringe Kosten, weil wirklich viele Knoten passen in eine cache-line (beachten Sie, dass Sie erhalten, 128 Knoten pro Kb!), und einer der beiden Kind-Knoten ist immer ein direkter Nachbar in Erinnerung.
Beispiel für cache-oblivious-Verfahren: Morton array-Indizierung, auch bekannt als Z-order-Kurve indizieren. Diese Art der Indizierung kann bevorzugt werden, wenn Sie in der Regel auf in der Nähe von array-Elementen in unvorhersehbare Richtung. Dies kann wertvoll sein für die große Bild-oder voxel-Daten, wo Sie haben könnte, 32 oder sogar 64 Byte großen Pixel, und dann Millionen von Ihnen (typische Kompaktkamera Messen Megapixel, richtig?) oder sogar Tausende von Milliarden für wissenschaftliche Simulationen.
Jedoch beide Techniken haben eine Sache gemeinsam: Halten Sie die am häufigsten zugegriffen Zeug in der Nähe, die weniger Häufig Dinge weiter Weg, spannt sich die ganze Bandbreite der L1-cache über Hauptspeicher auf die Festplatte, dann die anderen Rechner im gleichen Raum, weiter Raum, gleiche Land, weltweit, auch andere Planeten.
Einige zufällige tricks, die mir einfallen, und einige von Ihnen, die ich zuletzt verwendet:
Überdenken Sie Ihren Algorithmus. Für Beispiel haben Sie ein Bild mit einer Form und die Verarbeitung Algorithmus, der sieht für die Ecken der Form. Anstelle der Betrieb auf die image-Daten können Sie direkt Vorverarbeiten, speichern Sie alle die Form der pixel-Koordinaten in einer Liste und arbeiten Sie dann auf der Liste. Vermeiden Sie zufällig die springen, um das Bild
Schrumpfen Datentypen. Regelmäßige
intdauert 4 bytes, und wenn es Ihnen gelingt, z.B.uint16_tSie cache 2x mehr ZeugManchmal können Sie bitmaps, habe ich es für die Verarbeitung eines binären Bildes. Ich gespeicherten pixel pro bit), so dass ich passen könnte 8*32 Pixel in einer einzelnen cache-Zeile. Es wirklich verstärkt die Leistung
Form von Java, die Sie verwenden können, JNI (ist nicht schwer) und die Implementierung Ihre kritischen code in C zur Steuerung der Speicher
In der Java-Welt der JIT wird hart arbeiten, um dies zu erreichen, und versuchen, auf den zweiten denke, das ist wahrscheinlich kontraproduktiv. Diese Frage ALSO - Adressen Java-spezifische Probleme mehr voll.