Referenzort - Locality of reference

In der Informatik ist die Lokalität der Referenz , auch als Lokalitätsprinzip bekannt , die Tendenz eines Prozessors, über einen kurzen Zeitraum wiederholt auf denselben Satz von Speicherplätzen zuzugreifen. Es gibt zwei grundlegende Arten von Referenzlokalitäten – die zeitliche und die räumliche Lokalität. Zeitliche Lokalität bezieht sich auf die Wiederverwendung bestimmter Daten und/oder Ressourcen innerhalb einer relativ kurzen Zeitdauer. Räumliche Lokalität (auch als Datenlokalität bezeichnet ) bezieht sich auf die Verwendung von Datenelementen innerhalb relativ naher Speicherorte. Sequentielle Lokalität, ein Spezialfall der räumlichen Lokalität, tritt auf, wenn Datenelemente angeordnet sind und linear auf sie zugegriffen wird, wie zum Beispiel beim Durchlaufen der Elemente in einem eindimensionalen Array .

Lokalität ist eine Art von vorhersagbarem Verhalten, das in Computersystemen auftritt. Systeme, die eine starke Referenzlokalität aufweisen, sind großartige Kandidaten für die Leistungsoptimierung durch die Verwendung von Techniken wie Caching , Prefetching für Speicher und fortschrittliche Verzweigungsprädiktoren in der Pipeline- Phase eines Prozessorkerns.

Arten von Orten

Es gibt verschiedene Arten von Referenzorten:

  • Zeitliche Lokalität : Wenn an einem Punkt auf eine bestimmte Speicherstelle verwiesen wird, dann ist es wahrscheinlich, dass dieselbe Stelle in naher Zukunft erneut referenziert wird. Es besteht eine zeitliche Nähe zwischen benachbarten Referenzen auf denselben Speicherplatz. In diesem Fall ist es üblich, Anstrengungen zu unternehmen, eine Kopie der referenzierten Daten in einem schnelleren Speicher zu speichern, um die Latenzzeit nachfolgender Referenzen zu reduzieren. Die zeitliche Lokalität ist ein Sonderfall der räumlichen Lokalität (siehe unten), nämlich wenn der voraussichtliche Standort mit dem aktuellen Standort identisch ist.
  • Räumliche Lokalität : Wenn zu einer bestimmten Zeit auf einen bestimmten Speicherort verwiesen wird, ist es wahrscheinlich, dass in naher Zukunft auf nahegelegene Speicherorte verwiesen wird. In diesem Fall wird häufig versucht, die Größe und Form des Bereichs um die aktuelle Referenz herum zu erraten, für den es sich lohnt, einen schnelleren Zugriff für eine spätere Referenz vorzubereiten.
    • Speicherlokalität (oder Datenlokalität ): Räumliche Lokalität, die sich explizit auf den Speicher bezieht .
  • Zweig Lokalität : Wenn es nur wenig möglichen Alternativen für den prospektiven Teil des Weges in dem räumlich-zeitlichen Raum koordinieren. Dies ist der Fall, wenn eine Befehlsschleife eine einfache Struktur hat oder das mögliche Ergebnis eines kleinen Systems von bedingten Verzweigungsbefehlen auf eine kleine Menge von Möglichkeiten beschränkt ist. Zweiglokalität ist typischerweise keine räumliche Lokalität, da die wenigen Möglichkeiten weit voneinander entfernt liegen können.
  • Äquidistante Lokalität : Auf halbem Weg zwischen räumlicher Lokalität und Zweiglokalität. Betrachten Sie eine Schleife, die auf Orte in einem äquidistanten Muster zugreift, dh der Pfad im räumlich-zeitlichen Koordinatenraum ist eine gepunktete Linie. In diesem Fall kann eine einfache lineare Funktion vorhersagen, auf welchen Ort in naher Zukunft zugegriffen wird.

Um von der häufig vorkommenden zeitlichen und räumlichen Lokalität zu profitieren, sind die meisten Informationsspeichersysteme hierarchisch . Die äquidistante Lokalität wird normalerweise durch die diversen nichttrivialen Inkrementierungsbefehle eines Prozessors unterstützt. Für die Verzweigungslokalität verfügen die heutigen Prozessoren über ausgeklügelte Verzweigungsprädiktoren, und auf der Grundlage dieser Vorhersage versucht der Speichermanager des Prozessors, die Daten plausibler Alternativen zu sammeln und vorzuverarbeiten.

Relevanz

Die Lokalität hat mehrere Gründe. Diese Gründe sind je nach Aspekt entweder zu erreichende Ziele oder zu akzeptierende Umstände. Die folgenden Gründe sind nicht zusammenhangslos ; Tatsächlich geht die folgende Liste vom allgemeinsten Fall zu Spezialfällen:

  • Vorhersagbarkeit : Lokalität ist nur eine Art vorhersagbares Verhalten in Computersystemen.
  • Struktur des Programms : Lokalität tritt häufig aufgrund der Art und Weise auf, in der Computerprogramme erstellt werden, um entscheidbare Probleme zu behandeln. Im Allgemeinen werden zugehörige Daten an nahegelegenen Speicherorten gespeichert. Ein gängiges Muster in der Datenverarbeitung beinhaltet die Verarbeitung mehrerer Elemente nacheinander. Dies bedeutet, dass bei vielen Bearbeitungen auf das einzelne Element mehr als einmal zugegriffen wird, was zu einer zeitlichen Referenzlokalität führt. Darüber hinaus impliziert das Verschieben zum nächsten Element, dass das nächste Element gelesen wird, daher die räumliche Referenzlokalität, da Speicherorte typischerweise in Stapeln gelesen werden.
  • Lineare Datenstrukturen : Lokalität tritt häufig auf, weil Code Schleifen enthält, die dazu neigen, Arrays oder andere Datenstrukturen durch Indizes zu referenzieren. Sequentielle Lokalität, ein Sonderfall der räumlichen Lokalität, tritt auf, wenn relevante Datenelemente linear angeordnet und darauf zugegriffen werden. Zum Beispiel würde das einfache Durchlaufen von Elementen in einem eindimensionalen Array von der Basisadresse zum höchsten Element die sequentielle Lokalität des Arrays im Speicher ausnutzen. Eine äquidistante Lokalität tritt auf, wenn die lineare Durchquerung über einen längeren Bereich benachbarter Datenstrukturen mit identischer Struktur und Größe erfolgt, wobei auf wechselseitig entsprechende Elemente jeder Struktur anstatt auf jede gesamte Struktur zugegriffen wird. Dies ist der Fall, wenn eine Matrix als sequentielle Matrix von Zeilen dargestellt wird und der Zugriff auf eine einzelne Spalte der Matrix erforderlich ist.
  • Effizienz der Verwendung der Speicherhierarchie : Obwohl der Direktzugriffsspeicher dem Programmierer die Möglichkeit bietet, jederzeit und überall zu lesen oder zu schreiben, werden in der Praxis Latenz und Durchsatz von der Effizienz des Cache beeinflusst , die durch die Erhöhung der Referenzlokalität verbessert wird. Eine schlechte Lokalität der Referenz führt zu Cache- Thrashing und Cache-Verschmutzung, und um dies zu vermeiden, können Datenelemente mit schlechter Lokalität aus dem Cache umgangen werden.

Allgemeine Verwendung

Wenn der wesentliche Teil der Referenzen die meiste Zeit zu Clustern aggregiert und die Form dieses Clustersystems gut vorhergesagt werden kann, kann es zur Leistungsoptimierung verwendet werden. Es gibt mehrere Möglichkeiten, mithilfe von Optimierungstechniken von der Lokalität zu profitieren . Gängige Techniken sind:

  • Erhöhung der Lokalität von Referenzen (in der Regel softwareseitig)
  • Ausnutzung der Lokalität von Referenzen: Generell hardwareseitig erreicht, kann die zeitliche und räumliche Lokalität durch hierarchische Speicherhardware kapitalisiert werden. Die äquidistante Lokalität kann von den entsprechend spezialisierten Anweisungen der Prozessoren genutzt werden, diese Möglichkeit liegt nicht nur in der Verantwortung der Hardware, sondern auch der Software, ob deren Struktur geeignet ist, ein binäres Programm zu kompilieren, das die betreffenden spezialisierten Anweisungen aufruft. Die Verzweigungslokalität ist eine aufwendigere Möglichkeit, daher sind mehr Entwicklungsanstrengungen erforderlich, aber es gibt viel größere Reserven für zukünftige Explorationen in dieser Art von Lokalitäten als in allen anderen.

Räumliche und zeitliche Örtlichkeitsnutzung

Hierarchischer Speicher

Hierarchischer Speicher ist eine Hardwareoptimierung, die die Vorteile der räumlichen und zeitlichen Lokalität nutzt und auf mehreren Ebenen der Speicherhierarchie verwendet werden kann. Paging profitiert offensichtlich von der zeitlichen und räumlichen Lokalität. Ein Cache ist ein einfaches Beispiel für die Ausnutzung der zeitlichen Lokalität, da es sich um einen speziell entwickelten, schnelleren, aber kleineren Speicherbereich handelt, der im Allgemeinen verwendet wird, um kürzlich referenzierte Daten und Daten in der Nähe kürzlich referenzierter Daten zu halten, was zu potenziellen Leistungssteigerungen führen kann.

Datenelemente in einem Cache entsprechen nicht unbedingt Datenelementen, die im Hauptspeicher räumlich nahe beieinander liegen; Datenelemente werden jedoch jeweils eine Cache-Zeile in den Cache gebracht . Damit ist wieder die räumliche Lokalität wichtig: Wird ein Element referenziert, werden auch einige benachbarte Elemente in den Cache gebracht. Schließlich spielt auf unterster Ebene die zeitliche Lokalität eine Rolle, da sehr eng referenzierte Ergebnisse in den Maschinenregistern gehalten werden können . Einige Programmiersprachen (wie C ) erlauben dem Programmierer vorzuschlagen, dass bestimmte Variablen in Registern gehalten werden.

Die Datenlokalität ist ein typisches Speicherreferenzmerkmal von regulären Programmen (obwohl viele unregelmäßige Speicherzugriffsmuster existieren). Es macht das hierarchische Speicherlayout profitabel. Bei Computern wird der Speicher in eine Hierarchie eingeteilt, um Datenzugriffe zu beschleunigen. Die unteren Ebenen der Speicherhierarchie sind in der Regel langsamer, aber größer. Somit erreicht ein Programm eine höhere Leistung, wenn es Speicher verwendet, während es in den oberen Ebenen der Speicherhierarchie zwischengespeichert wird, und vermeidet, andere Daten in die oberen Ebenen der Hierarchie zu bringen, die Daten verdrängen, die in Kürze in der Zukunft verwendet werden. Dies ist ein Ideal und kann manchmal nicht erreicht werden.

Typische Speicherhierarchie (Zugriffszeiten und Cache-Größen sind Annäherungen an typische Werte, die ab 2013 zu Diskussionszwecken verwendet wurden; tatsächliche Werte und tatsächliche Anzahl von Ebenen in der Hierarchie variieren):

  • CPU-Register (8–256 Register) – sofortiger Zugriff mit der Geschwindigkeit des innersten Kerns des Prozessors
  • L1- CPU-Caches (32 KB bis 512  KB ) – schneller Zugriff mit der Geschwindigkeit des innersten Speicherbusses, der ausschließlich jedem Kern gehört
  • L2-CPU-Caches (128 KB bis 24  MB ) – etwas langsamerer Zugriff, wobei die Geschwindigkeit des Speicherbusses von Zwillingen von Kernen geteilt wird
  • L3-CPU-Caches (2 MB bis 32  MB ) – noch langsamerer Zugriff, wobei die Geschwindigkeit des Speicherbusses von noch mehr Kernen desselben Prozessors geteilt wird
  • Haupt physischen Speicher ( RAM ) (256 MB bis 64  GB ) - langsame Zugriffs, dessen Geschwindigkeit wird durch die räumlichen Abstände und allgemeine Hardware - Schnittstellen zwischen dem Prozessor und den Speichermodulen auf der begrenzten Motherboard
  • Festplatte ( virtueller Speicher , Dateisystem ) (1 GB bis 256  TB ) – sehr langsam, aufgrund des schmaleren (in Bitbreite), physikalisch viel längeren Datenkanals zwischen der Hauptplatine des Computers und den Festplattengeräten und aufgrund der überflüssiges Softwareprotokoll oben auf der langsamen Hardwareschnittstelle erforderlich
  • Remote-Speicher (andere Computer oder die Cloud) (praktisch unbegrenzt) – Geschwindigkeit variiert von sehr langsam bis extrem langsam

Moderne Maschinen neigen dazu, Blöcke mit niedrigerem Speicher in die nächste Ebene der Speicherhierarchie zu lesen. Wenn dadurch belegter Speicher verdrängt wird, versucht das Betriebssystem vorherzusagen, auf welche Daten am wenigsten (oder zuletzt) ​​zugegriffen wird und verschiebt sie in der Speicherhierarchie nach unten. Vorhersagealgorithmen sind in der Regel einfach, um die Komplexität der Hardware zu reduzieren, obwohl sie etwas komplizierter werden.

Matrix-Multiplikation

Ein gängiges Beispiel ist die Matrixmultiplikation :

for i in 0..n
  for j in 0..m
    for k in 0..p
      C[i][j] = C[i][j] + A[i][k] * B[k][j];

Durch Umschalten der Schleifenreihenfolge für jund kwird die Beschleunigung bei großen Matrixmultiplikationen dramatisch, zumindest für Sprachen, die zusammenhängende Array-Elemente in die letzte Dimension stellen. Dies ändert das mathematische Ergebnis nicht, verbessert jedoch die Effizienz. In diesem Fall bedeutet "groß" ungefähr mehr als 100.000 Elemente in jeder Matrix oder genügend adressierbaren Speicher, so dass die Matrizen nicht in L1- und L2-Caches passen.

for i in 0..n
  for k in 0..p
    for j in 0..m
      C[i][j] = C[i][j] + A[i][k] * B[k][j];

Der Grund für diese Beschleunigung ist, dass im ersten Fall die Lesevorgänge von A[i][k]im Cache gespeichert sind (da der kIndex die zusammenhängende, letzte Dimension ist), dies jedoch B[k][j]nicht der Fall ist, so dass eine Cache-Miss-Strafe auf B[k][j]. C[i][j]ist irrelevant, weil es sein kann , gehißt der inneren Schleife aus - der Schleifenvariable ist k.

for i in 0..n
  for j in 0..m
    temp = C[i][j]
    for k in 0..p
      temp = temp + A[i][k] * B[k][j];
    C[i][j] = temp

Im zweiten Fall befinden sich die Lese- und Schreibvorgänge von C[i][j]beide im Cache, die Lesevorgänge von B[k][j]befinden sich im Cache, und das Lesen von A[i][k]kann aus der inneren Schleife gehoben werden.

for i in 0..n
  for k in 0..p
    temp = A[i][k]
    for j in 0..m
      C[i][j] = C[i][j] + temp * B[k][j];

Somit hat das zweite Beispiel keine Cache-Fehltreffer-Strafe in der inneren Schleife, während das erste Beispiel eine Cache-Strafe hat.

Auf einem Prozessor aus dem Jahr 2014 ist der zweite Fall ungefähr fünfmal schneller als der erste Fall, wenn er in C geschrieben und mit kompiliert wird gcc -O3. (Eine sorgfältige Prüfung des demontierten Code zeigt , dass im ersten Fall, GCC verwendet SIMD Anweisungen und im zweiten Fall tut es nicht, aber die Cache - Strafe ist viel schlimmer als die SIMD - Verstärkung.)

Die zeitliche Lokalität kann im obigen Beispiel auch durch eine Technik namens Blocking verbessert werden . Die größere Matrix kann in gleich große Untermatrizen unterteilt werden, so dass die kleineren Blöcke im Speicher mehrmals referenziert (multipliziert) werden können. Beachten Sie, dass dieses Beispiel für quadratische Matrizen der Dimensionen SIZE x SIZE funktioniert, aber es kann leicht für beliebige Matrizen erweitert werden, indem SIZE_I, SIZE_J und SIZE_K gegebenenfalls ersetzt werden.

for (ii = 0; ii < SIZE; ii += BLOCK_SIZE)
  for (kk = 0; kk < SIZE; kk += BLOCK_SIZE)
    for (jj = 0; jj < SIZE; jj += BLOCK_SIZE)
      maxi = min(ii + BLOCK_SIZE, SIZE);
      for (i = ii; i < maxi; i++)
        maxk = min(kk + BLOCK_SIZE, SIZE);
        for (k = kk; k < maxk; k++)
          maxj = min(jj + BLOCK_SIZE, SIZE);
          for (j = jj; j < maxj; j++)
            C[i][j] = C[i][j] + A[i][k] * B[k][j];

Die zeitliche Lokalität der obigen Lösung ist gegeben, weil ein Block vor dem Weitergehen mehrmals verwendet werden kann, so dass er weniger oft in den Speicher und aus dem Speicher verschoben wird. Die räumliche Lokalität wird verbessert, da Elemente mit aufeinanderfolgenden Speicheradressen dazu neigen, gemeinsam in der Speicherhierarchie hochgezogen zu werden.

Siehe auch

Verweise

Literaturverzeichnis