Principiul de localitate (informatică)

Localitatea memoriei (numită și Principiul de localitate sau Localitatea datelor) este un termen din informatică utilizat pentru a descrie proximitatea temporală sau spațială a accesărilor locațiilor de memorie în programele de calculator. Există două tipuri primare de localitate a referinței de memorie: temporală și spațială:

Tipuri de localitate a datelor

• Localitate temporală: Un concept conform căruia o locație de memorie care este referită de către un program la un moment dat va fi referită din nou cândva în viitorul apropiat.
• Localitate spațială: Un concept conform căruia probabilitatea de referire a locației de memorie de către un program este mai mare dacă o locație de memorie din apropiere a fost deja referită.

Organizarea ierarhică a memoriei

Localitatea datelor este o capabilitate tipică a referinței de memorie în programele obișnuite (deși există multe modele de acces neregulat la memorie). Aceasta determină în mod pozitiv profitul din organizarea ierarhizată a memoriei. În calculatoare, memoria e divizată și ierarhizată pentru a crește viteza accesărilor de date. Nivelele de la baza ierarhiei memoriei tind să devină mai lente, dar mai mari. De aceea, un program va deveni mai performant dacă utilizează memorie cât timp aceasta este stocată în nivelele superioare din ierarhia memoriei și ocolește aducerea altor date pe nivelele superioare ale ierarhiei care altfel vor disloca datele care vor fi utilizate în scurt timp. Acesta este un ideal, și câteodată nu poate fi atins.

Tipul obișnuit de ierarhie a memoriei (timpii de acces și dimensiunea memoriei cache) sunt aproximații ale valorilor tipice utilizate din 2006 încoace în cazul discutat; valorile efective și numărul de nivele în cadrul ierarhiei variază:

• registrele UCP (registrele 8-32) – accesul imediat (0-1 cicluri de procesor)
• L1 memoriile cache ale UCP-urilor (32 KiB până la 128 KiB) – acces rapid (3 cicluri de procesor)
• memorii cache ale UCP-urilor de tipul L2 (128 KiB până la 4 MiB) – acces puțin mai lent (10 cicluri de procesor)
• memoria RAM principală memorie fizică (RAM) (256 MiB până la 4 GiB) – acces lent (100 cicluri de procesor)
• Disc (memorie virtuală și sistem de fișiere) (1 GiB până la 1 TiB) – foarte lent (1.000-10.000 cicluri de procesor)
• Memorie Depărtată (sum ar fi alte calculatoare sau Internetul) (Practic nelimitată) – viteza variază

Mașinile moderne tind să citească blocuri memorie de pe nivelele inferioare și să le scrie pe următorul nivel din ierarhia memoriei. Dacă aceasta determină dizlocarea memoriei utilizate, atunci sistemul de operare încearcă să prezică ce date vor fi accesate la urmă (sau în ultimul rând) și le mută în jos în cadrul ierarhiei. Algoritmii de predicție tind să devină simpli pentru a reduce din complexitatea hardware-ului, deși ei devin întrucâtva mai complicați.

Exemplu

Un exemplu obișnuit este înmulțirea matricilor:

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];

Când se confruntă cu matrice mari, acest algoritm tinde să amestece datele de jur împrejur prea mult. Întrucât memoria este trasă în susul ierarhiei în blocuri cu adrese consecutive, în limbajul C va fi avantajos să se refere câteva adrese de memorie ce au în comun aceeași linie (localitate spațială). Menținând numărul liniei fix, următorul element se modifică mai rapid. În C și C++, aceasta înseamnă că adresele de memorie sunt utilizate într-un mod ce se apropie de modelul secvențial. Cineva ar putea observa că întrucât j afectează referința la coloană a ambelor matrici C și B, ar trebui să fie iterat în bucla centrală (aceasta va fixa iteratorii de linie, i și k, cât timp j traversează fiecare coloană pe rând). Aceasta nu va modifica rezultatul matematic, dar îmbunătățește eficiența. Înterschimbând ordinea de iterare pentru j și k, creșterea de viteză în înmulțirea matricelor de dimensiuni mari devine semnificativă. (În acest caz , 'mare' înseamnă, aproximativ, mai mult de 100.000 elemente în fiecare matrice, sau destulă memorie adresabilă, astfel încât matricile nu vor încăpea în memoriile cash de tip L1 și L2.)

Localitatea temporală poate fi de asemenea îmbunătățită în exemplul anterior prin utilizarea unei tehnici numită În blocuri. Matricea mai mare poate fi împărțită în submatrici de dimensiuni egale, astfel încât blocurile de dimensiuni mai mici pot fi referite (înmulțite) de câteva ori cât timp acestea se află încă în memorie.

for (ii = 0; ii < SIZE; ii += BLOCK_SIZE)
  for (kk = 0; kk < SIZE; kk += BLOCK_SIZE)
    for (jj = 0; jj < SIZE; jj += BLOCK_SIZE)
      for (i = ii; i < ii + BLOCK_SIZE && i < SIZE; i++)
        for (k = kk; k < kk + BLOCK_SIZE && k < SIZE; k++)
          for (j = jj; j < jj + BLOCK_SIZE && k < SIZE; j++)
            C[i][j] = C[i][j] + A[i][k] * B[k][j];

Localitatea temporală din exemplul de mai sus este obținută deoarece un bloc poate fi utilizat de câteva ori înainte de a trece mai departe, astfel încât este mutat în și din memorie mai puțin frecvent. Localitatea spațială este îmbunătățită pentru că elementele cu adrese de memorie consecutive tind să fie scoase din ierarhia memoriei împreună.