Псевдо-LRU

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

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

Дерево-ПЛРУ

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

Этот метод используется в кэше процессора Intel 486 и во многих процессорах семейства PowerPC , таких как от Freescale, PowerPC G4 используемый Apple Computer .

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

Псевдо LRU работает — Pseudo LRU working

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

Бит-ПЛРУ

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

См. также

Алгоритмы кэширования

Ссылки

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

Эта по информатике статья незавершена . Вы можете помочь Википедии, расширив ее .

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

[1]