2.6. Алгоритм псевдо-lru
Алгоритм псевдо-LRU действует следующим образом. Когда в цикле считывания происходит промах и в кэш-память необходимо передать из памяти новую строку, приходится выбирать для заполнения одну из четырех строк множества. Если в множестве есть недостоверная строка (ее бит достоверности содержит 0), то для заполнения выбирается именно эта строка. Когда же все строки в множестве достоверны (все 4 бита достоверности содержат 1), заменяемая строка выбирается с привлечением бит из блока LRU.
Обозначим строки в множестве через L0, L1, L2 и L3. Каждому множеству в блоке LRU соответствуют три бита В0, В1 и В2, которые модифицируются при каждом попадании и заполнении следующим образом:
— если последнее обращение в множестве было к строке L0 или L1, то бит В0 устанавливается в состояние 1, а при обращении к строке L2 или L3 бит В0 сбрасывается в 0;
— если последнее обращение в паре L0—L1 было к строке L0, то бит В1 устанавливается в состояние 1, а при обращении к строке L1 бит В1 сбрасывается в 0;
— если последнее обращение в паре L2—L3 было к строке L2, то бит В2 устанавливается в состояние 1, а при обращении к строке L3 бит В2 сбрасывается в 0.
Выбор заменяемой строки (когда все строки в множестве достоверны) определяет содержимое бит В0, В1 и В2:
В0 |
В1 |
В2 |
|
0 |
0 |
X |
заменяется строка L0 |
0 |
1 |
X |
заменяется строка L1 |
1 |
X |
0 |
заменяется строка L2 |
1 |
X |
1 |
заменяется строка L3 |
Строки кэш-памяти можно по отдельности объявить недостоверными, задавая операцию недостоверности кэш-памяти на шине процессора. При инициировании такой операции кэш-память сравнивает объявляемый недостоверным адрес с тэгами строк, находящихся в кэш-памяти, и сбрасывает бит достоверности при обнаружении соответствия (равенства). Предусмотрена также операция очистки кэш-памяти, которая превращает в недостоверное все содержимое кэш-памяти.
3. Ход работы
1. Произвести синтез кэш-памяти объемом 32 байта, со схемой управления и взаимодействия, работающей по алгоритму согласно варианта.
LRU (Least Recently Used) — вытесняется буфер, неиспользованный дольше всех – 1,5,9,13,17,21
MRU (Most Recently Used) — вытесняется последний использованный буфер – 2,6,10,14,18,22
LFU (Least Frequently Used) — вытесняется буфер, использованный реже всех – 3,7,11,15,19,23,25
ARC (Advanced Replacement Cache) — алгоритм вытеснения, комбинирующий LRU и LFU, запатентованный IBM – 4,8,12,16,20,24
4. Контрольные вопросы
1. Проблема адресации данных в кэш-памяти.
2. Кэш-память на основе ассоциативного поиска.
3. Кэш память с прямым отображением.
4. Кэш-память на основе множественно-ассоциативной схемы поиска.
5. Алгоритм определения множества-кандидата на удаление.
6. Совместная оптимизация работы системы виртуальной и кэш-памяти