[c] Ottimizzazione del codice

[Demin Black Off]

Dovendo fare operazioni su blocchi di matrice di dimensione fissa, ho trovato un documento che consiglia di suddividere la matrice in blocchetti e memorizzarli in modo consecutivo.

Questo garantisce l'eliminazione di

TLB problems
riduce il cache thashing e massimizza l'utilizzo dei blocchi di cache.

Qualcuno mi sa spiegare cosa vuol dire TLB problems ??

[cdimauro]

Translation Lookaside Buffer. E' un buffer che la CPU usa per memorizzare un certo numero di entry. Ogni entry rappresenta un indirizzo virtuale da tradurre in indirizzo fisico.

Si usa con la memoria paginata, perché in genere la memoria virtuale è mappata gerarchicamente tramite un albero chiamato Page Table, dove ogni livello traduce una porzione dell'indirizzo virtuale, e ovviamente l'ultima parte contiene l'indirizzo fisico vero e proprio.

Ti risparmio ulteriori (tediosi) dettagli (che, comunque, ho descritto in maniera più precisa di recente in un altro thread), comunque questo processo di attraversamento della page table per ottenere l'indirizzo fisico è ovviamente dispendioso, e applicarlo per OGNI traduzione ucciderebbe le prestazioni della CPU, come puoi ben immaginare.

Per questo si usano i TLB: a ogni nuovo indirizzo virtuale da tradurre viene fatto posto nel TLB (generalmente scartando l'entry più vecchia), e in questo modo alle occorrenze successive l'indirizzo virtuale viene immediatamente tradotto in indirizzo fisico.

Essendo, però, limitato, il TLB non può eseguire il caching di tutti gli indirizzi virtuali, per cui è necessario comunque cercare di ridurre al minimo i problemi di svuotamento del TLB, facendo sì che la CPU acceda quanto più possibili a dati "locali" (intendendo con ciò non dati che risiedono tutti vicini, ma dati che risiedono su pagine che vengono usate molto spesso).

Quindi si deve minimizzare il numero di TLB entry usate in modo da non inficiare le prestazioni della CPU. Un buon sistema è quello, appunto, di localizzare dati sempre sulle stesse pagine, e nel tuo caso procedere alla suddivisione della matrice in blocchi contenenti un certo numero di valori, e accedere a (tutti) i valori di un blocco (prima di passare a un altro) viene in contro al problema di minizzare le TLB usate, appunto.

So che è un argomento complesso e di essere stato piuttosto superficiale: eventualmente avessi ancora dubbi, chiedi pure. ;)

[Demin Black Off]

Sei stato chiarissimo, ti ringrazio :)

[Demin Black Off]

Volendo riepilogare :

La memoria è suddivisa in pagine
La TLB è una cache che mantiene gli indirizzi fisici delle pagine più recentemente usate
Le pagine di memoria sono suddivise in blocchi che sono caricati, su richiesta, nella cache.

Se faccio riferimento ad un dato di una pagina non presente nella TLB, bisogna fare un accesso alla memoria per reperire nella PageTable l'indirizzo fisico della pagina

POI

accedere alla cache per verificare se il dato è presente, se non è presente è necessario fare un accesso alla memoria per prendere il blocco della pagina e caricarlo il cache.


Se i blocchi di matrice sono tutti nella stessa pagina -> non devo fare traduzioni, oltre alla prima

Se i dati sono vicini in termini di indirizzi -> Riutilizzo i dati presenti nella cache.

Ok ? Quindi il codice C fatto in quel moto è ottimizzato !

[cdimauro]

Sì, esattamente. :)