Principio di località (informatica)
In informatica il principio di località è un principio che dipende dall'esatta natura del programma, quindi non è da considerarsi una legge inflessibile, che non può essere cambiata, ma come una linea guida in quanto valido per la maggior parte dei casi ("rule of thumb", Regola del pollice).
Enunciato:
"Durante l'esecuzione di una data istruzione presente in memoria, con molta probabilità le successive istruzioni saranno ubicate nelle vicinanze di quella in corso. Nell'arco di esecuzione di un programma si tende a fare riferimenti continui alle stesse istruzioni."
Come si può notare esistono due località che compongono tale principio:
- Località spaziale.
- Località temporale.
Località spaziale
[modifica | modifica wikitesto]Se la CPU sta eseguendo un'istruzione presente in memoria, vuol dire che con molta probabilità le prossime istruzioni da eseguire si troveranno fisicamente nelle vicinanze di quella in corso; vale a dire che, durante la normale esecuzione dei programmi, la CPU passa molto tempo accedendo a zone di memoria ristrette e solo occasionalmente accede a locazioni molto lontane.
Ad esempio, una memoria cache può memorizzare in una zona di un programma contigua le informazioni che vengono utilizzate spesso(come un array), riducendone notevolmente i tempi di accesso:
Array a |0|1|2|3|4|5|6|7|8|9| di 10 elementi
//dichiarazione variabili
int a[10]={0,1,2,3,4,5,6,7,8,9};
int somma = 0;
for (i=0 ; i<10 ; i++){
somma += a[i]; //accesso ad array
}
Considerando solamente gli accessi all'array a [riga 6], all'inizio dell'esecuzione del ciclo for, si accede alla locazione di memoria a[0]: il gestore della memoria cercherà nella memoria cache tale indirizzo, che non sarà presente (si è verificato dunque un cache miss, mancanza del dato). Si provvederà a caricare nella cache tale dato, insieme alle zone di memoria ad esso vicine.
Situazione nella Cache: a[0], a[1], a[2], a[3], a[4]
Al successivo accesso a[1], si avrà un cache hit (ovvero il dato è stato trovato nella cache), in quanto, avendo caricato la zona in cui risiedeva a[0], si trova anche a[1], cioè sono vicini nello spazio fisico.
Si prosegue nell'esecuzione accedendo ad a[2], a[3], a[4], sempre incorrendo in un cache hit, accesso molto veloce.
Arrivati ad a[5], dal momento che questo non è presente nella memoria cache, si verifica un cache miss e la cache viene aggiornata con altri valori a seguire a[5]:
Cache: a[0]... a[5], a[6], a[7], a[8], a[9]
A questo punto, ogni accesso successivo all'array a sarà presente nella cache.
Su 10 accessi a memoria, si sono verificati 2 miss e 8 hit, con una percentuale dell'80% di hit. Per migliorare e sfruttare il principio di località, si cerca di aumentare questo tasso, caricando opportunamente quantità di memoria nella cache (notare che le memorie cache sono limitate in termini di quantità di memoria).
Località temporale
[modifica | modifica wikitesto]In genere, gran parte del codice di cui sono costituiti i programmi viene eseguito solo raramente, al verificarsi di errori o condizioni anomale: quindi, succede spesso che di tutto il codice che un programma carica in memoria ne venga realmente eseguita solo una piccola parte.
La località temporale si basa su questo: nell'arco temporale di esecuzione del programma, si accede molto spesso alle stesse zone del programma.
Dunque, mantenendo una copia in memoria cache dei dati più richiesti durante l'esecuzione del programma, si sfrutta tale principio.
Ad esempio, se una struttura dati, una variabile o una particolare routine, vengono utilizzate da un programma per la maggior parte del tempo, si possono memorizzare in una cache, rendendo tali riferimenti ripetitivi, efficienti e veloci.
Usi
[modifica | modifica wikitesto]
Questo principio è alla base del buon funzionamento della memoria cache(come TLB) e della memoria virtuale. Invece, dove tale principio non è rispettato, come per esempio nelle CPU grafiche tridimensionali che devono obbligatoriamente leggere tutta la memoria allocata per le texture ad ogni nuovo fotogramma da generare, implementare meccanismi di caching o di memoria virtuale penalizza pesantemente le prestazioni invece di migliorarle.
