Pseudo-LRU - Pseudo-LRU

Pseudo-LRU nebo PLRU je rodina algoritmy mezipaměti které zlepšují výkon systému Nejméně uživaný v poslední době Algoritmus (LRU) nahrazením hodnot pomocí přibližných měřítek věku místo zachování přesného stáří každé hodnoty v mezipaměti.

PLRU obvykle odkazuje na dva algoritmy nahrazení mezipaměti: strom-PLRU a bit-PLRU.

Strom-PLRU

Tree-PLRU je efektivní algoritmus vybrat položku, která s největší pravděpodobností nebyla nedávno zpřístupněna, vzhledem k sadě položek a posloupnosti událostí přístupu k položkám.

Tato technika se používá v Mezipaměť CPU z Intel 486 a v mnoha procesorech v PowerPC rodina, jako např Freescale's PowerPC G4 používá Počítač Apple.

Algoritmus funguje následovně: zvažte a binární vyhledávací strom pro dotyčné položky. Každý uzel stromu má jednobitový příznak označující „jít doleva k vyhledání prvku pseudo-LRU“ nebo „jít doprava k nalezení prvku pseudo-LRU“. Chcete-li najít prvek pseudo-LRU, projděte strom podle hodnot příznaků. Chcete-li aktualizovat strom s přístupem k položce N, projděte strom a vyhledejte N a během procházení nastavte příznaky uzlu k označení směru, který je opačný ke zvolenému směru.

Pseudo LRU funguje

Tento algoritmus může být neoptimální, protože se jedná o aproximaci. Například ve výše uvedeném diagramu s řádky mezipaměti A, C, B, D, pokud byl přístupový vzor: C, B, D, A, při vystěhování bychom místo B zvolili B. Je to proto, že A i C jsou ve stejné polovině a přístup A směruje algoritmus na druhou polovinu, která neobsahuje řádek mezipaměti C.

Bit-PLRU

Bit-PLRU ukládá jeden stavový bit pro každou linku mezipaměti. Tyto bity se nazývají MRU-bity. Každý přístup k lince nastavuje jeho bit MRU na 1, což naznačuje, že linka byla nedávno použita. Kdykoli je posledních zbývajících 0 bitů stavových bitů sady nastaveno na 1, všechny ostatní bity jsou resetovány na 0. Při vynechání mezipaměti je nahrazen řádek úplně vlevo, jehož bit MRU je 0. [1]

Viz také

Reference

  1. ^ Automatické generování modelů mikroarchitektur