Псевдо-LRU¶

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

¶История и предпосылки

Алгоритм LRU (Least Recently Used) является одним из классических методов управления кэш-памятью, при котором вытесняется элемент, к которому дольше всего не было обращений. Однако точная реализация LRU требует хранения для каждого кэш-набора (кэш-линии) информации о порядке всех его элементов. Для кэша с ассоциативностью N (числом блоков в наборе) это означает необходимость хранения N log2(N!) бит или использования сложных схем сравнения. Например, для 4-канального кэша (N=4) требуется 4 log2(24) ≈ 18,5 бит, а для 8-канального — 8 * log2(40320) ≈ 123 бита на набор. Такие затраты становятся непомерными для современных процессоров с тысячами кэш-наборов.

В 1980-х годах, с ростом тактовых частот и объёмов кэшей, инженеры начали искать более экономичные альтернативы. Псевдо-LRU был впервые предложен как аппаратно-эффективный компромисс: он обеспечивает поведение, близкое к LRU, но с линейной сложностью по числу каналов. Первые коммерческие реализации появились в процессорах Intel Pentium (1993) и PowerPC 604 (1995), где использовались битовые деревья для кэшей данных и инструкций.

¶Принцип работы

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

¶Пример для 4-канального кэша

Рассмотрим кэш-набор с четырьмя блоками (каналами), пронумерованными 0, 1, 2, 3. Бинарное дерево имеет три внутренних узла: корень (узел A) и два дочерних (узлы B и C). Каждый узел хранит один бит: 0 означает, что левая ветвь более недавняя, 1 — правая ветвь более недавняя. Изначально все биты могут быть установлены в 0.

При обращении к блоку 2 (который находится в правой ветви корня и левой ветви узла C):

1. На узле C (родитель блоков 2 и 3) бит устанавливается в 0 (левая ветвь более недавняя).
2. На корне A бит устанавливается в 1 (правая ветвь более недавняя).

При необходимости вытеснения:

1. На корне A бит равен 1, значит, менее недавняя ветвь — левая (блоки 0 и 1). Переходим к узлу B.
2. На узле B бит равен 0, значит, менее недавняя ветвь — левая (блок 0). Вытесняется блок 0.

После вытеснения биты не сбрасываются, а остаются для дальнейшего использования. Этот алгоритм гарантирует, что вытесняемый элемент не будет самым недавно использованным, но не гарантирует, что он будет именно наименее недавним.

¶Виды и модификации

¶Базовое битовое дерево (Tree-PLRU)

Наиболее распространённая реализация, описанная выше. Для N-канального кэша требуется N-1 бит на набор. Например, для 4-канального — 3 бита, для 8-канального — 7 бит, для 16-канального — 15 бит. Это значительно меньше, чем для точного LRU (например, для 8-канального — 123 бита).

¶PLRU со счётчиками (Counter-based PLRU)

Альтернативный подход, где каждый элемент кэша хранит небольшой счётчик (обычно 2-3 бита), который увеличивается при обращениях к другим элементам и сбрасывается при обращении к данному. Вытесняется элемент с наибольшим значением счётчика. Этот метод менее точен, чем дерево, но проще для реализации в программном обеспечении.

¶PLRU с кольцевым буфером

Используется в некоторых системах хранения данных. Элементы кэша организованы в кольцевой список, и указатель «вытеснения» циклически перемещается. При обращении к элементу его порядковый номер не меняется, но может быть выполнен сдвиг указателя. Этот метод ближе к FIFO, чем к LRU, но считается разновидностью псевдо-LRU.

¶Адаптивный PLRU

В современных процессорах (например, Intel Core i7) применяются гибридные схемы, которые переключаются между PLRU и другими алгоритмами (например, случайным вытеснением) в зависимости от паттернов доступа. Это позволяет улучшить производительность на специфических нагрузках.

¶Преимущества и недостатки

¶Преимущества

• Низкие аппаратные затраты: для N-канального кэша требуется всего N-1 бит на набор, что в десятки раз меньше, чем для точного LRU.
• Простота реализации: битовые деревья легко реализуются в виде комбинационных схем или микрокода, что снижает задержки и энергопотребление.
• Хорошая производительность: на большинстве реальных рабочих нагрузок (например, в базах данных, веб-серверах, компиляторах) PLRU показывает результаты, близкие к точному LRU (обычно разница в коэффициенте попаданий составляет 1–5%).
• Масштабируемость: алгоритм легко адаптируется к кэшам с высокой ассоциативностью (16, 32, 64 канала).

¶Недостатки

• Неточность: в худших случаях (например, при циклическом доступе к большому набору данных) PLRU может вытеснять недавно использованные элементы, что приводит к снижению коэффициента попаданий. Например, при последовательном доступе к 5 элементам в 4-канальном кэше PLRU может вытеснить элемент, к которому обращались всего 2 шага назад.
• Чувствительность к паттернам доступа: на некоторых паттернах (например, «запросы с повторением через фиксированный интервал») PLRU может работать хуже, чем случайное вытеснение.
• Сложность обновления: при каждом обращении к кэшу необходимо обновлять несколько битов дерева (в среднем log2(N) обновлений), что может увеличить задержку в конвейере процессора.

¶Применение

¶Процессоры общего назначения

PLRU является стандартным алгоритмом вытеснения для кэшей L2 и L3 в большинстве современных процессоров. Например:

• Intel Core i7 (Nehalem, Sandy Bridge, Haswell): кэш L3 использует PLRU с битовым деревом.
• AMD Ryzen (Zen, Zen 2, Zen 3): кэш L2 и L3 используют модифицированный PLRU с поддержкой адаптивного управления.
• ARM Cortex-A75, A76: кэш L2 использует PLRU для снижения энергопотребления.

¶Встраиваемые системы

В микроконтроллерах (например, ARM Cortex-M) и DSP-процессорах PLRU часто применяется из-за ограниченных ресурсов. Например, в процессоре TI TMS320C66x используется PLRU для кэша данных L1.

¶Системы хранения данных

В RAID-контроллерах и SSD-контроллерах (например, Samsung, Intel Optane) PLRU используется для управления кэш-памятью на уровне страниц. Алгоритм позволяет эффективно обрабатывать большие объёмы данных при низких накладных расходах.

¶Сетевые устройства

В маршрутизаторах и коммутаторах (например, Cisco Catalyst) PLRU применяется для кэширования таблиц маршрутизации и ACL, где важна скорость принятия решений.

¶Сравнение с другими алгоритмами

¶Критика и ограничения

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

Кроме того, в кэшах с очень высокой ассоциативностью (более 64 каналов) PLRU может становиться менее эффективным из-за увеличения глубины дерева и задержек обновления. В таких системах предпочтение отдаётся алгоритмам на основе хеширования (например, RRIP — Re-Reference Interval Prediction).

¶Интересные факты

• В процессоре Intel Pentium Pro (1995) впервые был реализован PLRU для кэша L2, что позволило снизить количество транзисторов на 30% по сравнению с точным LRU.
• В суперкомпьютере IBM Blue Gene/Q (2011) использовался PLRU с 16-канальным кэшем L2, что обеспечило высокую производительность при низком энергопотреблении.
• Алгоритм PLRU является частью стандарта IEEE 802.11 (Wi-Fi) для кэширования кадров в точках доступа.
• В некоторых реализациях PLRU биты дерева инициализируются не нулями, а случайными значениями, чтобы избежать «эффекта синхронизации» при запуске системы.

¶Источники

1. Hennessy, J. L., & Patterson, D. A. (2019). Computer Architecture: A Quantitative Approach (6th ed.). Morgan Kaufmann.
2. Jacob, B., Ng, S., & Wang, D. (2007). Memory Systems: Cache, DRAM, Disk. Morgan Kaufmann.
3. Intel Corporation. (2016). Intel 64 and IA-32 Architectures Optimization Reference Manual.
4. Al-Zoubi, H., Milenkovic, A., & Milenkovic, M. (2004). Performance evaluation of cache replacement policies for the SPEC CPU2000 benchmark suite. Proceedings of the 42nd Annual Southeast Regional Conference.
5. Smith, A. J. (1982). Cache memories. ACM Computing Surveys, 14(3), 473–530.