ня зазвичай вибирається рядок, до якої найдовше не зверталися (алгоритм LRU - Least Recently Used). При відносно великій кількості каналів (рядків у наборі) вдаються до деякого спрощення - алгоритм PseudoLRU для чотирьох рядків (Four Way Set Associative Cache) дозволяє приймати рішення, використовуючи всього 3 біта. Можливо також застосування алгоритму заміщення FIFO (першим увійшов - першим і вийшов) або навіть випадкового (random) заміщення, що простіше, але менш ефективно.
набірний-асоціативна архітектура широко застосовується для первинного кеша сучасних процесорів. Обсяг Кешована пам'яті визначається так само, як і в попередньому варіанті, але тут буде фігурувати обсяг одного банку (а не всього кеша) і розрядність відносяться до нього осередків тега.
2.3 Асоціативний кеш
На відміну від попередніх у повністю асоціативного кеша будь-яка його рядок може відображати будь блок пам'яті, що істотно підвищує ефективність використання його обмеженого обсягу. При цьому всі біти адреси кешованого блоку, за вирахуванням біт, що визначають положення (зміщення) даних в рядку, зберігаються в пам'яті тегів. У такій архітектурі для визначення наявності затребуваних даних у кеш-пам'яті потрібно порівняння зі старшою частиною адреси тегів всіх рядків, а не однієї або декількох, як при прямому відображенні або набірний-асоціативної архітектурі. Природно, послідовний перебір елементів пам'яті тегів відпадає - на це може піти надто багато часу. Залишається паралельний аналіз всіх осередків, що є складною апаратної завданням, яка поки вирішена тільки для невеликих обсягів первинного кеша в деяких процесорах. Застосування повністю асоціативної архітектури у вторинному кеші поки не передбачається.
3. Алгоритми і принцип дії
.1 Алгоритми заміщення даних
При виникненні промаху, контролер кеш-пам'яті повинен вибрати підлягає заміщенню блок. Користь від використання організації з прямим відображенням полягає в тому, що апаратні рішення тут найбільш прості. Вибирати просто нічого: на потрапляння перевіряється тільки один блок і тільки цей блок може бути заміщений. При повністю асоціативної або множественно-асоціативної організації кеш-пам'яті є кілька блоків, з яких треба вибрати кандидата у випадку промаху. Як правило, для заміщення блоків застосовуються дві основні стратегії: випадкова (Random) і LRU.
У першому випадку, щоб мати рівномірний розподіл, блоки-кандидати вибираються випадково. У деяких системах, щоб отримати відтворюване поведінку, яка особливо корисно під час налагодження апаратури, використовують псевдовипадковий алгоритм заміщення.
У другому випадку, щоб зменшити ймовірність викидання інформації, яка скоро може знадобитися, всі звернення до блокам фіксуються. Замінюється той блок, що не використовувався найдовше (LRU - Least-Recently Used).
Гідність випадкового способу полягає в тому, що його простіше реалізувати в апаратурі. Коли кількість блоків для підтримки траси збільшується, алгоритм LRU стає все більш дорогим і часто тільки наближеним. У таблиці показані відмінності в частках промахів при використанні алгоритму заміщення LRU і випадкового алгоритму.
Таблиця. Порівняння часткою промахів для алгоритму LRU і випадкового алгоритму заміщення при декількох розмірах кеша і різних асоціативних при розмірі блоку 16 байт
Розмір кеш-памятіLRURandomLRURandomLRURandom16 KB5.18% 5.69% 4.67% 5.29% 4.39% 4.96% 64 KB1.88% 2.01% 1.54% 1.66% 1.39% 1.53% 256 KB1.15% 1.17% 1.13% 1.13% 1.12% 1.12%
3.2 Алгоритми псевдо-LRU
Алгоритм псевдо-LRU діє таким чином. Коли в циклі зчитування відбувається промах і в кеш-пам'ять необхідно передати з пам'яті новий рядок, доводиться вибирати для заповнення одну з чотирьох рядків множини. Якщо в безлічі є недостовірна рядок (її біт достовірності містить 0), то для заповнення вибирається саме цей рядок. Коли ж всі рядки в безлічі достовірні (всі 4 біта достовірності містять 1), замінна рядок вибирається із залученням біт з блоку LRU.
Позначимо рядки в безлічі через L0, L1, L2 і L3. Кожному безлічі в блоці LRU відповідають три біта В0, В1 і В2, які модифікуються при кожному попаданні і заповненні наступним чином:
якщо останнє звернення в парі L0-L1 було до рядка L0, то біт В1 встановлюється в стан 1, а при зверненні до рядку L1 біт В1 скидається в 0;
якщо останнє звернення в парі L2-L3 було до рядка L2, то біт В2 встановлюється в стан 1, а при зверненні до рядку L3 біт В2 скидається в 0. Вибір замінної рядки (коли всі рядки в безлічі достовірні) визначає вміст біт В0, В1 і В2:
...
