Cache-uri

Mihai BUDIU
mihaib@pub.ro, budiu at cs.cornell.edu,
http://www.cs.cornell.edu/Info/People/budiu/budiu.html

ianuarie 1997

Subiect:
principiul cache-ului și aplicații
Cuvinte cheie:
cache, memorie virtuală, memorie asociativă, politică de înlocuire, localitate
Cunoștințe necesare:
arhitectura elementară a calculatoarelor


Contents




În acest articol îmi propun să disec unul dintre cele mai simple dintre ``aparatele'' folosite de calculatoare. Voi încerca să arăt că există foarte multe varietăți de cache, dar că toate se bazează pe aceeași idee foarte simplă: ține la-ndemînă ceea ce folosești des. Voi încerca de asemenea să arăt că fiecare calculator folosește cache-ul într-o mulțime de instanțe, și că impactul lui asupra eficienței este extrem de mare.

Ideea

Cuvîntul ``cache'' este extrem de familiar celor care lucrează cu calculatoare; chiar și cînd vrei să cumperi un calculator ți se spune: ``120MHz, cache de 256Kb, etc, etc''. Cuvîntul este împămîntenit în forma asta, și cum nu cunosc o traducere rezonabilă, voi continua să-l folosesc astfel. Voi desluși puțin mai tîrziu sursa numelui (care este un cuvînt franțuzesc, dar folosit ca atare de întreaga comunitate anglofonă a calculatoriștilor, ceea ce e se întîmplă foarte rar). Pronunția la rîndul ei variază: este sau ``cașe'' (franțuzism), sau ``cheiș'' (citire americană a cuvîntului).

Ce este un cache?

Mai curînd decît un dispozitiv concret putem spune despre cache că este un ``principiu''. Există foarte multe feluri de cache, unele construite din hardware special, altele care sunt doar programe. Toate însă se bazează pe aceeași idee:

Noi avem acasă un dulap (nu prea mare, dar la-ndemînă) și o debara (ceva mai mare, dar ce dezordine înauntru!). Primăvara și toamna se produce o mutare masivă de haine: hainele groase o iau într-o direcție, dislocuindu-le pe cele subțiri. Decizia este naturală, chit că ia o zi sa faci mutarea: după aia ai tot ce-ți trebuie la-ndemînă pentru juma' de an. O dificultate se ivește cînd dai peste o iarnă extrem de caldă, sau o vară prea rece: trebuie să scurmi în debara după ceva haine și cu alt prilej decît cu schimbarea sezonului.

Acesta este un exemplu tipic de cache.

În calculatoare lucrurile stau tot așa: am la dispoziție două memorii, una ieftină, mare (pentru că-ți permiți să cumperi), dar cam lentă, una mică și scumpă, dar rapidă. (Cel mai bine e sa fii și bogat și sănătos, dar nu se poate întotdeauna.) În plus mai am și o cantitate mare de date de păstrat, așa că trebuie să le țin în memoria lentă [debaraua], care e suficient de încăpătoare. Din păcate durează prea mult să iau și să pun lucruri acolo: nu e practic să am numai debara; trebuie și un dulap (memoria rapidă): doar nu o să pun hainele musafirilor în debara, nu? Memoria rapidă [dulapul] este cache-ul. Din păcate nu încape totul în memoria rapidă, așa că sunt forțat ca atunci cînd pun ceva în ea, să scot altceva în memoria lentă. Treaba este avantajoasă atîta vreme cît lucrurile aduse în memoria rapidă sunt folosite frecvent, deci nu trebuie să le tot mut. Figura 1 arată cum stau lucrurile.

Observați ca scopul meu nu este nici să am debara, nici să am dulap, ci să pot să pun undeva hainele, și să le pot manipula suficient de ușor. Dulapul și debaraua sunt doar unelte, nu scopuri. Dacă debaraua ar fi suficient de la-ndemînă, n-aș mai folosi dulapul deloc.

Figure 1: Principiul cache-ului
\begin{figure}\centerline{\epsfxsize=8cm\epsffile{principiul.eps}}\end{figure}

Atenție la analogie, care nu merge pînă la capăt: în calculatoare conținutul memoriei se copiază foarte ușor, ceea ce nu este adevărat despre paltoane. În calculatoare, cînd ``mut'' ceva, de fapt fac o copie; acel ceva rămîne și în memoria-sursă (locul de unde iau).

Numele

Abstract vorbind: vreau să implementez două operații pentru stocarea de date: citește și scrie. Pot să citesc și să scriu din memoria lentă, și totul merge cum trebuie, dar prea lent. Pentru a spori eficiența, copiez parte din memoria lentă în cea rapidă, și încerc să citesc și să scriu acolo. Cînd nu găsesc ce-mi trebuie, operez din nou în memoria lentă.

``Caché'', (cu accent ascuțit pe ultimul e), înseamnă în limba franceză ``ascuns''. Așa este și memoria rapidă: este un dispozitiv care poate să fie, sau poate să lipsească; absența lui se va remarca numai printr-o viteză mai scăzută, dar nu printr-o reducere a funcționalității (adică toate operațiile pe care le pot face cu cache-ul, le pot face și fără el).

În limbaj tehnic asta înseamnă că un cache oferă aceeași interfață lumii exterioare ca interfața pe care el o folosește; nu oferă nici o funcție suplimentară (pentru că atunci mi-aș da seama cînd l-aș scoate că lipsește ceva), ci doar crește eficiența.

Figura 1 arată acest lucru, indicînd interfețele, care constau din două proceduri: una pentru scriere și una pentru citire.

Cu toate că nu face mare lucru, vom vedea că arhitectura internă a cache-ului nu este banală, și că pentru a folosi eficient spațiul mic pe care-l are, trebuie să-și dea ceva osteneală.

Eficiența și localitatea

În mod evident, un cache nu este util în orișice situație: să ne imaginăm o țară cu o climă foarte capricioasă, în care fiecare zi este altfel decît cea precedentă. În cazul ăsta aproape niciodată nu am avea în dulap hainele necesare, și ar trebui să le mutăm din debara și înapoi. Dulapul mai mult ar complica treaba decît ar ajuta, pentru că pe lîngă faptul că nu oferă hainele de care avem nevoie, mai trebuie să avem grijă și de el.

La fel este și în calculatoare: un cache este util numai dacă anumite informații sunt folosite frecvent și mult. Atunci acele informații merită păstrate înauntru. Din fericire, experimental s-a constatat că acest lucru este foarte adesea adevărat. Această observație poate fi formulat în felurite moduri; unul dintre ele este ``principiilor localității (locality principles)''. Avem două feluri de localitate:

Acestea sunt doar observații, dar se potrivesc destul de bine la programele de calculator, așa cum funcționează ele în calculatoarele moderne (poate în viitor lucrurile se vor schimba). Validitatea observațiilor ne permite să folosim cache-uri. Asta nu înseamnă că nu există programe care folosesc prost cache-urile; dimpotrivă, dacă vreți puteți scrie destul de ușor un astfel de program (este o metodă eficientă de a încetini calculatorul de la locul de muncă). Programele obișnuite însă nu se comportă așa.

Eficiența unui cache se măsoară în procentajul de ``nimereli'' H (hit ratio): din 100 de accese, cîte găsesc datele în cache? Opusul acestei valori este miss ratio M (rateuri). Procentajele astea se măsoară rulînd o grămadă de programe și făcînd media. Avem desigur, dacă socotim 33% ca 1/3:


H = 1 - M

Dacă timpul de citire din cache este Tc (``hit time''), iar timpul pe care îl pierdem cînd ratăm este Tm (``miss time'') atunci putem măsura timpul mediu de acces la memoria cu cache cu următoarea formulă:


T = Tc x H + Tm x M

Observați că timpul unei ratări (Tm) nu este neapărat egal cu timpul de citire din memoria lentă (Tl), pentru că în cazul unei ratări, întîi trebuie să ne dăm seama dacă datele sunt în cache, iar dacă nu sunt să accesăm memoria lentă.

Cache-ul va fi eficient dacă T < Tl. Altfel mai bine fără el.

H depinde de mărimea cache-ului: pentru un cache de mărimea memoriei lente (caz limită), toate datele pot fi ținute în memoria rapidă, și vom avea H=1. Pentru un cache de mărime 0, H=0, pentru că niciodată datele nu se găsesc în el. Relația între mărimea cache-ului, a memoriei lente și H nu este o linie dreaptă, ci crește repede la început (figura 2). Din cauza asta un cache relativ mic ca mărime are o importanță mare ca eficiență.

Figure 2: Performanța cache-ului
\begin{figure}\centerline{\epsfxsize=6cm\epsffile{marime.eps}}\end{figure}

Eficiența depinde și de raportul dintre Tc și Tm; în anumite cazuri Tm este de ordinul a 10000 x Tc, deci chiar un H mic poate să însemne mare lucru.

Variațiuni

Pe lîngă dimensiuni și timpi de acces, există o sumedenie de detalii prin care cache-urile diferă între ele, datorate faptului că mediile de stocare a informației nu se comportă chiar la fel. Iată unele dintre posibilele diferențe:

1)
Mărimea blocului de date: cîteodată este mai economic să transporți mai multe date deodată din memoria lentă; cache-urile aduc atunci mai mult decît li se cere (un calup) și păstrează totul, în ideea (sugerată de principiul de localitate spațială) că și vecinii obiectului accesat vor fi căutați în curînd. Unitatea de transfer între cache și memoria lentă e numită bloc.

2)
Politica de înlocuire: după o vreme cache-ul se va umple cu date, și totuși altele vor trebui aduse. Decizia despre care date trebuie scoase afară este foarte importantă pentru eficiență; ea este politica de înlocuire (replacement policy). Există o sumedenie de politici; iată-le doar numite pe unele; orice carte de sisteme de operare va descrie cele mai multe dintre ele: politica aleatoare (random), politica circulară (round robin), politica ``cel mai rar folosit'' (least frequently used), politica ``primul intrat - primul ieșit'' (first in, first out), politica ``cel mai demult folosit'' (least recently used), politica ``setul de lucru'' (working set), politica ``optimă'' (optimal), politica ceasului, politica celei de-a doua șanse (second-chance).

3)
Politica de scriere: odată cu prezența unui cache, datele efectiv devin duplicate: există o copie în cache. Cînd se fac scrieri, care dintre copii trebuie modificată? Una sau amîndouă? În funcție de circumstanțe există varii răspunsuri la această întrebare.

4)
Metoda de identificare: cînd vreau ceva din memoria lentă indic adresa la care acel obiect se găsește. Principiul transparenței (faptul că interfețele sunt identice) cere ca in cache datele să fie căutate tot după această adresă; dar cum cache-ul este mic, adresele din memoria externă (= memoria lentă) nu reprezintă adrese și în memoria rapidă. Cum găsesc datele? Răspunsul este dat de metoda de identificare și strîns legat de politica de înlocuire, pentru că datele trebuie căutate acolo unde puteau fi aduse.

5)
Timpul de viață al informației: dacă dintre copiile pe care le am (una în cache și alta în memorie) una se schimbă? Care este cea bună după aceea? Ce trebuie să fac cu cealaltă? Cu ce ocazie trebuie făcută schimbarea?

Algoritmul

Schema generală de funcționare a unui cache este descrisă la un nivel abstract de următorul program în C. Aceasta este doar schema generală; în mod normal codul ar trebui să mai facă o grămadă de teste de eroare.

Singurul punct mai interesant este calculul adreselor: dacă împart fișierul în blocuri de mărime MARIME, octetul cu adresa a se va afla în blocul cu numărul a / MARIME în fișier (ATENȚIE: nu și în cache!) și va fi octetul cu numărul a % MARIME în acel bloc. Adresa de început a blocului va fi a - a % MARIME.

De asemenea, împărțirea în proceduri, constantele globale, nu sunt întotdeauna perfect alese; am încercat să păstrez cît mai clară structura esențială.

typedef unsigned char BYTE;

#define DA 1
#define NU 0

#define BLOCURI 20
#define MARIME 1024

struct bloc {
   unsigned int liber:1;      /* e folosit acest bloc? */
   unsigned int modificat:1;  /* e modificat acest bloc? */
   unsigned int adresa;       /* datele din fisier intre adresa si adresa+MARIME-1 */
   BYTE date[MARIME];         /* informatia */
};

typedef int blocnr;

struct cache {
   struct bloc blocuri[BLOCURI];
   int blocuri_libere;
   FILE * fisier;
};

/* Metoda de identificare implementata de `cauta' */
extern blocnr cauta(struct cache *c, unsigned int adresa);

/* Politica de inlocuire implementata de `alege_bloc' */
extern blocnr alege_bloc(struct cache *c, unsigned int adresa);

/* metodele de citire/scriere in fisier */
extern void 
citeste_din_fisier(FILE *f, int pozitie, char * buffer, int cantitate);
extern void
scrie_in_fisier(FILE *f, int pozitie, char * buffer, int cantitate);

static int contine(struct cache * c, blocnr bloc, unsigned int adresa)
/* DA daca blocul indicat contine adresa respectiva */
{
   if (c->blocuri[bloc].liber) return NU;
   if ((c->blocuri[bloc].adresa <= adresa) &&
       (c->blocuri[bloc].adresa + MARIME > adresa)) return DA;
   else return NU;
}

static blocnr aduce(struct cache * c, unsigned int adresa) 
/* gaseste blocul care contine aceasta
   adresa, sau aduce datele cu
   aceasta adresa intr-un bloc */
{
   blocnr bloc;

   bloc = cauta(c, adresa);  /* caut adresa indicata in cache */
   if (! contine(c, bloc, adresa)) {
        if (c->blocuri_libere > 0) {
           bloc = alege_bloc_liber(c);
           c->blocuri[bloc].liber = NU;
           c->blocuri_libere -= 1;
       } else {
           bloc = alege_bloc(c);
           if (c->blocuri[bloc].modificat) {
               scrie_in_fisier(c->fisier,           /* fisier */
                          c->blocuri[bloc].adresa,  /* offset in fis. */
                          c->blocuri[bloc].date,    /* datele */
                          MARIME);                  /* octeti */
               c->blocuri[bloc].modificat = NU;
           }
       }

       /* am facut rost de un bloc in cache; 
          trebuie sa aducem blocul cu octetul respectiv
          de pe memoria externa */
       c->blocuri[bloc].adresa = adresa - adresa % MARIME;
       citeste_din_fisier(c->fisier,                /* fisier */
                          c->blocuri[bloc].adresa,  /* offset in fis. */
                          c->blocuri[bloc].date,    /* datele */
                          MARIME);                  /* octeti */
       c->blocuri[bloc].modificat = NU;
   }
   return bloc;   /* acesta este blocul cu datele */
}

void scrie(struct cache * c, unsigned int adresa, BYTE valoare)
   /* scrie un octet folosind cache-ul */
{
   blocnr bloc;

   bloc = aduce(c, adresa);
   c->blocuri[bloc].date[adresa % MARIME] = valoare;
   c->blocuri[bloc].modificat = DA;
}

BYTE citeste(struct cache * c, unsigned int adresa)
   /* citeste un octet folosind cache-ul */
{
   blocnr bloc;

   bloc = aduce(c, adresa);
   return c->blocuri[bloc].date[adresa % MARIME];
}

Codul de mai sus implementează două proceduri: scrie și citeste. Acestea manipulează structura de date pusă la dispoziție pentru a memora blocuri. Procedura centrală este aduce. Ea caută blocul în cache, dacă nu e scoate unul afară pentru a face loc, și aduce blocul în locul disponibil.

Cei cinci parametri sunt vizibili în cod astfel:

1)
Mărimea blocului: constanta MARIME

2)
Politica de înlocuire: este realizată de funcția alege_bloc(), pe care n-am scris-o. Această funcție va arăta diferit în funcție de politica dorită. De exemplu, pentru a implementa o politică aleatoare, corpul ei, foarte simplu, este:

#include <stdlib.h>  /* pentru rand() */

blocnr alege_bloc(struct cache *c, unsigned int adresa)
{
   return rand() % BLOCURI;
}

blocnr alege_bloc_liber(struct cache *c)
  /* chemata numai cind EXISTA blocuri libere; gaseste unul */
{
   blocnr b;

   for (b=0; b < BLOCURI; b++) if (c->blocuri[b].liber) return b;
}

3)
Politica de scriere este în implementarea de mai sus cea numită write-back; scrierile se produc doar în copia din cache a datelor. [Opusa ei este write-through: cînd am de scris ceva scriu simultan și în memoria lentă. Cîteodată aceste două politici se suplimentează cu regula: no-load-on-write-miss: cînd scrierea nu găsește datele în cache nu le mai încarcă, ci doar scrie pe disc.]

4)
Metoda de identificare este de asemenea neprecizată; ea este treaba funcției cauta(). Cea mai simplă implementare posibilă este probabil căutarea liniară:

blocnr cauta(struct cache *c, unsigned int adresa)
  /* gaseste blocul care contine aceasta adresa */
{
   blocnr b;

   for (b=0; b < BLOCURI; b++) 
     if (contine(c, b, adresa)) return b;

   /* daca nu l-am gasit pot da orice rezultat; 
      oricum se verifica din nou */
   return 0;
}

5)
Datele rămîn în cache-ul acesta pînă sunt scoase afară din lipsă de spațiu. De obicei cache-urile conțin și o procedură care le ``golește'', astfel (numele tradițional este sync, pentru că procedura ``sincronizează'' cache-ul cu memoria lentă):

void goleste(struct cache *c)
  /* salveaza tot */
{
   blocnr b;

   for (b=0; b < BLOCURI; b++) {
      if (!c->blocuri[b].modificat) continue;
      scrie_in_fisier(c->fisier,                /* fisier */
                      c->blocuri[b].adresa,     /* offset in fis. */
                      c->blocuri[b].date,       /* datele */
                      MARIME);                  /* octeti */
      c->blocuri[b].modificat = NU;
   }
}

Cache-ul este aproape complet; Mai trebuie și o procedură de inițializare; ceva de genul:

void initializeaza(struct cache *c, FILE * fisier)
{
   blocnr b;

   c->fisier = fisier;
   for (b=0; b < BLOCURI; b++) 
      c->blocuri[b].liber = DA;
   c->blocuri_libere = BLOCURI;
}

Puține proceduri mai trebuie scrise pentru a putea fi testat; scrie_in_fisier() și
citeste_din_fisier() se pot scrie foarte simplu:

#include <stdio.h>

void citeste_din_fisier(FILE *f, int pozitie, 
                        char * buffer, int cantitate)
{
    fseek(f, (long)pozitie, SEEK_SET);
    fread(buffer, 1/* octet */, cantitate, f);
}

void scrie_in_fisier(FILE *f, int pozitie, 
                     char * buffer, int cantitate)
{
    fseek(f, (long)pozitie, SEEK_SET);
    fwrite(buffer, 1, cantitate, f);
}

Incarnații

Încheiem acest articol cu o listă (incompletă) de aplicații ale cache-urilor.

Cache-ul de disc

Orice sistem de operare modern (mai puțin MS-DOS) are un cache de disc. (Chiar și pentru MS-DOS există smartdrive sau ncache de la Norton). Cache-ul de disc este probabil una din cele mai mari surse de eficiență într-un sistem de operare. Acesta se datorește faptului că diferența între timpul de acces la disc și cel la memorie este uriașă (timpul de acces al unei memorii este de circa 60-70 de nanosecunde, adică 60x10-9, iar timpul de acces al unui disc este de ordinul a 10 milisecunde, adică 10x10-3. Cache-ul de disc este o structură de date care conține un vector de blocuri de mărime egală. Discul este la rîndul lui împărțit în blocuri de aceeași dimensiune. Cînd utilizatorul cere un octet de pe disc, blocul care conține acel octet este încărcat în cache, eventual scoțînd un alt bloc afară.

Din cele 5 puncte de vedere indicate anterior, un cache de disc are următoarele caracteristici:

1)
Mărimea blocului: Blocuri mari (512 octeți - 8 Kb).

2)
Politica de înlocuire: Politica de înlocuire este de obicei: dă-l afară pe cel pe care nu l-am folosit cel mai mult timp (Least Recently Used).

3)
Politica de scriere: Cache-urile de disc sunt în general ``write-back''. Asta înseamnă că atunci cînd se scrie pe disc, modificările sunt făcute doar în cache. Ele sunt mutate pe disc doar cînd blocul respectiv este dat afară, sau cînd acest lucru este cerut explicit de utilizator.

4)
Metoda de identificare: Pentru a găsi un bloc în cache se folosesc algoritmi de hash, care sunt foarte eficienți (nu ne putem permite să intrăm în detalii; orice carte elementară de algoritmi descrie hash-urile).

5)
Timpul de viață al informației din cache: Pentru a preveni catastrofele, sistemele de operare ``golesc'' (scriu toate blocurile modificate) din cache pe disc periodic (de ex. la 30 de secunde).

Cache-ul Microprocesorului

Un microprocesor la 200 de Megahertzi (un Pentium pro, de pildă) are un ciclu de instrucțiune de1/(200x106) = 5 nanosecunde. O instrucțiune poate dura un număr variabil de cicluri, între 1 și cîteva zeci. Executarea unei instrucțiuni înseamnă: citirea ei din memorie, decodificarea, executarea, memorarea rezultatelor. Dacă accesul la memorie durează 60 de nanosecunde atunci la fiecare citire procesorul trebuie să piardă 12 cicluri! Din cauza asta între microprocesor și memoria RAM principală se pune un cache construit din memorie rapidă, cu timp de acces de 5-10 nanosecunde.

Cîteodată designerii pun chiar mai mult decît atît: două nivele de cache între procesor și RAM: un nivel ceva mai lent, dar mai mare (pentru un PC între 64Kb și 512Kb de obicei), și un cache construit chiar în microprocesor, de ordinul a 1-10Kb, mult mai rapid.

Aceste cache-uri se implementează folosind hardware specializat.

1)
Mărimea blocului: blocurile sunt mici 1 - 16 octeți.

2)
Politica de înlocuire si 4) Metoda de identificare:

Există două clase mari de cache-uri de microprocesor, și una intermediară. Ele diferă prin locurile din cache în care un octet din memoria externă poate fi plasat. Cele două mari varietăți sunt: cache-ul cu adresare directă, în care locul fiecărui octet este unul și precis calculat, și cache-ul asociativ, în care un octet din memoria externă poate fi plasat în orice loc din cache.

Cache-ul cu adresare directă (direct mapped)

Figure 3: Cache-ul cu adresare directă
\begin{figure}\centerline{\epsfxsize=13cm\epsffile{direct.eps}}\end{figure}

De obicei chiar structura adresei este folosită la căutare. Figura 3 arată cum este plasat un anume bloc în cache: biții de la sfîrșitul adresei blocului dau și posibila poziție a blocului în cache. Biții din începutul adresei blocului constituie verificarea dacă blocul este cel aflat în cache (mai multe blocuri candidează pentru aceeași poziție; cel care se află înauntru este indicat prin etichetă (tag)).

În fine, ultimii biți din adresă indică poziția octetului în blocul de date.

Marele avantaj al schemei directe este că dată fiind adresa, poziția în cache a blocului este unic determinată, și nu trebuie făcută nici o căutare. Politica de înlocuire nu există din același motiv: nu poți alege în ce loc să aduci un bloc. Din cauza asta funcția de căutare și cea de înlocuire sunt identice.

În termenii codului anterior un exemplu ar fi:

#define BITI_BLOC        4   /* 2^4 octeti in bloc */
#define BITI_ADRESA_BLOC 8   /* 2^8 blocuri in cache */
#define MASCA_BLOC    0xff   /* un nr format din BITI_ADRESA_BLOC biti 1 */
#define BITI_ETICHETA    4 

#define MARIME (1 << BITI_ETICHETA)     /* marimea unui bloc */
#define BLOCURI (1 << BITI_ADRESA_BLOC) /* nr blocuri */

#define BITI_ADRESA (BITI_BLOC + BITI_ADRESA_BLOC + BITI_ETICHETA)
  /* marimea adresei */

blocnr alege_bloc(struct cache *c, unsigned int adresa)
{
   return (adresa >> BITI_BLOC) & MASCA_BLOC;
}

blocnr cauta(struct cache *c, unsigned int adresa)
{
   return alege_bloc(c, adresa);
}

(Pentru eficiență putem rescrie și structura blocului, să păstreze numai eticheta în loc de adresă, și sa facă toate calculele numai cu biți; de exemplu:)

int contine(struct cache * c, blocnr bloc, unsigned int adresa)
/* DA daca blocul indicat contine adresa respectiva */
{
   unsigned int diferenta;

   if (c->blocuri[bloc].liber) return NU;
   diferenta = adresa ^ c->blocuri[bloc].adresa; 
        /* sau exclusiv 'intre adrese */
   diferenta >>= BITI_BLOC; 
        /* arunc adresa octetului */
   if (diferenta == 0)
        /* toti bitii identici (rezultat 0) => acelasi bloc */
        return DA;
   else return NU;
}

Acest fel de operații se implementează foarte repede în hardware.

Cache-ul cu adresare asociativă (fully associative)

Cache-ul cu adresare asociativă se bazează pe un dispozitiv hardware foarte simpatic, care se numește memorie asociativă (din cauza prezenței ei își capătă cache-ul numele).

O memorie obișnuită oferă două operații: (a) dîndu-se o adresă, citește conținutul și (b) dindu-se o adresă și o valoare scrie această valoare acolo.

Pe lîngă aceste operații o memorie asociativă mai oferă încă una: dîndu-se o valoare, poate spune la care adresă se găsește ea. O memorie asociativă nu este tehnologic greu de construit, însă este un dispozitiv relativ costisitor.

Un cache asociativ folosește o memorie asociativă pentru a memora adresele externe ale blocurilor care corespund fiecărui bloc din cache.

Un bloc poate acum ocupa orice poziție în cache; cînd este căutat memoria asociativă spune unde se află.

Politica de înlocuire va fi însă ceva mai complicată, oricare din schemele înșirate fiind un candidat.

Cache-ul parțial asociativ (set-associative)

Putem să ne imaginăm un cache parțial asociativ ca o colecție de mai multe cache-uri directe care lucrează în paralel. Fie k numărul de astfel de cache-uri directe. (un astfel de cache se numește ``associative on k ways'' -- asociativ pe k direcții).

Ideea este simplă: cînd caut o adresă folosesc adresare directă în toate cele k cache-uri directe simultan. Dacă blocul se găsește într-unul am rezolvat problema. Daca nu, aleg unul dintre ele pentru înlocuire. Numele este de ``parțial asociativ'', pentru că plasamentul în cele k blocuri posibile este oricare, ca la un cache asociativ.

Să revenim la discuția privind cache-urile microprocesoarelor.

[3)] Politica de scriere, 5) Timpul de viață al informației din cache: Dacă mai multe microprocesoare sunt legate la aceeași memorie, există riscul ca fiecare să facă modificări în propriul cache, obținînd astfel rezultate eronate, așa cum arată și figura 4. Din cauza asta cache-ul se face adesea ``write-through'': toate modificările se fac simultan în memorie și în cache. Cache-urile monitorizează modificările făcute în memorie de celelalte cache-uri și invalidează copiile datelor pe care le posedă și care au fost modificate. (Un astfel de cache se numește ``snooping cache'': cache care trage cu urechea, să vadă dacă altcineva nu modifică memoria externă.)

Figure 4: Acces prin două cache-uri
\begin{figure}\centerline{\epsfxsize=8cm\epsffile{inconsistenta.eps}}\end{figure}

Cache-ul shell-ului

În Unix (și MS-DOS) o comandă tastată shell-ului (programului command.com) este adesea numele unui fișier. Acest fișier este căutat de shell într-o listă de directoare numită ``path'' (cărare). De pildă, dacă tastez ls (dir în DOS), shell-ul caută un fișier cu numele ls pe rînd (de la dreapta la stînga) în directoarele indicate de variabila PATH (o posibilă valoare este:
/sbin:/usr/sbin:/bin:/usr/bin:/usr/bin/X11:/usr/local/bin:.) Cum găsește un fișier executabil numit ls, îl execută. Shell-ul va găsi pe ls în directorul bin și va ține minte acest lucru.

Operația de căutare este costisitoare, implicînd multe accese la disc. Din cauza asta, de îndată ce un fișier a fost reperat, shell-urile inteligente țin minte unde și nu mai fac a doua oară căutarea. A doua oară cînd voi tasta ls, shell-ul se va duce direct în bin, fără să mai caute. Acesta este tot un cache: în loc să acceseze memoria lentă (discul) shell-ul se uită în structura de date pe care a construit-o.

(Puteți verifica acest lucru: dacă mutați un fișier executabil din locul unde se afla într-un alt director din path, shell-ul nu îl va mai găsi, pentru că nu mai caută lista de directoare o a doua oară. Shell-ul bash afișează conținutului cache-ul intern la comanda hash.)

1)
Mărimea blocului: Un shell ține minte de obicei numai fișierele care au fost folosite; ``blocul'' este perechea nume-loc.

2)
Politica de înlocuire: Cel mai puțin frecvent folosite nume pot fi șterse.

3)
Politica de scriere, 5) Timpul de viață al informației din cache: După cum am văzut, de obicei shell-ul nu dă atenție modificărilor; el ține minte locul unui fișier chiar dacă acest a fost mutat. De obicei shell-ul are o comandă prin care i se spune explicit să uite tot ce a învățat despre fișiere (la shell-ul csh comanda este rehash).

4)
Metoda de identificare: Pentru a găsi locul unui fișier folosește funcții de hash.

Serverele de Nume (``Domain Name Servers'')

Cache-urile sunt extrem de utile în rețelele de calculatoare, în care memoria lentă este un calculator aflat la distanță. Un exemplu foarte interesant în acest context (dar nu singurul posibil) este cel al serverelor de nume.

Ca să facem dintr-o poveste lungă una scurtă, fiecare calculator este identificat printr-o adresă numerică (de pildă 141.85.128.1). Din cauză că astfel de adrese sunt greu de ținut minte, fiecăruia i se atribuie și o adresă ``simbolică'' (de pildă pub.pub.ro). Asta simplifică problema oamenilor, dar nu pe a calculatoarelor, pentru că atunci cînd cineva indică o adresă simbolică trebuie găsită adresa corespunzătoare numerică. Adresele simbolice sunt aranjate (ca și numele directoarelor, numai că se scriu de la dreapta la stînga) într-o ierarhie: pentru a afla adresa lui pub.pub.ro, trebuie să aflăm adresa (numerică) a calculatorului care știe totul despre ro, să-l întrebăm pe acesta cine este cel care știe totul despre pub.ro, care ne va zice la rîndul lui cine este despre pub.pub.ro. Treaba asta cere timp (secunde prețioase).

Din cauza asta, de îndată ce a aflat o pereche de adrese simbolică-numerică, un calculator o păstrează într-un cache local, în ideea că o va mai folosi. Trucul merge pentru că adresele se schimbă foarte rar.

1)
Mărimea blocului: Blocul este o pereche (nume simbolic-adresa).

2)
Politica de înlocuire: LRU este un candidat bun.

3)
Politica de scriere: Această informație este practic ``read-only'': un utilizator nu poate schimba adresa unui calculator; nu se pune problema scrierii. (Cu alte cuvinte memoria lentă este ``read-only'').

4)
Metoda de identificare: Identificarea se face tot cu funcții de hash.

5)
Timpul de viață al informației din cache: Pentru a permite adaptarea la schimbări de adrese, fiecare pereche de adrese are un ``timp de viață'', de ordinul săptămînilor. După ce timpul de viață expiră, informația este ștearsă din cache. În acest fel, dacă adresa unui calculator se schimbă, celelalte vor afla acest lucru la un moment dat.

Clienții de WWW

Dacă ați folosit Netscape (sau Internet explorer sau Mosaic), ați observat că la apăsarea butonului ``back'', care vă mută la documentul pe care l-ați vizionat înaintea celui curent, afișarea se face mult mai repede decît prima oară cînd l-ați văzut. Explicația este simplă: clientul de web (Netscape, etc.) face pe discul local un cache în care ține minte ultimele documente pe care le-ați văzut (în directorul .netscape/cache de obicei. Pune acolo în fișiere toate paginile recente, figurile aduse și ce-o mai fi. Asta pentru că (de obicei) e mult mai rapidă citirea de pe discul local decît transferul din rețea.

1)
Mărimea blocului: Unitatea de memorare (blocul) este în acest caz fișierul (fie el pagina html, figură gif sau document postscript).

2)
Politica de înlocuire: Probabil LRU.

3)
Politica de scriere: În principiu clientul de web poate doar citi datele; din cauza asta politica de scriere nu există.

4)
Metoda de identificare: Identificarea prezenței unui document în cache se face după URL-ul lui (Universal Resource Locator). În lume nu pot exista două documente cu același URL. Căutarea este probabil o simplă căutare într-un vector ne-ordonat, care conține lista URL-urilor prezente în cache, combinată cu un hash parțial după prima literă (uitați-vă la directorul indicat).

5)
Timpul de viață al informației din cache: Dacă informația pe care o citiți cu clientul de web se schimbă la sursă, clientul nu-și va da seama, și vă va arăta tot ce are în cache. Puteți să-l forțați să recitească datele de la sursă apăsînd pe butonul ``reload''.

Memoria Virtuală

Memoria virtuală este un mecanism prezent în orice sistem modern de operare. Prin acest mecanism se pot executa programe mai mari decît încap în memorie. Ideea este de a ține programele pe disc, și de a aduce în memoria RAM a calculatorului numai partea de program care tocmai se execută. Figura 5 ilustrează acest lucru.

Figure 5: Memoria virtuală
\begin{figure}\centerline{\epsfxsize=8cm\epsffile{virtual.eps}}\end{figure}

Sună familiar, nu? Este tocmai comportarea unui cache, dacă stăm să ne gîndim bine! Tot ce am discutat despre cache-uri se aplică și în acest caz.

1)
Mărimea blocului: Blocurile sunt numite în acest caz pagini, și au dimensiuni tipice de 1Kb-8Kb (la Pentium 4Kb).

2)
Politica de înlocuire: Politica cea mai des folosită este o variantă a politicii ``setului de lucru'' (WS), care pe engleză are împămîntenit numele de WSCLOCK. Pe scurt politica funcționează astfel:

3)
Politica de scriere: Write-back.

4)
Metoda de identificare: Identificarea poziției în RAM a unei adrese virtuale se face folosind hardware specializat (Unitatea de Management a Memoriei) care ține ``tabele de pagini''. Tabelele de pagini descriu pentru fiecare pagină de adrese virtuale pagina fizică ce-i corespunde. (Tabelele arată cîteodată ca niște arbori, dar deja am aluneca prea departe cu detaliile).

5)
Timpul de viață al informației din cache: Paginile pot fi modificate numai cînd se află în memoria fizică (RAM).

``Translation Lookaside Buffer'' (TLB)

Din păcate nu cunosc nici o traducere a termenului, așa că îl voi folosi cu numele englezesc. TLB este un dispozitiv folosit pentru a implementa memoria virtuală.

Memoria virtuală se bazează pe traducerea fiecărei adrese pe care un program o generează într-o altă adresă. (Revedeți figura 5). Traducerea se face căutînd într-o tabelă mare, care ține pentru fiecare adresă virtuală adresa din RAM (sau de pe disc) corespunzătoare. Problema este că tabela însăși trebuie să fie stocată în memorie.

În felul acesta la fiecare acces la memorie se fac două accese: unul în care se caută în tabelă, și unul în care se iau datele de la adresa indicată de tabelă. Vedeți și figura 6.

Figure 6: Traducerea adresei
\begin{figure}\centerline{\epsfxsize=5cm\epsffile{tlb.eps}}\end{figure}

Pentru că nu are sens să faci două accese pentru unul singur, se construiește un cache cu cele mai folosite adrese virtuale și traducerile lor. Acest cache se numește TLB.

Adresarea se face atunci astfel: întîi se încearcă drumul (1) din figură, căutînd adresa în TLB. Doar dacă nu e acolo căutăm și în tabela de pagini, pe varianta (2).

1)
Mărimea blocului: Un bloc este o pereche de adrese virtuală-fizică.

2)
Politica de înlocuire: LRU probabil.

3)
Politica de scriere, 5) Timpul de viață al informației din cache: Cînd translatarea virtual-fizic se schimbă (de pildă cînd o pagină este înlocuită), informația din TLB nu mai este corectă. Soluția este de obicei ștergerea întregului conținut al TLB.

4)
Metoda de identificare: folosind memorii asociative.