Логически как они реализованы, так это то, что строки кэша в наборе упорядочены, поэтому они образуют очередь.Голова очереди - это строка, которая будет удалена в следующий раз, когда кешу потребуется выделить строку в этом наборе.
Новые строки выделяются в конце очереди, наиболее удаленной от "разделочная доска ".Если в наборе была недопустимая строка, выселение не требуется: элементы перемещаются, чтобы заполнить пробел в очереди.В противном случае необходимо выселение, чтобы освободить место в этом наборе.
Для LRU, при попадании эта линия перемещается в самое последнее использованное (MRU) положение.Для FIFO это не так.
Для случайных нет очереди;кеш просто выбирает случайную строку для замены, если в наборе нет недопустимых строк.
Чтобы минимизировать загрязнение кеша, невременная загрузка или предварительная выборка может выделить строку в позиции LRU (затемв очереди на выселение) вместо обычного LRU.Это полезно для данных, которые вы не ожидаете прочитать более одного раза, прежде чем они будут удалены в любом случае.(Я думаю, что процессоры AMD на самом деле работают так для предварительной выборки NT. Процессоры Intel реализуют prefetchnta, ограничивая его заполнением только 1 или 2 способов любого набора в кеше L3.)
Физически как они реализованы, могут различаться, если они реализуют желаемый алгоритм.IDK, если обычно на самом деле копируют данные (записывают все обратно в массив кеша после нажатия на чтение для LRU) или используют дополнительные биты в тегах для записи порядка и только их записи.Я предполагаю, что это был бы компромисс между гораздо более широким дополнительным портом записи и 3 дополнительными битами тегов.
Обычно для быстрых кэшей L1d считывание тегов + данных параллельно, поэтому данные для всех способов в наборепрямо здесь, чтобы выбрать из на основе результата сравнения тегов.Но для более энергоэффективных кешей, которые ждут проверки тегов, а затем извлекают данные только из того, как они попадают (если есть попадание), копирование данных было бы нецелесообразным.
Я думаю, что это очень вероятночто логика LRU обычно реализуется с дополнительными битами тегов, которые задают порядок путей в наборе.Ваша ментальная модель может игнорировать это и просто смотреть на линии, перемещающие позиции, хотя.
Или вместо того, чтобы я придумывал что-то, просто прочитайте ответ Пола Клейтона на Как кэш LRU реализован вCPU?
Очевидно, что некоторые конструкции используют псевдо-LRU вместо истинного LRU, чтобы уменьшить количество дополнительных битов в наборе.например, 4-битное число для каждого из 16 путей в большом кеше последнего уровня или 8x 3-битных числа в 8-канальном кэше.(Кроме того, аппаратное обеспечение для параллельной логики LRU было бы весьма значительным.) Или вместо простой наивной нумерации в каждом случае, вы можете потенциально кодировать возможные состояния очереди всего в 16 битах на набор.Но это по-прежнему важно.
(я не знаю, что на практике используют современные высокопроизводительные процессоры x86 - стоит ли истинный LRU стоимость для маленького / быстрого L1d и / или для большего / медленного L2 и L3)