Diskussion:Lokalitätseigenschaft

Und was hat das mit der Zeit zu tun?

Das steht in keinem Verhältnis von Adressraum und Zeit! (nicht signierter Beitrag von 134.130.232.116 (Diskussion) 13:01, 3. Jul 2013 (CEST))

Lokalitätsausnutzung

Da Caches schnell sein sollen, verwendet man für sie meist eine andere (schnellere) Speichertechnologie als für den zu cachenden Speicher (zum Beispiel SRAM gegenüber DRAM, DRAM gegenüber Magnetscheibe etc.). Daher sind Caches meist wesentlich teurer in Bezug auf das Preis-Bit-Verhältnis, weswegen Caches deutlich kleiner ausgelegt werden. Das führt dazu, dass ein Cache nicht alle Daten gleichzeitig vorrätig haben kann. Um das Problem zu lösen, welche Daten denn nun im Cache gehalten werden sollen, werden Lokalitätseigenschaften der Zugriffe ausgenutzt:

   Zeitliche (temporale) Lokalität: Da sich Zugriffe auf Daten wiederholen (z. B. beim Abarbeiten einer Programmschleife), ist es eher wahrscheinlich, dass auf Daten, auf die schon einmal zugegriffen wurde, auch noch ein weiteres Mal zugegriffen wird. Diese Daten sollten also bevorzugt im Cache gehalten werden. Dadurch ergibt sich auch eine Notwendigkeit, alte Daten, die lange nicht benutzt wurden, aus dem Cache zu entfernen, um Platz für neuere zu machen. Diesen Vorgang nennt man auch „Verdrängung“.
   Räumliche (spatiale) Lokalität: Da Programmcode und -daten nicht wild verstreut im Adressraum herumliegen, sondern „hintereinander“ und teilweise auch nur in bestimmten Adressbereichen angeordnet sind (Code-, Daten-, Stack-Segment, Heap etc.), ist es bei einem stattgefundenen Zugriff auf eine bestimmte Adresse wahrscheinlich, dass auch auf eine „naheliegende“ Adresse (sprich: Betrag der Differenz der beiden Adressen sehr klein) zugegriffen wird. Bei der Abarbeitung eines Programms wird z. B. ein Befehl nach dem anderen abgearbeitet, wobei diese „nacheinander“ im Speicher liegen (wenn es kein Sprung ist). Viele Datenstrukturen wie Arrays liegen ebenfalls „hintereinander“ im Speicher.

Die räumliche Lokalität ist der Grund, warum man bei Caches nicht einzelne Bytes, sondern die Daten ganzer Adressbereiche („Cacheblock“ oder manchmal auch „Cache-Line“ genannt) speichert. Zusätzlich erleichtert das die Implementierung und verringert Speicheroverhead, da man nicht für jedes Datenbyte dessen Adresse im Speicher festhalten muss, sondern nur für jeden Cacheblock (der aus vielen Bytes besteht). Die Wahl der Blockgröße ist ein wichtiger Designparameter für einen Cache, der die Leistung stark beeinflussen kann, positiv wie auch negativ. (nicht signierter Beitrag von 134.130.232.76 (Diskussion) 13:03, 3. Jul 2013 (CEST))