Algoritmi de stocare în cache ( algoritmi de preempțiune , politici de preempțiune și „algoritmi/politici de înlocuire”) - în informatică , aceasta este optimizarea instrucțiunilor : un program special de calculator sau o structură suportată de hardware care poate gestiona memoria cache a informațiilor stocate într-un computer. Când memoria cache este plină, algoritmul trebuie să aleagă ce anume trebuie să fie eliminat din el pentru a putea scrie (în cache) informații noi, mai actualizate. Implementarea hardware a acestor algoritmi implică utilizarea unui temporizator , contor sau o combinație a ambelor.
„Rata de accesare” din cache se referă la cât de des sunt găsite datele pe care le căutați în cache. Politicile de evacuare mai eficiente țin evidența acceselor la cele mai utilizate informații pentru a îmbunătăți ratele de accesare (pentru aceeași dimensiune a memoriei cache).
„Latența” cache se referă la cât de repede poate returna cache-ul datele solicitate imediat după solicitare (în cazul în care apare o „lovitură”). Strategiile de evacuare mai rapide țin evidența informațiilor cel mai puțin utilizate – sau, în cazul unui cache mapat direct, lipsa informațiilor – pentru a reduce timpul necesar pentru actualizarea informațiilor.
Fiecare strategie de deplasare este un compromis între rata de lovituri și latență.
Cea mai eficientă regulă de evacuare este eliminarea informațiilor din cache care nu vor fi necesare cel mai mult timp în viitor. Acest algoritm optim de stocare în cache a fost numit algoritmul Beladi sau algoritmul de previziune . Întrucât în cazul general este imposibil de prezis când exact această informație va fi necesară data viitoare, în practică (din nou, în cazul general) o astfel de implementare este imposibilă. Minimul practic poate fi calculat doar empiric, după care eficiența algoritmului actual de caching poate fi comparată cu acesta.
Utilizat cel mai puțin recent (LRU): În primul rând, cel mai lung neutilizat este deplasat. Acest algoritm necesită urmărirea a ceea ce a fost folosit și când, ceea ce poate fi destul de costisitor, mai ales dacă trebuie să faceți o verificare suplimentară pentru a vă asigura. Implementarea generală a acestei metode necesită păstrarea unui „bit de vârstă” pentru liniile cache și, prin aceasta, ține evidența celor mai puțin utilizate linii (adică prin compararea acestor biți). Într-o astfel de implementare, de fiecare dată când este accesată o linie cache, „vârsta” tuturor celorlalte linii se schimbă. LRU este de fapt o familie de algoritmi de stocare în cache care include 2Q de Theodore Johnson și Dennis Schasha și LRU/K de Pat O'Neill, Betty O'Neill și Gerhard Weikum.
Cel mai recent folosit (MRU): spre deosebire de LRU, cel mai recent articol folosit este evacuat mai întâi. Potrivit sursei [1] , „Când un fișier este scanat periodic într-un mod round robin, MRU este cel mai bun algoritm de evacuare”. În [2] , autorii subliniază, de asemenea, că pentru schemele de acces aleatoriu și scanarea ciclică a seturilor mari de date (uneori numite scheme round robin), algoritmii de stocare în cache MRU au mai multe rezultate în comparație cu LRU datorită tendinței lor de a păstra datele vechi. Algoritmii MRU sunt cei mai utili în cazurile în care cu cât elementul este mai vechi, cu atât apar mai multe accesări la acesta.
Pseudo-LRU (PLRU): Pentru cache-urile cu asociativitate mare (de obicei mai mult de 4 canale), resursele necesare pentru implementarea LRU devin prea mari. Dacă politica este suficientă pentru a elimina aproape întotdeauna cea mai puțin utilizată intrare, atunci algoritmul PLRU poate fi utilizat în acest caz, necesitând doar un bit per intrare în cache.
LRU segmentat (sau SLRU): „Cache-ul SLRU este împărțit în două segmente: un segment de probă și un segment protejat. Liniile din fiecare segment sunt ordonate de la cele mai utilizate la cele mai puțin utilizate. Datele despre rateuri sunt adăugate în cache și în zona ultimelor elemente utilizate ale segmentului de încercare. Datele despre accesări sunt eliminate oriunde se află și adăugate în zona elementelor utilizate frecvent din segmentul protejat. Rândurile de segmente protejate sunt astfel accesate de cel puțin două ori. Segmentul protejat este limitat. Un astfel de transfer de linie de la segmentul de încercare la segmentul protejat poate determina ca ultimul rând utilizat (LRU) din segmentul protejat să fie transferat în zona MRU a segmentului de încercare, oferind acelei linii o a doua șansă de a fi utilizată înainte de a fi utilizată. evacuat. Dimensiunea segmentului protejat este un parametru SLRU care variază în funcție de schema I/O. Ori de câte ori datele trebuie evacuate din cache, rândurile sunt solicitate de la capătul LRU al segmentului de sondă. [3] »
Asociativitatea bidirecțională se aplică cache-urilor procesoarelor de mare viteză , unde chiar și PLRU-ul este prea lent. Adresa noului element este folosită pentru a calcula una dintre cele două locații posibile din cache (în zona alocată pentru aceasta). Conform algoritmului LRU, două elemente sunt deplasate. Este nevoie de un bit pentru câteva linii de cache pentru a indica care dintre ele au fost utilizate ultima dată.
Direct Mapped Cache : Pentru memoria cache a procesoarelor de mare viteză, unde performanța caching-ului asociativ în 2 căi lipsește. Adresa noului element este folosită pentru a calcula locația în cache (în zona alocată pentru aceasta). Tot ce era înainte este înlocuit.
Utilizat cel mai puțin frecvent (LFU): LFU numără cât de des este utilizat un element. Acele elemente care sunt accesate cel mai puțin des sunt preemptate primele.
Adaptive Replacement Cache (ARC): [4] echilibrează constant între LRU și LFU, ceea ce îmbunătățește rezultatul final.
Algoritm de stocare în cache Multi Queue (MQ) : [5] (dezvoltat de Y. Zhu, J. F. Philbin și Kai Li).
Sunt luate în considerare următoarele puncte:
Există, de asemenea, diverși algoritmi pentru a asigura coerența cache -ului . Acest lucru se aplică numai în cazurile în care sunt folosite mai multe cache independente pentru a stoca aceleași informații (de exemplu, mai multe servere de baze de date actualizează un fișier de date comun).