Localitat de referència

En informàtica, la localitat de referència, també coneguda com a principi de localitat, és la tendència d'un processador a accedir al mateix conjunt d'ubicacions de memòria de manera repetitiva durant un període de temps curt. Hi ha dos tipus bàsics de localitat de referència – localitat temporal i espacial. La localitat temporal es refereix a la reutilització de dades i/o recursos específics en un període de temps relativament petit. La localitat espacial (també anomenada localitat de dades) fa referència a l'ús d'elements de dades dins d'ubicacions d'emmagatzematge relativament properes. La localitat seqüencial, un cas especial de localitat espacial, es produeix quan els elements de dades s'organitzen i s'accedeix linealment, com ara travessant els elements en una matriu unidimensional.

La localitat és un tipus de comportament previsible que es produeix als sistemes informàtics. Els sistemes que presenten una forta localitat de referència són excel·lents candidats per a l'optimització del rendiment mitjançant l'ús de tècniques com ara la memòria cau, la recuperació prèvia per a la memòria i els predictors de branca avançats en l'etapa de canalització d'un nucli de processador.

Tipus de localitat

Hi ha diferents tipus de localitats de referència:

• Localitat temporal: si en un moment es fa referència a una ubicació de memòria determinada, és probable que es torni a fer referència a la mateixa ubicació en un futur proper. Hi ha proximitat temporal entre referències adjacents a la mateixa ubicació de memòria. En aquest cas és habitual fer esforços per emmagatzemar una còpia de les dades referenciades en un emmagatzematge de memòria més ràpid, per reduir la latència de les referències posteriors. La localitat temporal és un cas especial de localitat espacial (vegeu més avall), és a dir, quan la ubicació prospectiva és idèntica a la ubicació actual.
• Localitat espacial: si es fa referència a una ubicació d'emmagatzematge concreta en un moment determinat, és probable que es faci referència a ubicacions de memòria properes en un futur proper. En aquest cas, és habitual intentar endevinar la mida i la forma de l'àrea al voltant de la referència actual per a la qual val la pena preparar un accés més ràpid per a una referència posterior.
  • Localitat de memòria (o localitat de dades ): Localitat espacial relacionada explícitament amb la memòria.
• Localitat de branca: si només hi ha unes poques alternatives possibles per a la part prospectiva del camí a l'espai de coordenades espacial-temporal. Aquest és el cas quan un bucle d'instruccions té una estructura simple, o el possible resultat d'un petit sistema d'instruccions de ramificació condicional està restringit a un petit conjunt de possibilitats. La localitat de la branca normalment no és una localitat espacial, ja que les poques possibilitats es poden situar molt lluny les unes de les altres.
• Localitat equidistant: A mig camí entre localitat espacial i localitat ramal. Considereu un bucle que accedeix a ubicacions en un patró equidistant, és a dir, el camí a l'espai de coordenades espacial-temporal és una línia de punts. En aquest cas, una funció lineal senzilla pot predir a quina ubicació s'accedirà en un futur proper.

Per tal de beneficiar-se de la localitat temporal i espacial, que es produeix amb freqüència, la majoria dels sistemes d'emmagatzematge d'informació són jeràrquics. La localitat equidistant sol ser compatible amb les diverses instruccions d'increment no trivials d'un processador. Per a la localitat de la branca, els processadors contemporanis tenen predictors de branca sofisticats, i sobre la base d'aquesta predicció el gestor de memòria del processador intenta recollir i preprocessar les dades d'alternatives plausibles.

Ús de la localitat espacial i temporal

Memòria jeràrquica

La memòria jeràrquica és una optimització de maquinari que aprofita els beneficis de la localitat espacial i temporal i es pot utilitzar en diversos nivells de la jerarquia de memòria. La paginació òbviament es beneficia de la localitat temporal i espacial. Una memòria cau és un exemple senzill d'explotació de la localitat temporal, perquè és una àrea de memòria especialment dissenyada, més ràpida però més petita, que s'utilitza generalment per mantenir les dades i les dades de referència recentment a prop de les dades de referència recents, cosa que pot provocar augments potencials del rendiment.

Els elements de dades d'una memòria cau no es corresponen necessàriament amb els elements de dades que estan espacialment propers a la memòria principal; tanmateix, els elements de dades s'introdueixen a la memòria cau una línia a la vegada. Això vol dir que la localitat espacial torna a ser important: si es fa referència a un element, alguns elements veïns també es portaran a la memòria cau. Finalment, la localitat temporal juga un paper en el nivell més baix, ja que els resultats que es refereixen molt a prop es poden guardar en els registres de la màquina. Alguns llenguatges de programació (com ara C) permeten al programador suggerir que certes variables es mantinguin en registres.

La localitat de les dades és una característica de referència de memòria típica dels programes normals (tot i que existeixen molts patrons d'accés a la memòria irregulars). Fa que la disposició de la memòria jeràrquica sigui rendible. En els ordinadors, la memòria es divideix en una jerarquia per tal d'accelerar l'accés a les dades. Els nivells inferiors de la jerarquia de memòria solen ser més lents, però més grans. Així, un programa aconseguirà un major rendiment si utilitza la memòria mentre està en memòria cau als nivells superiors de la jerarquia de memòria i evita portar altres dades als nivells superiors de la jerarquia que desplaçaran les dades que s'utilitzaran en breu en el futur. Aquest és un ideal, i de vegades no es pot aconseguir.

Jerarquia de memòria típica (els temps d'accés i les mides de la memòria cau són aproximacions dels valors típics utilitzats a 2013 amb finalitats de discussió; els valors reals i el nombre real de nivells a la jerarquia varien):

• Registres de la CPU (8–256 registres) – accés immediat, amb la velocitat del nucli més interior del processador
• Cachés de CPU L1 (32 KB a 512 KB) – accés ràpid, amb la velocitat del bus de memòria més interior propietat exclusiva de cada nucli
• Cachés de CPU L2 (128 KB fins a 24 MB) – accés una mica més lent, amb la velocitat del bus de memòria compartida entre dos nuclis.
• Cachés de CPU L3 (2 MB fins a un màxim de 64 MB) – accés encara més lent, amb la velocitat del bus de memòria compartida entre encara més nuclis del mateix processador
• Memòria física principal (RAM) (256 MB fins a 64 GB) – accés lent, la velocitat del qual està limitada per les distàncies espacials i les interfícies de maquinari generals entre el processador i els mòduls de memòria de la placa base
• Disc (memòria virtual, sistema de fitxers) (1 GB fins a 256 TB) – molt lent, a causa del canal de dades més estret (en ample de bits), físicament molt més llarg entre la placa principal de l'ordinador i els dispositius de disc, i a causa del protocol de programari ali necessari a la part superior de la interfície de maquinari lenta
• Memòria remota (altres ordinadors o el núvol) (pràcticament il·limitada) – la velocitat varia de molt lenta a extremadament lenta

Les màquines modernes tendeixen a llegir blocs de memòria inferior al següent nivell de la jerarquia de memòria. Si això desplaça la memòria utilitzada, el sistema operatiu intenta predir a quines dades s'accedirà menys (o les darreres) i moure'ls cap avall per la jerarquia de memòria. Els algorismes de predicció solen ser senzills per reduir la complexitat del maquinari, tot i que s'estan tornant una mica més complicats.