Pre-preluare cache - Cache prefetching

Pre- preluarea cache-ului este o tehnică utilizată de procesoarele de computer pentru a spori performanța de execuție prin preluarea instrucțiunilor sau datelor din stocarea lor originală în memorie mai lentă într-o memorie locală mai rapidă înainte ca aceasta să fie efectiv necesară (de unde și termenul „pre-preluare”). Majoritatea procesoarelor moderne de computer au memorie cache rapidă și locală, în care datele pre-preluate sunt păstrate până când sunt necesare. Sursa pentru operația de preluare este de obicei memoria principală . Datorită designului lor, accesarea memoriilor cache este de obicei mult mai rapidă decât accesarea memoriei principale , astfel încât preluarea datelor și accesarea acestora din cache sunt de obicei mai multe ordine de mărime mai rapide decât accesarea acestora direct din memoria principală . Pre-preluarea se poate face cu instrucțiuni de control cache care nu blochează .

Pre-preluare cache de date vs. instrucțiuni

Pre-preluarea memoriei cache poate prelua date sau instrucțiuni în memoria cache.

Pre- preluarea datelor preia date înainte de a fi necesare. Deoarece modelele de acces la date prezintă mai puțină regularitate decât modelele de instrucțiuni, preluarea precisă a datelor este în general mai dificilă decât preluarea preinstrucțiunii.

Pre- preluarea instrucțiunilor preia instrucțiuni înainte ca acestea să fie executate. Primii microprocesoare de masă care au folosit o formă de preinstrucțiune au fost Intel 8086 (șase octeți) și Motorola 68000 (patru octeți). În ultimii ani, toate procesoarele de înaltă performanță folosesc tehnici de preluare.

Pre-preluare cache hardware și software

Pre-preluarea memoriei cache poate fi realizată fie prin hardware, fie prin software.

Pre-preluarea bazată pe hardware se realizează de obicei prin intermediul unui mecanism hardware dedicat în procesor care urmărește fluxul de instrucțiuni sau date solicitate de programul de execuție, recunoaște următoarele elemente de care ar putea avea nevoie programul pe baza acestui flux și preinstalează în memoria cache a procesorului .

Pre-preluarea bazată pe software se realizează de obicei prin solicitarea compilatorului de a analiza codul și de a insera instrucțiuni suplimentare de „pre-preluare” în program în timpul compilării.

Metode de preluare hardware

Tampoane de flux

Tampoanele de flux au fost dezvoltate pe baza conceptului de „schemă one block lookahead (OBL)” propus de Alan Jay Smith .
Bufferele de flux sunt una dintre cele mai comune tehnici de preluare bazate pe hardware utilizate. Această tehnică a fost propusă inițial de Norman Jouppi în 1990 și multe variante ale acestei metode au fost dezvoltate de atunci. Ideea de bază este că adresa de pierdere a memoriei cache (și adresele ulterioare) sunt preluate într-un tampon separat de adâncime . Acest buffer se numește buffer de flux și este separat de cache. Procesorul consumă apoi date / instrucțiuni din buffer-ul fluxului dacă adresa asociată cu blocurile pre-preluate se potrivește cu adresa solicitată generată de programul care execută pe procesor. Figura de mai jos ilustrează această configurare: ${\ displaystyle k}$ ${\ displaystyle k}$

O configurație tipică de tampon de flux, așa cum a fost propusă inițial de Norman Jouppi în 1990

Ori de câte ori mecanismul de preluare detectează o eroare pe un bloc de memorie, să zicem A, acesta alocă un flux pentru a începe preluarea blocurilor succesive din blocul ratat în continuare. Dacă memoria tampon de flux poate conține 4 blocuri, atunci am prefixa A + 1, A + 2, A + 3, A + 4 și le vom menține pe cele din memoria tampon de flux alocată. Dacă procesorul consumă A + 1 în continuare, atunci acesta va fi mutat „în sus” din memoria tampon de flux în memoria cache a procesorului. Prima intrare a bufferului de flux ar fi acum A + 2 și așa mai departe. Acest model de preluare a blocurilor succesive se numește Pre-preluare secvențială . Se utilizează în principal atunci când locurile adiacente urmează să fie pre-preluate. De exemplu, se folosește la preluarea instrucțiunilor.
Acest mecanism poate fi extins prin adăugarea mai multor astfel de „buffere de flux” - fiecare dintre acestea ar menține un flux separat de preluare. Pentru fiecare nouă ratare, ar exista un nou buffer de flux alocat și ar funcționa într-un mod similar, așa cum este descris mai sus.
Adâncimea ideală a bufferului de flux este ceva care poate fi experimentat în funcție de diferitele etaloane și depinde de restul microarhitecturii implicate.

Un alt model de instrucțiuni de preluare preliminară este de a prelua adrese care sunt adrese dinainte în secvență. Este utilizat în principal atunci când blocurile consecutive care urmează să fie pre-preluate sunt adrese separate. Aceasta este denumită Stretch Prefetching. ${\ displaystyle s}$ ${\ displaystyle s}$

Metode de preluare software

Pre-preluare direcționată de compilator

Pre-preluarea direcționată de compilator este utilizată pe scară largă în buclele cu un număr mare de iterații. În această tehnică, compilatorul prezice ratările viitoare ale memoriei cache și introduce o instrucțiune de preluare bazată pe pedeapsa ratată și timpul de execuție al instrucțiunilor.

Aceste prefete sunt operații de memorie care nu blochează, adică aceste accesări de memorie nu interferează cu accesele de memorie reale. Acestea nu modifică starea procesorului și nu provoacă defecțiuni la pagină.

Un avantaj principal al preluării software-ului este că reduce numărul de cache-uri obligatorii ratate.

Următorul exemplu arată cum va fi adăugată o instrucțiune de preluare într-un cod pentru a îmbunătăți performanța cache .

Luați în considerare o buclă for așa cum se arată mai jos:

for (int i=0; i<1024; i++) {
    array1[i] = 2 * array1[i];
}

La fiecare iterație, I - ^lea element al matrice „matrice1“ este accesat. Prin urmare, putem prelua elementele care urmează să fie accesate în iterații viitoare prin inserarea unei instrucțiuni „prefetch” așa cum se arată mai jos:

for (int i=0; i<1024; i++) {
    prefetch (array1 [i + k]);
    array1[i] = 2 * array1[i];
}

Aici, pasul de preluare depinde de doi factori, penalizarea ratată a memoriei cache și timpul necesar pentru a executa o singură iterație a buclei for . De exemplu, dacă o iterație a buclei durează 7 cicluri pentru a se executa, iar penalizarea ratată a cache-ului este de 49 de cicluri, atunci ar trebui să avem - ceea ce înseamnă că preluăm 7 elemente înainte. Cu prima iterație, voi fi 0, așa că preluăm cel de-al 7-lea element. Acum, cu acest aranjament, primele 7 accesări (i = 0-> 6) vor fi în continuare ratate (în ipoteza simplificatoare că fiecare element al matricei 1 se află într-o linie cache separată). ${\ displaystyle k}$ ${\ displaystyle k = 49/7 = 7}$

Comparație de preluare hardware și software

În timp ce preluarea software necesită intervenția programatorului sau a compilatorului , preluarea hardware necesită mecanisme hardware speciale.
Pre-preluarea software-ului funcționează bine numai cu bucle în care există acces regulat la matrice, deoarece programatorul trebuie să codeze manual instrucțiunile de pre-preluare. În timp ce pre-prelucratoarele hardware funcționează dinamic pe baza comportamentului programului în timpul rulării .
Pre-preluarea hardware are, de asemenea, mai puțină cheltuială a procesorului în comparație cu pre-preluarea software-ului.

Valori de preluare cache

Există trei valori principale pentru a evalua preluarea cache

Acoperire

Acoperirea este fracția din totalul ratărilor care sunt eliminate din cauza pre-preluării, adică

${\ displaystyle Coverage = {\ frac {\ text {Cache Misses eliminate by Prefetching}} {\ text {Total Cache Misses}}}}$ ,

Unde, ${\ displaystyle {\ text {Total Cache Misses}} = ({\ text {Cache ratează eliminate prin preluare}}) + ({\ text {Memorări cache nu sunt eliminate prin preluare}})}}$

Precizie

Acuratețea este fracția din totalul prefetchelor care au fost utile - adică raportul dintre numărul de adrese de memorie preluate au fost de fapt referențiat de program la totalul prefetchelor efectuate.

${\ displaystyle {\ text {Prefetch Accuracy}} = {\ frac {\ text {Cache Misses eliminat prin preluare}} {({\ text {Useless Cache Prefetches}}) + ({\ text {Cache Misses eliminat prin pre-preluare) })}}}$

Deși se pare că a avea o precizie perfectă ar putea implica faptul că nu există rateuri, nu este cazul. Prefixările în sine ar putea duce la noi rate dacă blocurile pre-preluate sunt plasate direct în cache. Deși acestea pot fi o mică parte din numărul total de ratări pe care le-am putea vedea fără nici o preluare, acesta este un număr de zero ratări.

Actualitatea

Definiția calitativă a oportunității este cât de devreme este preluat un bloc față de momentul în care este de fapt referențiat. Un exemplu pentru a explica în continuare oportunitatea este următorul:

Luați în considerare o buclă for în care fiecare iterație durează 3 cicluri pentru a se executa și operațiunea „prefetch” durează 12 cicluri. Acest lucru implică faptul că pentru ca datele pre-preluate să fie utile, trebuie să începem iterațiile de pre- preluare înainte de a fi utilizate pentru a menține actualitatea. ${\ displaystyle 12/3 = 4}$

Languages

In other projects