LRU требует поддержания отношения total order между всеми действительными строками кэша в наборе кэша.Например, рассмотрим трехсторонний набор кешей со следующими строками A, B и C, упорядоченными от самого последнего обращения к наименее последнему доступу (представленному как ABC).Если доступ к C следующий, то заказ становится CAB.Если новая строка, D, должна быть заполнена в том же наборе кеша, поскольку нет недопустимых строк, политика замены LRU выберет B, который будет удален и заменен новой строкой.Затем ордер становится DCA.
Для 3-х стороннего кэша существует до 3 * 2 = 6 возможных ордеров для строк в каждом наборе.В общем случае для N-way-кэша их может быть N!(N факториал) возможные заказы.Теоретически, вам нужно как минимум log2 (N!) Битов (округленных до ближайшего целого числа) на каждый набор кэша, чтобы точно поддерживать свойство LRU.Обратите внимание, что log2 (N!) Равно Θ (Nlog (N)) , поэтому оно растет суперлинейно по отношению к числу способов.Ни один нормальный человек не любит ничего, чья стоимость растет сверхлинейно.
Особенно дешевым случаем является двухсторонний кэш, в котором состояние LRU требует только log2 (2!) = 1 бит, т.е. один бит.Хотя это намного дороже для любого другого числа способов.
На практике, однако, нет простого способа сохранить одно число, которое представляет состояние LRU набора.Если текущее состояние LRU равно X, а затем происходит некоторый доступ к линии, как можно определить следующее состояние LRU?Не существует простого математического соотношения, которое может быть реализовано аппаратно.Таким образом, вместо использования одного числа, реалистичная реализация будет использовать несколько чисел, по одному на строку кэша.В этом случае эти числа называются возрастами.Такая конструкция даже потребует (много) больше битов, чем теоретический минимум log2 (N!), Для поддержания состояния LRU.
Помимо аппаратных издержек, политика замены LRU не обязательно является оптимальной для производительности.Это зависит от шаблонов доступа к памяти приложений в целевой рыночной области и остальной иерархии кэша.
LRU использовался во многих реальных процессорах.Кэши, которые являются двусторонними ассоциативными, обычно используют LRU.Например, AMD SledgeHammer использует LRU для кэшей L1I и L1D.Кэш инструкций L1 процессора Itanium 2 использует LRU и является четырехпозиционным ассоциативным .Обычно, когда число путей больше двух, кэши не используют LRU.