Algoritm fără memorie cache - Cache-oblivious algorithm

În calcul , un algoritm de memorie cache (sau algoritm transcendent de cache) este un algoritm conceput pentru a profita de un cache de procesor fără a avea dimensiunea cache-ului (sau lungimea liniilor de cache etc.) ca parametru explicit. Un algoritm optim de memorie cache este un algoritm de memorie cache care folosește memoria cache în mod optim (într-un sens asimptotic , ignorând factorii constanți). Astfel, un algoritm care nu ține cont de cache este conceput pentru a funcționa bine, fără modificări, pe mai multe mașini cu dimensiuni diferite de cache sau pentru o ierarhie de memorie cu niveluri diferite de cache cu dimensiuni diferite. Algoritmii fără memorie cache sunt contrastați cu blocarea explicită , ca și în optimizarea cuiburilor , care împarte în mod explicit o problemă în blocuri care sunt dimensionate optim pentru o memorie cache dată.

Algoritmi Optimal-cache orb sunt cunoscute pentru matrice de multiplicare , transpunere matrice , sortarea și alte câteva probleme. Unii algoritmi mai generali, cum ar fi Cooley-Tukey FFT , sunt în mod optim ignorând memoria cache în anumite alegeri de parametri. Deoarece acești algoritmi sunt optimi numai în sens asimptotic (ignorând factorii constanți), poate fi necesară o reglare specifică mașinii pentru a obține performanțe aproape optime în sens absolut. Scopul algoritmilor fără memorie cache este de a reduce cantitatea de reglare necesară.

În mod obișnuit, un algoritm fără memorie cache funcționează printr-un algoritm recursiv de divizare și cucerire , în care problema este împărțită în subprobleme din ce în ce mai mici. În cele din urmă, se ajunge la o dimensiune de subproblemă care se potrivește în cache, indiferent de dimensiunea cache-ului. De exemplu, o înmulțire optimă a matricei fără memorie cache este obținută prin împărțirea recursivă a fiecărei matrice în patru sub-matrici care urmează să fie înmulțite, înmulțind submatricele într-o manieră de adâncime . În reglarea pentru o anumită mașină, se poate utiliza un algoritm hibrid care folosește blocarea reglată pentru dimensiunile cache specifice la nivelul inferior, dar în caz contrar se folosește algoritmul care nu ține cont de cache.

Istorie

Ideea (și numele) algoritmilor care nu- și ascund cache-ul a fost concepută de Charles E. Leiserson încă din 1996 și publicată pentru prima dată de Harald Prokop în teza de masterat de la Institutul de Tehnologie din Massachusetts în 1999. Au existat mulți predecesori, care de obicei analizează probleme specifice. ; acestea sunt discutate în detaliu în Frigo și colab. 1999. Exemplele timpurii citate includ Singleton 1969 pentru o transformare recursivă rapidă Fourier, idei similare în Aggarwal și colab. 1987, Frigo 1996 pentru multiplicarea matricii și descompunerea LU și Todd Veldhuizen 1996 pentru algoritmii matriciali din biblioteca Blitz ++ .

Model de cache idealizat

Algoritmii fără memorie cache sunt de obicei analizați utilizând un model idealizat al memoriei cache, numit uneori modelul fără memorie cache . Acest model este mult mai ușor de analizat decât caracteristicile unui cache real (care au asociativitate complicată, politici de înlocuire etc.), dar, în multe cazuri, se poate dovedi într-un factor constant al performanței unui cache mai realist. Este diferit de modelul de memorie externă, deoarece algoritmii care nu cunosc memoria cache nu cunosc dimensiunea blocului sau dimensiunea cache- ului.

În special, modelul care nu conține cache este o mașină abstractă (adică un model teoretic de calcul ). Este similar cu modelul mașinii RAM care înlocuiește banda infinită a mașinii Turing cu o matrice infinită. Fiecare locație din matrice poate fi accesată în timp, similar cu memoria cu acces aleatoriu de pe un computer real. Spre deosebire de modelul mașinii RAM, introduce și un cache: un al doilea nivel de stocare între RAM și CPU. Celelalte diferențe dintre cele două modele sunt enumerate mai jos. În modelul de memorie cache: ${\ displaystyle O (1)}$

Memoria cache din stânga conține blocuri de dimensiuni fiecare, pentru un total de M obiecte. Memoria externă din dreapta este nelimitată.${\ displaystyle {\ tfrac {M} {B}}}$${\ displaystyle B}$

• Memoria este împărțită în blocuri de obiecte fiecare.${\ displaystyle B}$
• O încărcare sau un depozit între memoria principală și un registru CPU pot fi acum deservite din cache.
• Dacă o încărcare sau un magazin nu poate fi reparat din cache, se numește cache miss .
• O lipsă de cache duce la încărcarea unui bloc din memoria principală în cache. Și anume, dacă CPU încearcă să acceseze cuvânt și este linia care conține , atunci este încărcat în cache. Dacă memoria cache a fost anterior plină, atunci va fi evacuată și o linie (a se vedea politica de înlocuire de mai jos).${\ displaystyle w}$${\ displaystyle x}$${\ displaystyle w}$${\ displaystyle x}$
• Cache-ul conține obiecte, unde . Acest lucru este, de asemenea, cunoscut sub numele de presupunerea cache-ului înalt .${\ displaystyle M}$${\ displaystyle M = \ Omega (B ^ {2})}$
• Cache-ul este complet asociativ: fiecare linie poate fi încărcată în orice locație din cache.
• Politica de înlocuire este optimă. Cu alte cuvinte, se presupune că cache-ului i se oferă întreaga secvență de accesări de memorie în timpul executării algoritmului. Dacă trebuie să evacueze o linie la timp , va analiza succesiunea cererilor sale viitoare și va evacua linia care este accesată cel mai departe în viitor. Acest lucru poate fi imitat în practică cu politica „ Cel mai recent folosit ”, care se dovedește a fi în cadrul unui mic factor constant al strategiei de înlocuire optimă offline.${\ displaystyle t}$

Pentru a măsura complexitatea unui algoritm care se execută în cadrul modelului de memorie cache, măsurăm numărul de rate de cache pe care le experimentează algoritmul. Deoarece modelul surprinde faptul că accesarea elementelor din cache este mult mai rapidă decât accesarea lucrurilor din memoria principală , durata de funcționare a algoritmului este definită doar de numărul de transferuri de memorie dintre cache și memoria principală. Acest lucru este similar cu modelul de memorie externă , care are toate caracteristicile de mai sus, dar algoritmii care nu conțin cache sunt independenți de parametrii cache ( și ). Avantajul unui astfel de algoritm este că ceea ce este eficient pe o mașină fără memorie cache este probabil să fie eficient pe multe mașini reale, fără reglarea fină a anumitor parametri reali ai mașinii. Pentru multe probleme, un algoritm optim de memorie cache va fi, de asemenea, optim pentru o mașină cu mai mult de două niveluri de ierarhie a memoriei . ${\ displaystyle B}$${\ displaystyle M}$

Exemple

Ilustrația ordinii majore în rânduri și coloane

Cel mai simplu algoritm de memorie cache prezentat în Frigo și colab. este o operațiune de transpunere a matricei în afara locului (algoritmi în loc au fost de asemenea concepuți pentru transpunere, dar sunt mult mai complicate pentru matricele care nu sunt pătrate). Dată fiind m × n matrice A și n × m matrice B , am dori să stocheze transpusa A în B . Soluția naivă traversează o matrice în ordine rând-major și alta în coloană-major. Rezultatul este că, atunci când matricile sunt mari, obținem o pierdere a memoriei cache la fiecare etapă a traversării coloanei. Numărul total de rateuri cache este . ${\ displaystyle \ Theta (mn)}$

Principiul algoritmului fără memorie cache pentru transpunerea matricei utilizând o abordare de divizare și cucerire. Graficul prezintă pasul recursiv ( a → b ) al împărțirii matricei și al transpunerii fiecărei părți individual.

Algoritmul fără memorie cache are o complexitate optimă de lucru și o complexitate optimă a memoriei cache . Ideea de bază este de a reduce transpunerea a două matrice mari în transpunerea (sub) matricilor mici. Facem acest lucru împărțind matricile în jumătate de-a lungul dimensiunii lor mai mari până când trebuie doar să efectuăm transpunerea unei matrice care se va potrivi în cache. Deoarece dimensiunea cache-ului nu este cunoscută de algoritm, matricile vor continua să fie împărțite recursiv chiar și după acest punct, dar aceste subdiviziuni suplimentare vor fi în cache. Odată ce dimensiunile m și n sunt suficient de mici, astfel încât o matrice de intrare de dimensiune și o matrice de ieșire de dimensiune să se potrivească în cache, atât traversările rând-majore, cât și coloanele majore duc la lipsă de lucru și cache. Prin utilizarea acestei abordări de divizare și cucerire, putem atinge același nivel de complexitate pentru matricea generală. ${\ displaystyle O (mn)}$${\ displaystyle O (1 + mn / B)}$${\ displaystyle m \ times n}$${\ displaystyle n \ times m}$${\ displaystyle O (mn)}$${\ displaystyle O (mn / B)}$

(În principiu, s-ar putea continua împărțirea matricilor până când se ajunge la un caz de bază de dimensiunea 1 × 1, dar în practică se folosește un caz de bază mai mare (de exemplu, 16 × 16) pentru a amortiza cheltuielile generale ale apelurilor recursive de subrutină.)

Majoritatea algoritmilor fără memorie cache se bazează pe o abordare de împărțire și cucerire. Acestea reduc problema, astfel încât să se încadreze în cache, indiferent de cât de mică este cache-ul, și încetează recursivitatea la o dimensiune mică determinată de funcția-overhead de apel și de optimizări similare care nu au legătură cu cache-ul, apoi utilizează un acces eficient cache model pentru a îmbina rezultatele acestor mici probleme rezolvate.

La fel ca sortarea externă în modelul de memorie externă , sortarea fără memorie cache este posibilă în două variante: funnelsort , care seamănă cu mergesort și sortare de distribuție fără memorie cache , care seamănă cu quicksort . La fel ca și colegii lor de memorie externă, ambii ating un timp de funcționare de , care se potrivește cu o limită inferioară și este astfel asimptotic optim . ${\ displaystyle O \ left ({\ tfrac {N} {B}} \ log _ {\ tfrac {M} {B}} {\ tfrac {N} {B}} \ right)}$

Vezi si

• Sortare de distribuție fără memorie
• Algoritm de memorie externă
• Funnelsort

Referințe