Pseudo-LRU

Pseudo-LRU

Pseudo-LRU (also known as Tree-LRU, LRU meaning "least recently used") is an efficient algorithm to find an item that most likely has not been accessed very recently, given a set of items and a sequence of access events to the items. This technique is used in the CPU cache of the Intel 486 and in many processors in the Power Architecture (formerly PowerPC) family, such as Freescale's PowerPC G4 used by Apple Computer.

The algorithm works as follows: consider a binary search tree for the items in question. Each node of the tree has a one-bit flag denoting "go left to find a pseudo-LRU element" or "go right to find a pseudo-LRU element". To find a pseudo-LRU element, traverse the tree according to the values of the flags. To update the tree with an access to an item N, traverse the tree to find N and, during the traversal, set the node flags to denote the direction that is opposite to the direction taken.

ee also

* Cache algorithms


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Algorithmes De Remplacement Des Lignes De Cache — Il existe différents types de mémoire cache, dont l organisation amène des situations où une ligne de la mémoire principale est mappé sur un ensemble de lignes de mémoire cache remplie. Il faut donc choisir la ligne de mémoire cache qui sera… …   Wikipédia en Français

  • Algorithmes de remplacement des lignes de cache — Il existe différents types de mémoire cache, dont l organisation amène des situations où une ligne de la mémoire principale est mappée sur un ensemble de lignes de mémoire cache remplie. Il faut donc choisir la ligne de mémoire cache qui sera… …   Wikipédia en Français

  • LRR — Algorithmes de remplacement des lignes de cache Il existe différents types de mémoire cache, dont l organisation amène des situations où une ligne de la mémoire principale est mappé sur un ensemble de lignes de mémoire cache remplie. Il faut donc …   Wikipédia en Français

  • Least Frequently Used — Algorithmes de remplacement des lignes de cache Il existe différents types de mémoire cache, dont l organisation amène des situations où une ligne de la mémoire principale est mappé sur un ensemble de lignes de mémoire cache remplie. Il faut donc …   Wikipédia en Français

  • PLRUt — Algorithmes de remplacement des lignes de cache Il existe différents types de mémoire cache, dont l organisation amène des situations où une ligne de la mémoire principale est mappé sur un ensemble de lignes de mémoire cache remplie. Il faut donc …   Wikipédia en Français

  • Cache algorithms — This article is about general cache algorithms. For detailed algorithms specific to paging, see page replacement algorithm. For detailed algorithms specific to the cache between a CPU and RAM, see CPU cache. In computing, cache algorithms (also… …   Wikipedia

  • Anomalie De Belady — L anomalie de Belady est une anomalie de comportement observée en informatique pour l algorithme de remplacement des lignes de cache Fifo. Augmenter le nombre de voies de la mémoire cache peut accroître le taux de défauts de cache. Ce phénomène n …   Wikipédia en Français

  • Anomalie de Belady — L anomalie de Belady est une anomalie de comportement observée en informatique pour l algorithme de remplacement des lignes de cache FIFO. Augmenter le nombre de voies de la mémoire cache peut accroître le taux de défauts de cache. Ce phénomène n …   Wikipédia en Français

  • Anomalie de belady — L anomalie de Belady est une anomalie de comportement observée en informatique pour l algorithme de remplacement des lignes de cache Fifo. Augmenter le nombre de voies de la mémoire cache peut accroître le taux de défauts de cache. Ce phénomène n …   Wikipédia en Français

  • Cache — [kæʃ] bezeichnet in der EDV einen schnellen Puffer Speicher, der Zugriffe auf ein langsames Hintergrundmedium oder zeitaufwendige Neuberechnungen nach Möglichkeit vermeidet. Meist werden hierzu Inhalte/Daten gepuffert, die bereits einmal… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”