Псевдо-LRU - Pseudo-LRU

Псевдо-LRU или же PLRU это семья алгоритмы кеширования которые улучшают производительность Наименее недавно использованные (LRU) путем замены значений с использованием приблизительных мер возраста, а не поддержания точного возраста каждого значения в кеше.

PLRU обычно относится к двум алгоритмам замены кеша: tree-PLRU и bit-PLRU.

Дерево-PLRU

Tree-PLRU - эффективный алгоритм для выбора элемента, к которому, скорее всего, не было доступа совсем недавно, учитывая набор элементов и последовательность событий доступа к элементам.

Этот метод используется в Кэш процессора из Intel 486 и во многих процессорах в PowerPC семья, например Freescale's PowerPC G4 использован Компьютер Apple.

Алгоритм работает следующим образом: рассмотрим двоичное дерево поиска для рассматриваемых предметов. Каждый узел дерева имеет однобитовый флаг, обозначающий «идти налево, чтобы найти элемент псевдо-LRU» или «идти вправо, чтобы найти элемент псевдо-LRU». Чтобы найти элемент псевдо-LRU, просмотрите дерево в соответствии со значениями флагов. Чтобы обновить дерево с доступом к элементу N, обойдите дерево, чтобы найти N, и во время обхода установите флаги узла, чтобы обозначить направление, противоположное выбранному направлению.

Псевдо LRU работает

Этот алгоритм может быть неоптимальным, так как он является приближенным. Например, на приведенной выше диаграмме со строками кэша A, C, B, D, если шаблон доступа был: C, B, D, A, при выселении мы выбрали бы B вместо C. Это потому, что и A, и C находятся в одной половине, и доступ к A направляет алгоритм на другую половину, которая не содержит строки кэша C.

Bit-PLRU

Bit-PLRU хранит один бит состояния для каждой строки кэша. Эти биты называются MRU-битами. При каждом доступе к строке ее бит MRU устанавливается в 1, указывая на то, что линия использовалась недавно. Каждый раз, когда последний оставшийся 0 бит битов состояния набора устанавливается в 1, все остальные биты сбрасываются в 0. При промахах кэша заменяется самая левая строка, у которой бит MRU равен 0. [1]

Смотрите также

Рекомендации

  1. ^ Автоматическое создание моделей микроархитектур