Почему Bit-PLRU отличается от LRU

Question

Ниже приведено описание о bit-plru

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

Я думаю, что политика замены lru и bit-plru одинакова, их доля промахов также одинакова.

Моя причина: At cache misses, the line with lowest index whose MRU-bit is 0 is replaced.

Строка с наименьшим индексом означает наименьшее количество использованных за последнее время, поэтому ее mru-бит определенно равен нулю (это не может быть 1, потому что он не использовался недавно),Значит, mru-bit избыточен?

Если моя причина неверна, кто-нибудь может дать мне какую-нибудь причину или пример, показывающий, где разница между бит-плру и лру?Почему bit-plru дал лучшую производительность (шанс промаха)?

Спасибо!

Answer 1

Наименее недавно использованная означает линию с самым старым временем доступа. Но отслеживание доступа, чтобы всегда знать, какой из них самый старый, может быть сложным в контексте кэша. Сохранение порядка доступа для каждого блока потребует как минимум ceil (log ₂ ( n !)) Бит или, наиболее вероятно, n & times; log ₂ n битов, что близко к n небольшим и намного более простым в управлении. Всякий раз, когда к ссылке на память обращаются, она должна быть удалена из списка заказов, помещена вверху, а остальная часть списка обновлена. Это может быть сложно сделать в один цикл.

Это причина, по которой были разработаны методы псевдо-LRU. Они гарантируют, что «древняя» линия будет выброшена, но не самая древняя.

Рассмотрим пример для бит-LRU вашего вопроса. Мы предполагаем, что начальное установленное состояние следующее.

line    status    real order
(index) (MRU)
0       0         3  LRU
1       1         0  MRU
2       1         1
3       0         2

Реальный заказ не сохраняется, но мы будем использовать его для понимания поведения алгоритма (самый маленький - самый младший).

Теперь предположим, что мы получили доступ к существующей строке 0. Статус становится

line    status    real order
(index) (MRU)
0       1         0  MRU
1       1         1  
2       1         2
3       0         3  LRU

Предположим, за этим следует промах, поэтому мы применяем метод и заменяем строку 3:

Всякий раз, когда последний оставшийся 0 бит битов состояния набора устанавливается в 1, все остальные биты сбрасываются в 0.

line    status    real order
(index) (MRU)
0       0         1  
1       0         2  
2       0         3  LRU
3       1         0  MRU

Таким образом, алгоритм правильно извлек LRU (строка 3).

Предположим, что есть еще одна мисс. Алгоритм гласит:

При отсутствии кэша строка с самым низким индексом, бит MRU которого равен 0, заменяется.

Таким образом, строка 0 будет заменена. Но это строка , а не LRU, которая является строкой 2. Это даже самая «молодая» из древних линий. Но имеет самый низкий индекс.
Чтобы извлечь другую, лучшую строку, потребуется дополнительная информация о времени доступа.
Возможно, некоторая случайность в выбросе может быть просто добавлена. Но найти настоящий LRU сложнее.

Обратите внимание, что есть лучшие способы иметь псевдо LRU. Например, Tree-LRU намного лучше, но он еще не гарантирует, что будет использоваться настоящий LRU.
Для практических применений pLRU дает частоту промахов, аналогичную реальной LRU, хотя и намного проще.

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