text:
# Кеш процесора
Кеш процесора — кеш, який використовується центральним процесором (англ. CPU) для скорочення середнього часу доступу до пам'яті комп'ютера. Кеш — це швидша і менша за розміром пам'ять, яка зберігає копії даних, що часто використовуються, з головної пам'яті.
Коли процесору потрібно звернутися в пам'ять для читання або запису даних, він спочатку перевіряє, чи є їхні копії в кеші. У разі успіху перевірки процесор виконує операцію використовуючи кеш, що працює швидше ніж при використанні повільнішої основної пам'яті. Детальніше про затримки пам'яті див. затримки (англ. SDRAM latency) SDRAM: tCAS, tRCD, tRP, tRAS
Більшість сучасних мікропроцесорів для настільних комп'ютерів і серверів мають щонайменше три незалежних кеші: кеш інструкцій для прискорення завантаження машинного коду, кеш даних для прискорення читання і запису даних і буфер асоціативної трансляції (TLB) для прискорення трансляції віртуальних (логічних) адрес у фізичні, як для інструкцій, так і для даних. Кеш даних часто реалізується у вигляді багаторівневого кешу (L1, L2, L3)..
Збільшення розміру кеш-пам'яті може позитивно впливати на продуктивність майже всіх застосунків, хоча в деяких випадках ефект незначний. Робота кеш-пам'яті зазвичай прозора для програміста, проте для її ефективного використання у деяких випадках застосовуються спеціальні алгоритмічні прийоми, які змінюють порядок обходу даних в ОЗП або підвищують їх локальність (наприклад, при блочному множенні матриць).

## Принцип роботи
Даний розділ описує типовий кеш даних і деякі види кешу інструкцій; TLB може бути влаштований складніше, а кеш інструкцій — простіше. На діаграмі праворуч зображені основна і кеш-пам'ять. Кожен рядок — група комірок пам'яті, що містить дані, організовані в кеш-лінії. Розмір кожної кеш-лінії може розрізнятися у різних процесорах, але для більшості x86-процесорів він становить 64 байта. Розмір кеш-лінії зазвичай більше розміру даних, до якого є можливим доступ з однієї машинної команди (типові розміри від 1 до 16 байт). Кожна група даних в пам'яті розміром у 1 кеш-лінію має порядковий номер. Для основної пам'яті цей номер є адресою пам'яті з відкинутими молодшими бітами. У кеші кожної кеш-лінії додатково ставиться у відповідність тег, який є адресою продубльованих в цій кеш-лінії даних в основній пам'яті.
При звертанні процесора в пам'ять спочатку проводиться перевірка, чи зберігає кеш запитувані з пам'яті дані. Для цього проводиться порівняння адреси запиту з значеннями всіх тегів кешу, в яких ці дані можуть зберігатися. Випадок збігу з тегом якої-небудь кеш-лінії називається попаданням в кеш (англ. cache hit), зворотний випадок називається кеш-промахом (англ. cache miss). Попадання в кеш дозволяє процесору негайно провести читання або запис даних у кеш-лінії з збіглася тегом. Відношення кількості попадань в кеш до загальної кількості запитів до пам'яті називають рейтингом влучень (англ. hit rate), воно є мірою ефективності кешу для обраного алгоритму або програми.
У разі промаху в кеші виділяється новий запис, у тег якого записується адреса поточного запиту, а в саму кеш-лінію — дані з пам'яті після їх прочитання або дані для запису в пам'ять. Промахи з читання затримують виконання, оскільки вони вимагають запиту даних в більш повільної основної пам'яті. Промахи по запису можуть не давати затримку, оскільки потрібні дані можуть бути збережені в кеші, а запис їх в основну пам'ять можна зробити у фоновому режимі. Робота кешу інструкцій багато в чому схожа на вищенаведений алгоритм роботи кешу даних, але для інструкцій виконуються тільки запити на читання. Кеш інструкцій і даних можуть бути розділені для збільшення продуктивності (принцип, використовуваний в Гарвардській архітектурі) або об'єднані для спрощення апаратної реалізації.
Для додавання даних в кеш після кеш-промаху може знадобитися витіснення (англ. evict) раніше записаних даних. Для вибору заміщаючого рядка кешу використовується евристика, звана політика заміщення (англ. replacement policy). Основною проблемою алгоритму є передбачення, який рядок найімовірніше не буде потрібно для подальших операцій. Якісні передбачення складні, і апаратні кеші використовують прості правила, такі, як LRU. Відмітка деяких областей пам'яті як некешованих (англ. non cacheable) покращує продуктивність за рахунок заборони кешування рідко використовуваних даних. Промахи для такої пам'яті не створюють копію даних в кеші.
При запису даних у кеш повинен існувати певний момент часу, коли вони будуть записані в основну пам'ять. Це час контролюється політикою запису (англ. write policy). Для кешу зі наскрізним записом (англ. write-through) будь-який запис у кеш приводить до негайного запису в пам'ять. Інший тип кешів, зворотна запис англ. write-back (іноді також званий copy-back), відкладає запис на більш пізній час. У таких кешах відстежується стан кеш-лінійок ще не скинутих в пам'ять (відмітка бітом «брудний» англ. dirty). Запис в пам'ять проводиться при витісненні подібного рядка кешу. Таким чином, промах в кеші, що використовує політику зворотного запису, може вимагати двох операцій доступу в пам'ять, один для скидання стану старого рядка і інший — для читання нових даних.
Існують також змішані політики. Кеш може бути із наскрізним записом (англ. write-through), але для зменшення кількості транзакцій на шині записи можуть тимчасово міститися в чергу і об'єднуватися один з одним.
Дані в основній пам'яті можуть змінюватися не тільки процесор, але і периферією, що використовує прямий доступ до пам'яті, або іншими процесорами багатопроцесорні системи. Зміна даних призводить до застарівання їх копії в кеші (стан stale). В іншої реалізації, коли один процесор змінює дані в кеші, копії цих даних в кешах інших процесорів будуть помічені як stale. Для підтримки вмісту декількох кешів в актуальному стані використовується спеціальний протокол кеш когерентності.

### Структура запису в кеші
Типова структура запису в кеші
| Блок даних | тег | біт актуальності |

Блок даних (кеш-лінія) містить безпосередню копію даних з основної пам'яті. Біт актуальності означає, що даний запис містить актуальну (найсвіжішу) копію.
Структура адреси
| тег | індекс | зміщення |

Адреса пам'яті, що розділяється (від старших біт до молодших) на Тег, індекс і зміщення. Довжина поля індексу дорівнює  {\displaystyle \lceil \log _{2}(cache\_rows)\rceil } біт і відповідає ряду (рядку) кешу, використовуваної для запису. Довжина зсуву дорівнює  {\displaystyle \lceil \log _{2}(data\_blocks)\rceil }.

### Асоціативність
Асоціативність є компромісом. Перевірка більшого числа записів вимагає більше енергії, площі чипу, і, потенційно, часу. Якщо б існувало 10 місць, які алгоритм витіснення міг би відобразити місце в пам'яті, тоді перевірка наявності цього місця в кеші зажадала б переглянути 10 записів в кеші. З іншого боку, кеші з високою асоціативністю піддаються меншому кількості промахів (див. нижче «конфліктуючі промахи») і процесор витрачає менше часу на читання з повільної основної пам'яті. Існує емпіричне спостереження, що подвоєння асоціативності (від прямого відображення до 2-канальної або від 2- до 4-канальної) має приблизно такий же вплив на інтенсивність влучень (hit rate), що і подвоєння розміру кешу. Збільшення асоціативності понад 4 каналів приносить менший ефект для зменшення кількості промахів (miss rate) і зазвичай виробляється з інших причин, наприклад, через перетин віртуальних адрес.
В порядку погіршення (збільшення тривалості перевірки на потрапляння) та поліпшення (зменшення кількості промахів):
1. кеш прямого відображення (англ. direct mapped cache) — найкращий час попадання і, відповідно, найкращий варіант для великих кешів;
2. 2-канальний множинно-асоціативний кеш англ. 2-way set associative cache;
3. 2-канальний skewed асоціативний кеш (англ. «the best for tradeoff …. caches whose sizes are in the range 4K-8K bytes» — André Seznec);
4. 4-канальний множинно-асоціативний кеш (англ. 4-way set associative cache);
5. повністю асоціативний кеш, (англ. fully associative cache) — найкращий (найнижчий) відсоток промахів (miss rate) і найкращий варіант при надзвичайно високих витратах при промаху (miss penalty).
  - Кеш прямого відображення
  - n-канальний множинно-асоціативний кеш
  - Повністю асоціативний кеш

### Види промахів
Промах з читання з кешу інструкцій. Зазвичай дає дуже велику затримку, оскільки процесор не може продовжувати виконання програми (принаймні, виконання поточного потоку) і змушений простоювати в очікуванні завантаження інструкції з пам'яті.
Промах з читання з кешу даних. Зазвичай дає меншу затримку, оскільки інструкції, які не залежать від запитаних даних, можуть продовжувати виконуватися, поки запит обробляється в основній пам'яті. Після отримання даних з пам'яті можна продовжувати виконання залежних інструкцій.

### Категорії промахів (Three Cs)
- Compulsory misses — промахи, викликані першою згадкою потрібної адреси. Розміри кешів і їх асоціативність не впливають на кількість даних промахів. Попередня вибірка (prefetching), як програмну, так і апаратну, може допомогти, так само, як і збільшення розміру кеш-лінії (як виду апаратного вибору). Такі промахи іноді називають «холодними».
- Capacity misses — промахи, викликані виключно кінцевим розміром кешу, що відбуваються незалежно від ступеня асоціативності або розміру кеш-лінії. Графік таких промахів щодо розміру кешу може дати деяку міру тимчасової локальності (temporal locality) деякого набору запитів в пам'ять. Варто зауважити, що не існує поняття повного кешу, порожнього кешу або майже повного кешу, так як кеші процесора майже весь час мають кеш-лінії в зайнятому стані, і, отже, практично кожен заклад нової лінії зажадає гасіння вже зайнята.
- Conflict misses — промахи, викликані конфліктом. Їх можна уникнути, якщо б кеш не витіснив запис раніше. Можна додатково розділити на промахи, викликані відображенням (конкретним значенням асоціативності) і промахи заміщення, які викликані конкретним алгоритмом вибору записів для заміщення.

### Трансляція адрес
Більша частина процесорів загального призначення реалізує якийсь варіант віртуальної пам'яті. Коротко кажучи, кожна програма, що виконується на машині, бачить власний спрощений адресний простір, що містить код і дані тільки цієї програми. Будь-яка програма використовує свій віртуальний адресний простір незалежно від його місцезнаходження у фізичній пам'яті.
Наявність віртуальної пам'яті вимагає від процесора проведення трансляції віртуальних (математичних) адрес, використовуваних програмою, у фізичні адреси, відповідні реальному розташуванню в ОЗП. Частина процесора, провідна це перетворення, називається пристрій управління пам'яттю (MMU). Для прискорення трансляцій в MMU доданий кеш нещодавно використаних відображень (відповідностей віртуальних і фізичних адрес), званий Translation Lookaside Buffer (TLB).
Для подальшого опису важливі три особливості процесу трансляції адрес:
- Затримка: Фізичний адресу буде отримано від MMU тільки через деякий час, аж до декількох тактів, після подачі на вхід MMU віртуального адреси з генератора адрес.
- Ефект накладення: Кілька віртуальних адрес, які можуть відповідати одному фізичному. У більшості процесорів гарантується, що всі записи по фізичній адресою будуть здійснені в порядку, заданому програмою. Для виконання цієї властивості потрібна перевірка, що тільки один екземпляр копії даних з фізичної адреси знаходиться в даний момент в кеші.
- Одиниця відображення: Віртуальне адресний простір розбито на сторінки — блоки пам'яті фіксованого розміру, що починаються з адреси, кратних їх розміром. Наприклад, 4 ГБ адресного простору можна розділити на 1048576 сторінки по 4 КБ, для кожної з яких можливо незалежне відповідність фізичним сторінкам. У сучасних процесорах часто підтримується використання одночасно декількох розмірів сторінки, наприклад, 4 КБ і 2 МБ для x86-64, а в деяких сучасних AMD-процесорах ще і 1 ГБ.

Важливо також зауважити, що перші системи віртуальної пам'яті були дуже повільними, тому що вони вимагали перевірки таблиці сторінок (зберігається в основній ПАМ'ЯТІ) перед будь-яким програмним зверненням в пам'ять. Без використання кешування для відображень такі системи зменшують швидкість роботи з пам'яттю приблизно в 2 рази. Тому використання TLB дуже важливо і іноді його додавання в процесори передувало появі звичайних кешу даних та інструкцій.
По відношенню до віртуальної адресації кеші даних та інструкцій можуть бути поділені на 4 типи. Адреси в кешах використовуються для двох різних цілей: індексування і тегів.
- Physically indexed, physically tagged (PIPT) — фізично індексовані і фізично тегируемые. Такі кеші прості і уникають проблем з накладенням (aliasing), але вони повільні, так як перед зверненням в кеш потрібен запит фізичної адреси в TLB. Цей запит може викликати промах в TLB і додаткове звернення в основну пам'ять перед тим, як наявність даних буде перевірено в кеші.
- Virtually indexed, virtually tagged (VIVT) — віртуально індексовані і віртуально тегируемые. І для тегів, і для індексу використовується віртуальний адресу. Завдяки цьому перевірки наявності даних в кеші відбуваються швидше, не вимагаючи звернення до MMU. Однак виникає проблема накладання, коли кілька віртуальних адрес відповідають одному й тому ж фізичному. У цьому випадку дані будуть закешовані двічі, що сильно ускладнює підтримку когерентності. Іншою проблемою є омоніми, ситуації, коли один і той же віртуальний адресу (наприклад, у різних процесах) відображається різні фізичні адреси. Стає неможливим розрізнити такі відображення виключно по віртуальному індексу. Можливі рішення: скидання кешу при перемиканні між завданнями (context switch), вимога непересечения адресних просторів процесів, тегування віртуальних адрес ідентифікатором адресного простору (address space ID, ASID) або використання фізичних тегів. Також виникає проблема при зміні відображення віртуальних адрес у фізичні, що вимагає скидання кеш-ліній, для яких змінилося відображення.
- Virtually indexed, physically tagged (VIPT) — віртуально індексовані і фізично тегируемые. Для індексу використовується віртуальний адреса, а для тегу — фізичний. Перевагою над першим типом є менша затримка, оскільки можна шукати кеш-лінію одночасно з трансляцією адрес в TLB, однак порівняння тегу затримується до одержання фізичної адреси. Перевагою над другим типом є виявлення омонімів (homonyms), так як тег містить фізична адреса. Для даного типу потрібно більше біт для тегу, оскільки індексні біти використовують інший тип адресації.
- Physically indexed, virtually tagged — фізично індексовані і віртуально теговані кеші вважаються непотрібними і маргінальними і представляють виключно академічний інтерес.

Швидкість цих дій (затримка завантаження з пам'яті) критично важлива для продуктивності процесорів, і тому більшість сучасних L1-кешів є віртуально індексованими, що як мінімум дозволяє блоку MMU робити запит в TLB одночасно з запитом даних їх кеш-пам'яті.

### Віртуальне тегування і механізм vhints
Але віртуальна індексація не є найкращим вибором для інших рівнів кешу. Вартість виявлення перетину віртуальних адрес (aliasing) зростає із збільшенням розміру кешу і, в результаті, більшість реалізацій L2 і більш далеких від процесора рівнів кешу використовують індексування за фізичними адресами
Досить тривалий час кеші використовували для тегів як фізичні, так і віртуальні адреси, хоча віртуальне тегування в даний час зустрічається дуже рідко. Якщо TLB-запит закінчується раніше запиту в кеш-пам'ять, фізичний адресу буде доступний для порівняння з тегом до моменту, коли це буде необхідно, і, отже, віртуальне тегування не потрібно. Великі кеші частіше тегуються фізичними адресами, і лише невеликі швидкодіючі кеші використовують для тегів віртуальні адреси. У сучасних процесорах загального призначення, віртуальне тегування замінено на механізм vhints, описаний далі.

### Ієрархія кешів в сучасних мікропроцесорах
Більшість сучасних процесорів містять у собі кілька взаємодіючих кешів.

#### Спеціалізовані кеші
Суперскалярні процесори здійснюють доступ до пам'яті з декількох етапів конвеєра: читання інструкцій (instruction fetch), трансляція віртуальних адрес у фізичні, читання даних (data fetch). Очевидним рішенням є використання різних фізичних кешів для кожного з цих випадків, щоб не було боротьби за доступ до одного з фізичних ресурсів з різних стадій конвеєра. Таким чином, наявність конвеєра зазвичай призводить до наявності, принаймні, трьох роздільних кешів: кеш інструкцій, кеш трансляцій TLB і кеш даних, кожен з яких спеціалізується на своєму завданні.
Конвеєрні процесори, що використовують роздільні кеші для даних і інструкцій (такі процесори зараз повсюдні), називаються процесорами з Гарвардською архітектурою. Спочатку даний термін застосовувався для комп'ютерів, у яких інструкції і дані розділені повністю і зберігаються в різних пристроях пам'яті. Однак таке повне розділення не виявилося популярним, і більшість сучасних комп'ютерів мають один пристрій основної пам'яті, тому можуть вважатися машинами з архітектурою фон Неймана.

#### Багаторівневі кеші
Однією з проблем є фундаментальна проблема балансу між затримками кешу і інтенсивністю влучень. Великі кеші мають більш високий відсоток влучень але, разом з тим, і велику затримку. Щоб послабити протиріччя між цими двома параметрами, більшість комп'ютерів використовує кілька рівнів кешу, коли після маленьких і швидких кешів знаходяться більш повільні великі кеші (зараз — сумарно до 3 рівнів в ієрархії кешу).
У поодиноких випадках реалізують 4 рівні кеш-пам'яті.
Багаторівневі кеші зазвичай працюють в послідовності від менших кешів до великих. Спочатку відбувається перевірка найменшого і заразом — найшвидшого кешу першого рівня (L1), у разі попадання процесор продовжує роботу на високій швидкості. Якщо менший кеш дав промах, перевіряється наступний, трохи більший і більш повільний кеш другого рівня (L2), і так далі, поки не буде запиту до основного ОЗП.
По мірі того, як різниця затримок між ОЗП і найшвидшим кешем збільшується, в деяких процесорах збільшують кількість рівнів кешу (у деяких — до 3х рівнів на кристалі). Наприклад, процесор Alpha 21164 в 1995 році мав накристальний кеш 3го рівня в 96 КБ; IBM POWER4 у 2001 році мав до чотирьох кешу L3 32 МБ на окремих кристалах, що використовуються спільно декількома ядрами; Itanium 2 у 2003 році мав 6 МБ кеш L3 на кристалі; Xeon MP під кодом «Tulsa» у 2006 році — 16 МБ кешу L3 на кристалі, спільний на 2 ядра; Phenom II в 2008 році — до 6 МБ універсального кешу L3; Intel Core i7 у 2008 році — 8 МБ накристалльного кешу L3, який є інклюзивним та поділяється між усіма ядрами. Користь від кешу L3 залежить від характеру звернень програми в пам'ять.
Нарешті, з іншого боку ієрархії пам'яті знаходиться регістровий файл самого мікропроцесора, який можна розглядати як невеликий і найшвидший кеш в системі зі спеціальними властивостями (наприклад, статичне планування компілятором при розподілі регістрів). Детальніше див. loop nest optimization. Регістрові файли також можуть мати ієрархію: Cray-1 (у 1976 році) мав 8 адресних «A»-регістрів і 8 скалярних «S»-регістрів загального призначення. Також машина містила набір з 64 адресних «B» і 64 скалярних «T» регістрів, звернення до яких було довше, але все ж значно швидше основний ОЗП. Ці регістри були введені через відсутність в машині кешу даних (хоча кеш команд в машині був)
- Витребувані дані зчитуються з кешу першого (англ. L1) рівня.
- Витребувані дані зчитуються з кешу другого (англ. L2) рівня.
- У разі відсутності потрібних даних в кешах, проводиться читання з ОЗП.

#### Ексклюзивність (винятковість) і інклюзивність
Для багаторівневих кешів потрібно робити нові архітектурні рішення.
Наприклад, в деякому процесорі можуть вимагати, щоб всі дані, що зберігаються в кеші L1, зберігалися також і в кеш-пам'яті L2. Такі пари кешів називають строго інклюзівними (англ. inclusive). Інші процесори (наприклад, AMD Athlon) можуть не мати такого вимоги, тоді кеші називаються ексклюзивні (виняткові) — дані можуть бути або в L1 або L2 кеш, але ніколи не можуть бути одночасно в обох.
Досі іншим процесорам (таким, як Pentium II, Pentium III і Pentium 4) не потрібні, щоб дані в кеші першого рівня також розміщувалися в кеші другого рівня, тим не менш, вони продовжують робити. Немає ніякого універсального загальноприйнятого імені для цієї проміжної політики, хоча часто використовується термін головним чином інклюзівно (англ. mainly inclusive).
Перевага виняткових кешів в тому, що вони зберігають більше даних. Це перевага більше, коли винятковий кеш L1 порівнянний за розміром з кешем L2, і менше, якщо кеш L2 у багато разів більше, ніж кеш L1. Коли L1 пропускає і L2 отримує доступ у разі попадання, рядок кешу попадання в L2 обмінюється з рядком в L1.

#### Victim cache
Victim cache або Victim buffer (дослівно «Кеш жертв») — це невеликий спеціалізований кеш, зберігає ті кеш-лінії, які нещодавно були витіснені з основного кешу мікропроцесора при їх заміщення. Цей кеш розташовується між основним кешем і його англ. refill path. Зазвичай кеш жертв є повністю асоціативним і служить для зменшення кількості конфліктних промахів (conflict miss). Багато часто використовувані програми не вимагають повного асоціативного відображення для всіх спроб доступу до пам'яті. За статистикою лише невелика частка звернень до пам'яті вимагає високого ступеня асоціативності. Саме для таких звернень є кеш жертв, що надає високу асоціативність для таких рідкісних запитів. Був запропонований Norman Jouppi (DEC) в 1990. Розмір такого кешу може становити від 4 до 16 кеш-ліній.

#### Кеш трас
Одним з найбільш екстремальних випадків спеціалізації кешів можна вважати кеш трас (англ. trace cache), використовуваний в процесорах Intel Pentium 4. Кеш трас — це механізм для збільшення пропускної здатності завантаження інструкцій і для зменшення тепловиділення (у разі Pentium 4) за рахунок зберігання декодованих трас інструкцій. Таким чином цей кеш виключав роботу декодера при повторному виконанні  коду, що нещодавно виконувався
Однією з ранніх публікацією про кеші трас була стаття колективу авторів (Eric Rotenberg, Steve Bennett і Jim Smith), що вийшла в 1996 році під назвою «Trace Cache: a Low Latency Approach to High Bandwidth Instruction Fetching.» (Кеш трас: низколатентный підхід для забезпечення високої пропускної спроможності завантаження інструкцій).
Кеш трас зберігає декодовані інструкції або після їх декодування, або після закінчення їх виконання. Узагальнюючи, інструкції додаються в кеш трас в групах, що представляють собою або базові блоки, або динамічні траси. Динамічна траса (шлях виконання) складається тільки з інструкцій, результати яких були значимі (використовувалися згодом), і видаляє інструкції, які знаходяться в не які працюють гілках, крім того, динамічна траса може бути об'єднанням декількох базових блоків. Така особливість дозволяє пристрою підвантаження інструкцій у процесорі завантажувати відразу декілька базових блоків без необхідності піклуватися про наявність розгалужень у потоці виконання.
Лінії трас зберігаються в кеші трас за адресами, відповідним лічильника інструкцій першої машинної команди з траси, до яких доданий набір ознак передбачення розгалужень. Така адресація дозволяє зберігати різні траси виконання, що починаються з однієї адреси, але представляють різні ситуації по результату передбачення розгалужень. На стадії підвантаження інструкції (instruction fetch) конвеєра інструкцій для перевірки попадання в кеш трас використовується як поточний лічильник інструкцій (program counter), так і стан провісника розгалужень. Якщо попадання сталося, лінія траси безпосередньо подається на конвеєр без необхідності опитувати звичайний кеш (L2) або основне ОЗП. Кеш трас подає машинні команди на вхід конвеєра, поки не скінчиться лінія траси, або поки не станеться помилка передбачення в конвеєрі. У разі промаху кеш трас починає будувати таку лінію траси, завантажуючи машинний код з кешу або з пам'яті.
Схожі кеші трас використовувалися в Pentium 4 для зберігання декодованих мікрооперацій і мікрокоду, що реалізує складні x86-інструкції. Smith, Rotenberg and Bennett's paper См повний текст роботи в Citeseer.

## Реалізації

### Історія
У ранні роки мікропроцесорних технологій доступу в пам'ять був лише трохи повільніше доступу до процесорним регістрів. Але з 1980х розрив у продуктивності між процесорами і пам'яттю став наростати. Мікропроцесори удосконалювалися швидше, ніж пам'ять, особливо в плані частоти функціонування, таким чином, пам'ять ставала вузьким місцем при досягненні повної продуктивності від системи. Хоча було технічно можливим мати основну пам'ять настільки ж швидко, як і процесор, був обраний більш економічний шлях: використовувати надмірну кількість низькошвидкісний пам'яті, але ввести в систему невелику, але швидку кеш-пам'ять, для пом'якшення розриву в продуктивності. В результаті отримали на порядок великі обсяги пам'яті, приблизно за ту ж ціну і з невеликими втратами загальної продуктивності.
Читання даних з кешу для сучасних процесорів зазвичай займає більш одного такту. Час виконання програм є чутливим до затримок читання з кешу даних першого рівня. Багато зусиль розробників, а також потужності і площі кристала при створенні процесора відводиться для прискорення роботи кешів.
Найпростішим кешем є віртуально індексований кеш прямого відображення. Віртуальний адресу підраховується за допомогою суматора, відповідна частина адреси виділяється і використовується для індексування SRAM, який поверне завантажуються дані. Дані можуть бути вирівняні по байтовим кордонів байтовому сдвигателе і потім передані наступної операції. При такому читанні не потрібна якась перевірка тегів, фактично немає навіть необхідності зчитувати тег. На більш пізніх стадіях конвейєра, перед закінченням виконання інструкції читання потрібно читання тегу і його порівняння з віртуальним адресою, щоб упевнитися, що сталося попадання в кеш. Якщо ж був промах, потрібно читання з пам'яті або більш повільного кешу з подальшим оновленням розглянутого кешу і перезапуском конвеєра.
Асоціативний кеш більш складний, тому що певний варіант тегу потрібно вважати для визначення, яку частину кешу вибрати. Кеш N-way set-associative першого рівня зазвичай зчитує одночасно всі N можливих тегів і N даних паралельно, потім проводить порівняння тегів з адресою і вибір даних, асоційованих з збіглася тегом. Кеш 2-го рівня в цілях економії енерговиділення іноді виконують спочатку читання тегів, і тільки потім читання одного елемента даних SRAM-даних.
Діаграма справа повинна показати, як відбувається використання різних частин адреси. Біт 31 адреси є найбільш значущим бітом (старшим), біт 0 — найменш значущим бітом (молодшим). На діаграмі показані дві SRAM, індексація і мультиплексування для 4 КБ, 2-way set-associative, віртуально індексованого і віртуально тегированного кешу з 64байтними блоками, 32бітною шириною читання і 32битным віртуальним адресою.
Оскільки кеш має розмір 4 КБ і лінії розміром 64 байта, у ньому зберігається 64 лінії, і ми можемо вважати за два рази з тегу SRAM, який містить 32 стовпця, кожен з яких містить кілька 21-бітних тегів. Хоча може бути використана будь-яка функція віртуальної адресації бітів 31 6, щоб індексувати тег і дані SRAM, найпростіше скористатися молодшими розрядами. Так само, тому що обсяг кешу складає 4 кБ, кеш має чотирибайтний шлях для читання і читання проводиться за двома шляхами для кожного доступу, дані SRAM складають 512 рядів шириною 8 байтів.
Більш сучасний кеш, можливо, був би 16-кілобайтним, чотирьохшляховим, набір-асоціативним, віртуально індексовані, віртуально влучаємим і фізично відмічаємим (тегом), з 32-бітовими рядками, 32-бітної шириною шини читання і 36-бітним фізичним адресуванням. Рекурентне співвідношення шляху читання для такого кешу виглядає дуже схоже з розглянутими вище. Замість тегів читаються віртуальні потрапляння (англ. vhits), і знову проводиться відповідність підмножини віртуального адресою. Пізніше, в конвеєрі, віртуальна адреса переводиться у фізичну адресу TLB, і проводиться читання фізичного тегу (тільки одне, так як віртуальне потрапляння поставляє шлях для читання кешу). В кінці фізична адреса порівнюється з фізичним тегом, щоб визначити, чи відбулося попадання.
Деякі процесори SPARC мали прискорені на кілька затримок затвора (англ. gate delay) L1 кеш за рахунок використання SRAM-декодерів замість суматора віртуальних адрес. Детальніше див. Sum addressed decoder.

### В X86
Коли x86 мікропроцесори досягли частот у 20 і більше мегагерц (починаючи з Intel 80386), для збільшення продуктивності в них було додано невелику кількість швидкої кеш-пам'яті. Це було необхідно через те, що використовується як системна ОПЕРАТИВНОЇ пам'яті DRAM мала значні затримки (до 120 нс), і вимагала такти для оновлення. Кеш був побудований на базі дорожчий, але значно більш швидкої SRAM, яка в ті часи мала затримки близько 10 нс. Ранні кеші були зовнішніми по відношенню до процесора і часто розташовувалися на материнській платі як 8 або 9 мікросхем в корпусах DIP, розташовані в сокети для можливості збільшення або зменшення розміру кешу. Деякі версії процесора I386 підтримували від 16 до 64 КБ зовнішнього кешу.
З виходом процесора Intel 80486 8 КБ кешу було інтегровано безпосередньо на кристал мікропроцесора. Цей кеш був названий L1 (першого рівня, англ. level 1), щоб відрізняти його від більш повільного кешу на материнській платі, названого L2 (другого рівня, англ. level 2). Останні були значно більше, аж до 256 КБ.
В подальшому випадки відділення кешу проводилися, виходячи лише з міркувань маркетингової політики, наприклад, у мікропроцесорі Celeron, побудованому на ядрі Pentium II.
У мікропроцесорі Pentium використовується роздільний кеш команд і даних. Буфер трансляції адрес (TLB) перетворює адреса в ОЗП відповідний адресу в кеші. Кеш даних Pentium використовує метод зворотного запису (англ. write-back), який дозволяє модифікувати дані в кеші без додаткового звернення до оперативної пам'яті (дані записуються в ОЗП тільки при видаленні з кешу) і протокол MESI (Modified, Exclusive, Shared, Invalid), який забезпечує когерентність даних в кешах процесорів і в ОЗП при роботі в мультипроцесорної системи.
Кожен з окремих кешів, даних і команд мікропроцесора Pentium MMX має обсягом 16 кБ і містить два порти, по одному для кожного виконавчого конвеєра. Кеш даних має буфер трансляції адрес (TLB).
Наступний варіант реалізації кешів у x86 з'явився в Pentium Pro, в якому кеш другого рівня (об'єднаний для даних і команд, розміром 8 кБ) розміщений в одному корпусі з процесором і кешем першого рівня, розміром 8 кБ, роздільним для даних і команд, і підняв його частоту до частоти ядра. Пізніше кеш другого рівня став розміщуватися на тому ж кристалі, що і процесор. Подвійна незалежна шина (TLB)англ. DIB), нова архітектура кеш-пам'яті, використовує різні шини для підключення процесорного ядра з основною оперативною пам'яттю. Кеш першого рівня двухпортовий, неблокуючий, підтримує одну операцію завантаження і одну операцію запису за такт. Працює на тактовій частоті процесора. За такт передається 64 біта.
У мікропроцесорі Pentium II кеш першого рівня збільшено — 16 кбайт для даних і 16 кбайт для команд. Для кешу другого рівня використовується BSRAM, розташована на одній з процесором платі у картриджі S. E. C. для установки в Slot 1.
З зростанням популярності багатоядерних процесорів на кристал стали додавати кеш третього рівня, названі L3. Цей рівень кешу може бути загальним для декількох ядер і реалізовувати ефективну взаємодію між ядрами. Його обсяг зазвичай більше сумарного обсягу кешу всіх підключених до нього ядер і може досягати 16 МБ.
Популярним кеш на материнській платі залишався до ери виходу Pentium MMX і вийшов з ужитку з введенням SDRAM і зростанням різниці між частотою шини процесора і частотою ядра процесора: кеш на материнській платі став лише трохи швидше основний ОЗП.

#### Приклад кешу (процесорне ядро К8)
Наведена схема кешів ядра мікропроцесорів AMD K8, на якій видно як спеціалізовані кеші, так і їх багаторівневість.
Ядро використовує чотири різних спеціалізованих кешу: кеш інструкцій, TLB інструкцій, TLB даних і кеш даних:
- Кеш інструкцій складається з 64-байтних блоків, які є копією основної пам'яті, і може завантажувати до 16 байтів за такт. Кожен байт у цьому кеші зберігається в 10 бітах, а не у 8, причому в додаткових бітах відзначені кордону інструкцій (т. о. кеш проводить часткове преддекодирование). Для перевірки цілісності даних використовується лише контроль парності, а не ECC, так як біт парності займає менше місця, а в разі збою пошкоджені дані можна оновити правильною версією з пам'яті.
- TLB інструкцій, що містять копії записів з таблиці сторінок. На кожен запит читання команд потрібно трансляція математичних адрес у фізичні. Записи про трансляції бувають 4 — і 8-байтними, і TLB розбитий на 2 частини, відповідно одна для 4 КБ відображень і інша для 2 і 4 МБ відображень (великі сторінки). Таке розбиття спрощує схеми повністю асоціативного пошуку в кожній з частин. ОС і додатки можуть використовувати відображення різного розміру для частин віртуального адресного простору.
- TLB даних є здвоєним, і обидва буфера містять однаковий набір записів. Їх здвоєння дозволяє виробляти кожен такт трансляцію для двох запитів до даних одночасно. Так само, як і TLB інструкцій, цей буфер розділений між записами двох видів.
- Кеш даних містить 64-байтні копії фрагментів пам'яті. Він розділений на 8 банків (банок), кожний з яких містить по 8 кілобайт даних. Кеш дозволяє проводити по два запити до 8-байтовим даними кожен такт, за умови, що запити будуть оброблені різними банками. Тегові структури в кеші продубльовані, так як кожен 64-байтний блок розподілений по всьому 8 банкам. Якщо відбувається 2 запиту в один такт, вони працюють з власною копією теговій інформації.

Також в цьому ядрі використовуються багаторівневі кеші: дворівневі TLB інструкцій і даних (на другому рівні зберігаються лише записи про 4-кб відображеня), і кеш другого рівня (L2), уніфікований для роботи як з кешами даних та інструкцій 1-го рівня, так і для різних TLB. Кеш L2 є ексклюзивним для даних L1 L1 і інструкцій, тобто кожен ваш 8-байтовий фрагмент може знаходитися або в L1 інструкцій, або в даних L1 або L2. Винятком можуть бути лише байти, складові запису PTE, які можуть перебувати одночасно в TLB і в кеші даних під час обробки віртуального відображення з боку ОС. В такому випадку ОС відповідає за своєчасний скидання TLB після оновлення записів трансляції.

### DEC Alpha
У мікропроцесорі DEC Alpha 21164 (випущений в листопаді 1995 року з тактовою частотою 333 МГц) кеш першого рівня може підтримувати деяка кількість (до 21) необроблених промахів. Є шестиелементний файл адрес необроблених промахів (англ. miss address file, MAF), кожен елемент якого містить адресу та регістр для завантаження при промаху (якщо адреси промаху належать одним рядком кешу, то в MAF вони розглядаються як один елемент).
Крім роздільних кешу L1 зі наскрізним записом, на кристалі процесора розташовані частково-асоціативний кеш L2 зі зворотним записом і контролер кешу L3, який працює як у синхронному, так і в асинхронному режимі.
У випущеному в березні 1997 року DEC Alpha 21164PC зовнішній кеш другого рівня; обсяг кешу команд збільшено до 16 кБ.
У мікропроцесорі DEC Alpha 21264 немає кешу другого рівня (контролер якого, тим не менш, розміщується на кристалі), але кеш першого рівня збільшено до 128 кбайт (по 64 кбайт для кешу команд і кеш даних відповідно).

### PA-RISC
Розробка Hewlett-Packard для наукових та інженерних обчислень PA-8000 містить буфер переупорядковування адрес (англ. ARB), що відслідковує всі команди завантаження/збереження, який дозволяє скоротити затримку адресування зовнішньої кеш-пам'яті даних і команд, яка в даному процесорі може мати обсяг до 4 МБ. Тим не менш, навіть ефективне управління зовнішнім кешем за допомогою високошвидкісних ліній управління і предвибірки даних і команд з основної пам'яті в кеш не скомпенсировало невисоку швидкість і високу вартість.
Усунути вказані недоліки вдалося PA-8500, в якому за рахунок техпроцесу 0,25 мкм вдалося додати на кристал 512 кБ кешу інструкцій і 1 МБ кешу даних.

### PowerPC
Побудований на гарвардській архітектурі PowerPC 620 містить два вбудованих кешу, ємністю 32 кБ кожний, які мають власні блоки управління пам'яттю (англ. MMU) і функціонують незалежно один від одного. Команди і адреси переходів зберігається в кеші BTAC (англ. Branch Target Adress Cache).
Шинний інтерфейс процесора включає повну реалізацію підтримки кешу другого рівня (обсягом до 128 МБ, працює на частоті процесора удвічі/вчетверо меншою), і для управління роботою зовнішнього кешу не вимагає додаткових тактів. Реалізована комбінація наскрізний і зворотного запису, а також підтримка протоколу MESI.

### MIPS
Своя специфіка у кешу L1, застосовуваного в RA-10000, — кожна команда в кеші забезпечена додатковим четырехбитным тегом, який використовується в подальшому декодуванні та класифікації команди.

title: Кеш процесора

wikitext:
{{Сирий переклад|дата=вересень 2015}}

'''Кеш процесора''' — [[кеш]], який використовується [[Центральний процесор|центральним процесором]] ({{lang-en|CPU}}) для скорочення середнього часу доступу до [[Комп'ютерна пам'ять|пам'яті комп'ютера]]. Кеш — це швидша і менша за розміром пам'ять, яка зберігає копії даних, що часто використовуються, з головної пам'яті.

Коли процесору потрібно звернутися в пам'ять для читання або запису даних, він спочатку перевіряє, чи є їхні копії в кеші. У разі успіху перевірки процесор виконує операцію використовуючи кеш, що працює швидше ніж при використанні повільнішої основної пам'яті. Детальніше про затримки пам'яті див. [[затримки]] ({{lang-en|SDRAM latency}}) [[SDRAM]]: tCAS, tRCD, tRP, tRAS

Більшість сучасних мікропроцесорів для настільних комп'ютерів і серверів мають щонайменше три незалежних кеші: '''кеш інструкцій''' для прискорення завантаження [[Машинний код|машинного коду]], '''кеш даних''' для прискорення читання і запису даних і [[буфер асоціативної трансляції]] (TLB) для прискорення трансляції віртуальних (логічних) адрес у фізичні, як для інструкцій, так і для даних. Кеш даних часто реалізується у вигляді багаторівневого кешу (L1, L2, L3)..

Збільшення розміру кеш-пам'яті може позитивно впливати на продуктивність майже всіх [[Застосунок|застосунків]], хоча в деяких випадках ефект незначний. Робота кеш-пам'яті зазвичай прозора для програміста, проте для її ефективного використання у деяких випадках застосовуються спеціальні алгоритмічні прийоми, які змінюють порядок обходу даних в [[ОЗП]] або підвищують їх локальність (наприклад, при [[Блочна матриця|блочному множенні матриць]]).

== Принцип роботи ==
[[Файл:cache,basic,ru.svg|right|thumb|350x350px|Діаграма кешів ЦПУ]]
Даний розділ описує типовий кеш даних і деякі види кешу інструкцій; TLB може бути влаштований складніше, а кеш інструкцій — простіше. На діаграмі праворуч зображені основна і кеш-пам'ять. Кожен рядок — група комірок пам'яті, що містить дані, організовані в'' кеш-лінії''. Розмір кожної кеш-лінії може розрізнятися у різних процесорах, але для більшості x86-процесорів він становить 64 байта. Розмір кеш-лінії зазвичай більше розміру даних, до якого є можливим доступ з однієї машинної команди (типові розміри від 1 до 16 байт). Кожна група даних в пам'яті розміром у 1 кеш-лінію має порядковий номер. Для основної пам'яті цей номер є адресою пам'яті з відкинутими молодшими бітами. У кеші кожної кеш-лінії додатково ставиться у відповідність '''тег''', який є адресою продубльованих в цій кеш-лінії даних в основній пам'яті.

При звертанні процесора в пам'ять спочатку проводиться перевірка, чи зберігає кеш запитувані з пам'яті дані. Для цього проводиться порівняння адреси запиту з значеннями всіх тегів кешу, в яких ці дані можуть зберігатися. Випадок збігу з тегом якої-небудь кеш-лінії називається попаданням в кеш ([[Англійська мова|англ]]. ''cache hit''), зворотний випадок називається кеш-промахом ({{lang-en|cache miss}}). Попадання в кеш дозволяє процесору негайно провести читання або запис даних у кеш-лінії з збіглася тегом. Відношення кількості попадань в кеш до загальної кількості запитів до пам'яті називають рейтингом влучень ({{lang-en|hit rate}}), воно є мірою ефективності кешу для обраного алгоритму або програми.

У разі промаху в кеші виділяється новий запис, у тег якого записується адреса поточного запиту, а в саму кеш-лінію — дані з пам'яті після їх прочитання або дані для запису в пам'ять. Промахи з читання затримують виконання, оскільки вони вимагають запиту даних в більш повільної основної пам'яті. Промахи по запису можуть не давати затримку, оскільки потрібні дані можуть бути збережені в кеші, а запис їх в основну пам'ять можна зробити у фоновому режимі. Робота кешу інструкцій багато в чому схожа на вищенаведений алгоритм роботи кешу даних, але для інструкцій виконуються тільки запити на читання. Кеш інструкцій і даних можуть бути розділені для збільшення продуктивності (принцип, використовуваний в [[Гарвардська архітектура|Гарвардській архітектурі]]) або об'єднані для спрощення апаратної реалізації.

Для додавання даних в кеш після кеш-промаху може знадобитися витіснення ([[Англійська мова|англ]]. ''evict'') раніше записаних даних. Для вибору заміщаючого рядка кешу використовується евристика, звана ''політика заміщення'' ([[Англійська мова|англ]]. ''replacement policy''). Основною проблемою алгоритму є передбачення, який рядок найімовірніше не буде потрібно для подальших операцій. Якісні передбачення складні, і апаратні кеші використовують прості правила, такі, як LRU. Відмітка деяких областей пам'яті як ''некешованих'' ({{lang-en|non cacheable}}) покращує продуктивність за рахунок заборони кешування рідко використовуваних даних. Промахи для такої пам'яті не створюють копію даних в кеші.

При запису даних у кеш повинен існувати певний момент часу, коли вони будуть записані в основну пам'ять. Це час контролюється ''політикою запису'' ({{lang-en|write policy}}). Для кешу зі ''наскрізним записом'' ({{lang-en|write-through}}) будь-який запис у кеш приводить до негайного запису в пам'ять. Інший тип кешів, зворотна запис {{lang-en|write-back}} (іноді також званий ''copy-back''), відкладає запис на більш пізній час. У таких кешах відстежується стан кеш-лінійок ще не скинутих в пам'ять (відмітка бітом «брудний» {{lang-en|dirty}}). Запис в пам'ять проводиться при витісненні подібного рядка кешу. Таким чином, промах в кеші, що використовує політику зворотного запису, може вимагати двох операцій доступу в пам'ять, один для скидання стану старого рядка і інший — для читання нових даних.

Існують також змішані політики. Кеш може бути із наскрізним записом ({{lang-en|write-through}}), але для зменшення кількості транзакцій на шині записи можуть тимчасово міститися в чергу і об'єднуватися один з одним.

Дані в основній пам'яті можуть змінюватися не тільки процесор, але і периферією, що використовує [[прямий доступ до пам'яті]], або іншими процесорами багатопроцесорні системи. Зміна даних призводить до застарівання їх копії в кеші (стан ''stale''). В іншої реалізації, коли один процесор змінює дані в кеші, копії цих даних в кешах інших процесорів будуть помічені як stale. Для підтримки вмісту декількох кешів в актуальному стані використовується спеціальний протокол кеш когерентності.

=== Структура запису в кеші ===
Типова структура запису в кеші
{| border="1" style="width:30%; text-align:center"

| Блок даних
| тег
| біт актуальності
|}
Блок даних (кеш-лінія) містить безпосередню копію даних з основної пам'яті. Біт актуальності означає, що даний запис містить актуальну (найсвіжішу) копію.

Структура адреси
{| border="1" style="width:30%; text-align:center"

| тег
|індекс
|зміщення

|}
Адреса пам'яті, що розділяється (від старших біт до молодших) на Тег, індекс і зміщення. Довжина поля індексу дорівнює  <math>\lceil \log_2(cache\_rows) \rceil</math> біт і відповідає ряду (рядку) кешу, використовуваної для запису. Довжина зсуву дорівнює  <math>\lceil \log_2(data\_blocks) \rceil</math>.

=== Асоціативність ===
[[Файл:Cache,missrate.png|right|График эффективности кэша (количество промахов по оси ординат), в зависимости от степени ассоциативности и количества каналов. По оси абсцисс — размер кэша.]]
'''Асоціативність''' є компромісом. Перевірка більшого числа записів вимагає більше енергії, площі чипу, і, потенційно, часу. Якщо б існувало 10 місць, які алгоритм витіснення міг би відобразити місце в пам'яті, тоді перевірка наявності цього місця в кеші зажадала б переглянути 10 записів в кеші. З іншого боку, кеші з високою асоціативністю піддаються меншому кількості промахів (див. нижче «конфліктуючі промахи») і процесор витрачає менше часу на читання з повільної основної пам'яті. Існує емпіричне спостереження, що подвоєння асоціативності (від прямого відображення до 2-канальної або від 2- до 4-канальної) має приблизно такий же вплив на інтенсивність влучень (''hit rate''), що і подвоєння розміру кешу. Збільшення асоціативності понад 4 каналів приносить менший ефект для зменшення кількості промахів (''miss rate'') і зазвичай виробляється з інших причин, наприклад, через перетин віртуальних адрес.

В порядку погіршення (збільшення тривалості перевірки на потрапляння) та поліпшення (зменшення кількості промахів):
# кеш прямого відображення ({{lang-en|direct mapped cache}}) — найкращий час попадання і, відповідно, найкращий варіант для великих кешів;
# 2-канальний множинно-асоціативний кеш {{lang-en|2-way set associative cache}};
# 2-канальний skewed асоціативний кеш ({{lang-en|«the best for tradeoff …. caches whose sizes are in the range 4K-8K bytes» — André Seznec}});
# 4-канальний множинно-асоціативний кеш ({{lang-en|4-way set associative cache}});
# повністю асоціативний кеш, ({{lang-en|fully associative cache}}) — найкращий (найнижчий) відсоток промахів (''miss rate'') і найкращий варіант при надзвичайно високих витратах при промаху (''miss penalty'').
<gallery widths="300" perrow="3">
File:Direct mapped cache.JPG|Кеш прямого відображення
File:Cache nway.jpg|n-канальний множинно-асоціативний кеш
File:Fully associative.jpg|Повністю асоціативний кеш
</gallery>

==== Псевдо-ассоціативний кеш ====

=== Види промахів ===
''Промах з читання з кешу інструкцій. ''Зазвичай дає дуже велику затримку, оскільки процесор не може продовжувати виконання програми (принаймні, виконання поточного потоку) і змушений простоювати в очікуванні завантаження інструкції з пам'яті.

''Промах з читання з кешу даних''. Зазвичай дає меншу затримку, оскільки інструкції, які не залежать від запитаних даних, можуть продовжувати виконуватися, поки запит обробляється в основній пам'яті. Після отримання даних з пам'яті можна продовжувати виконання залежних інструкцій.

=== Категорії промахів (''Three Cs'') ===
* ''Compulsory misses'' — промахи, викликані першою згадкою потрібної адреси. Розміри кешів і їх асоціативність не впливають на кількість даних промахів. Попередня вибірка (prefetching), як програмну, так і апаратну, може допомогти, так само, як і збільшення розміру кеш-лінії (як виду апаратного вибору). Такі промахи іноді називають «холодними».
* ''Capacity misses ''— промахи, викликані виключно кінцевим розміром кешу, що відбуваються незалежно від ступеня асоціативності або розміру кеш-лінії. Графік таких промахів щодо розміру кешу може дати деяку міру тимчасової локальності (''temporal locality'') деякого набору запитів в пам'ять. Варто зауважити, що не існує поняття повного кешу, порожнього кешу або майже повного кешу, так як кеші процесора майже весь час мають кеш-лінії в зайнятому стані, і, отже, практично кожен заклад нової лінії зажадає гасіння вже зайнята.
* ''Conflict misses'' — промахи, викликані конфліктом. Їх можна уникнути, якщо б кеш не витіснив запис раніше. Можна додатково розділити на промахи, викликані відображенням (конкретним значенням асоціативності) і промахи заміщення, які викликані конкретним алгоритмом вибору записів для заміщення.

=== Трансляція адрес ===
Більша частина процесорів загального призначення реалізує якийсь варіант [[Віртуальна пам'ять|віртуальної пам'яті]]. Коротко кажучи, кожна програма, що виконується на машині, бачить власний спрощений адресний простір, що містить код і дані тільки цієї програми. Будь-яка програма використовує свій віртуальний адресний простір незалежно від його місцезнаходження у фізичній пам'яті.

Наявність віртуальної пам'яті вимагає від процесора проведення трансляції віртуальних (математичних) адрес, використовуваних програмою, у фізичні адреси, відповідні реальному розташуванню в ОЗП. Частина процесора, провідна це перетворення, називається пристрій управління пам'яттю (MMU). Для прискорення трансляцій в MMU доданий кеш нещодавно використаних відображень (відповідностей віртуальних і фізичних адрес), званий Translation Lookaside Buffer (TLB).

Для подальшого опису важливі три особливості процесу трансляції адрес:
* Затримка: Фізичний адресу буде отримано від MMU тільки через деякий час, аж до декількох тактів, після подачі на вхід MMU віртуального адреси з генератора адрес.
*  Ефект накладення: Кілька віртуальних адрес, які можуть відповідати одному фізичному. У більшості процесорів гарантується, що всі записи по фізичній адресою будуть здійснені в порядку, заданому програмою. Для виконання цієї властивості потрібна перевірка, що тільки один екземпляр копії даних з фізичної адреси знаходиться в даний момент в кеші.
* Одиниця відображення: Віртуальне адресний простір розбито на сторінки — блоки пам'яті фіксованого розміру, що починаються з адреси, кратних їх розміром. Наприклад, 4 ГБ адресного простору можна розділити на 1048576 сторінки по 4 КБ, для кожної з яких можливо незалежне відповідність фізичним сторінкам. У сучасних процесорах часто підтримується використання одночасно декількох розмірів сторінки, наприклад, 4 КБ і 2 МБ для x86-64, а в деяких сучасних AMD-процесорах ще і 1 ГБ.

Важливо також зауважити, що перші системи віртуальної пам'яті були дуже повільними, тому що вони вимагали перевірки таблиці сторінок (зберігається в основній ПАМ'ЯТІ) перед будь-яким програмним зверненням в пам'ять. Без використання кешування для відображень такі системи зменшують швидкість роботи з пам'яттю приблизно в 2 рази. Тому використання TLB дуже важливо і іноді його додавання в процесори передувало появі звичайних кешу даних та інструкцій.

По відношенню до віртуальної адресації кеші даних та інструкцій можуть бути поділені на 4 типи. Адреси в кешах використовуються для двох різних цілей: індексування і тегів.
* Physically indexed, physically tagged (PIPT) — фізично індексовані і фізично тегируемые. Такі кеші прості і уникають проблем з накладенням (aliasing), але вони повільні, так як перед зверненням в кеш потрібен запит фізичної адреси в TLB. Цей запит може викликати промах в TLB і додаткове звернення в основну пам'ять перед тим, як наявність даних буде перевірено в кеші.
* '' Virtually indexed, virtually tagged'' (VIVT) — віртуально індексовані і віртуально тегируемые. І для тегів, і для індексу використовується віртуальний адресу. Завдяки цьому перевірки наявності даних в кеші відбуваються швидше, не вимагаючи звернення до MMU. Однак виникає проблема накладання, коли кілька віртуальних адрес відповідають одному й тому ж фізичному. У цьому випадку дані будуть закешовані двічі, що сильно ускладнює підтримку когерентності. Іншою проблемою є омоніми, ситуації, коли один і той же віртуальний адресу (наприклад, у різних процесах) відображається різні фізичні адреси. Стає неможливим розрізнити такі відображення виключно по віртуальному індексу. Можливі рішення: скидання кешу при перемиканні між завданнями (''context switch''), вимога непересечения адресних просторів процесів, тегування віртуальних адрес ідентифікатором адресного простору (''address space ID, ASID'') або використання фізичних тегів. Також виникає проблема при зміні відображення віртуальних адрес у фізичні, що вимагає скидання кеш-ліній, для яких змінилося відображення.
* ''Virtually indexed, physically tagged'' (VIPT) — віртуально індексовані і фізично тегируемые. Для індексу використовується віртуальний адреса, а для тегу — фізичний. Перевагою над першим типом є менша затримка, оскільки можна шукати кеш-лінію одночасно з трансляцією адрес в TLB, однак порівняння тегу затримується до одержання фізичної адреси. Перевагою над другим типом є виявлення омонімів (''homonyms''), так як тег містить фізична адреса. Для даного типу потрібно більше біт для тегу, оскільки індексні біти використовують інший тип адресації.
* ''Physically indexed, virtually tagged ''— фізично індексовані і віртуально теговані кеші вважаються непотрібними і маргінальними і представляють виключно академічний інтерес.

Швидкість цих дій (затримка завантаження з пам'яті) критично важлива для продуктивності процесорів, і тому більшість сучасних L1-кешів є віртуально індексованими, що як мінімум дозволяє блоку MMU робити запит в TLB одночасно з запитом даних їх кеш-пам'яті.

=== Віртуальне тегування і механізм vhints ===
Але віртуальна індексація не є найкращим вибором для інших рівнів кешу. Вартість виявлення перетину віртуальних адрес (''aliasing'') зростає із збільшенням розміру кешу і, в результаті, більшість реалізацій L2 і більш далеких від процесора рівнів кешу використовують індексування за фізичними адресами

Досить тривалий час кеші використовували для тегів як фізичні, так і віртуальні адреси, хоча віртуальне тегування в даний час зустрічається дуже рідко. Якщо TLB-запит закінчується раніше запиту в кеш-пам'ять, фізичний адресу буде доступний для порівняння з тегом до моменту, коли це буде необхідно, і, отже, віртуальне тегування не потрібно. Великі кеші частіше тегуються фізичними адресами, і лише невеликі швидкодіючі кеші використовують для тегів віртуальні адреси. У сучасних процесорах загального призначення, віртуальне тегування замінено на механізм ''vhints'', описаний далі.

=== Ієрархія кешів в сучасних мікропроцесорах ===
Більшість сучасних процесорів містять у собі кілька взаємодіючих кешів.

==== Спеціалізовані кеші ====
Суперскалярні процесори здійснюють доступ до пам'яті з декількох етапів [[Конвеєр команд|конвеєра]]: читання інструкцій (''instruction fetch''), трансляція віртуальних адрес у фізичні, читання даних (''data fetch''). Очевидним рішенням є використання різних фізичних кешів для кожного з цих випадків, щоб не було боротьби за доступ до одного з фізичних ресурсів з різних стадій конвеєра. Таким чином, наявність конвеєра зазвичай призводить до наявності, принаймні, трьох роздільних кешів: кеш інструкцій, кеш трансляцій [[Буфер асоціативної трансляції|TLB]] і кеш даних, кожен з яких спеціалізується на своєму завданні.

Конвеєрні процесори, що використовують роздільні кеші для даних і інструкцій (такі процесори зараз повсюдні), називаються процесорами з [[Гарвардська архітектура|Гарвардською архітектурою]]. Спочатку даний термін застосовувався для комп'ютерів, у яких інструкції і дані розділені повністю і зберігаються в різних пристроях пам'яті. Однак таке повне розділення не виявилося популярним, і більшість сучасних комп'ютерів мають один пристрій основної пам'яті, тому можуть вважатися [[Архітектура фон Неймана|машинами з архітектурою фон Неймана]].

==== Багаторівневі кеші ====
Однією з проблем є фундаментальна проблема балансу між затримками кешу і інтенсивністю влучень. Великі кеші мають більш високий відсоток влучень але, разом з тим, і велику затримку. Щоб послабити протиріччя між цими двома параметрами, більшість комп'ютерів використовує кілька рівнів кешу, коли після маленьких і швидких кешів знаходяться більш повільні великі кеші (зараз — сумарно до 3 рівнів в ієрархії кешу).

У поодиноких випадках реалізують 4 рівні кеш-пам'яті.

Багаторівневі кеші зазвичай працюють в послідовності від менших кешів до великих. Спочатку відбувається перевірка найменшого і заразом — найшвидшого кешу першого рівня (L1), у разі попадання процесор продовжує роботу на високій швидкості. Якщо менший кеш дав промах, перевіряється наступний, трохи більший і більш повільний кеш другого рівня (L2), і так далі, поки не буде запиту до основного ОЗП.

По мірі того, як різниця затримок між ОЗП і найшвидшим кешем збільшується, в деяких процесорах збільшують кількість рівнів кешу (у деяких — до 3х рівнів на кристалі). Наприклад, процесор [[DEC Alpha|Alpha 21164]] в 1995 році мав накристальний кеш 3го рівня в 96 КБ; IBM [[POWER4]] у 2001 році мав до чотирьох кешу L3 32 МБ на окремих кристалах, що використовуються спільно декількома ядрами; [[Itanium|Itanium 2]] у 2003 році мав 6 МБ кеш L3 на кристалі; Xeon MP під кодом «Tulsa» у 2006 році — 16 МБ кешу L3 на кристалі, спільний на 2 ядра; [[Phenom II]] в 2008 році — до 6 МБ універсального кешу L3;[[ Intel Core i7]] у 2008 році — 8 МБ накристалльного кешу L3, який є інклюзивним та поділяється між усіма ядрами. Користь від кешу L3 залежить від характеру звернень програми в пам'ять.

Нарешті, з іншого боку ієрархії пам'яті знаходиться [[регістровий файл]] самого мікропроцесора, який можна розглядати як невеликий і найшвидший кеш в системі зі спеціальними властивостями (наприклад, статичне планування компілятором при розподілі регістрів). Детальніше див. [[loop nest optimization]]. Регістрові файли також можуть мати ієрархію: [[Cray-1]] (у 1976 році) мав 8 адресних «A»-регістрів і 8 скалярних «S»-регістрів загального призначення. Також машина містила набір з 64 адресних «B» і 64 скалярних «T» регістрів, звернення до яких було довше, але все ж значно швидше основний ОЗП. Ці регістри були введені через відсутність в машині кешу даних (хоча кеш команд в машині був)
<gallery widths="300">
File:Processor cacheL1.png|Витребувані дані зчитуються з кешу першого ({{lang-en|L1}}) рівня.
File:Processor cacheL2.png|Витребувані дані зчитуються з кешу другого ({{lang-en|L2}}) рівня.
File:Processor cacheM.png|У разі відсутності потрібних даних в кешах, проводиться читання з ОЗП.
</gallery>

==== Ексклюзивність (винятковість) і інклюзивність ====
Для багаторівневих кешів потрібно робити нові архітектурні рішення.

Наприклад, в деякому процесорі можуть вимагати, щоб всі дані, що зберігаються в кеші L1, зберігалися також і в кеш-пам'яті L2. Такі пари кешів називають '''строго інклюзівними''' ({{lang-en|inclusive}}). Інші процесори (наприклад, AMD Athlon) можуть не мати такого вимоги, тоді кеші називаються '''ексклюзивні (виняткові) '''— дані можуть бути або в L1 або L2 кеш, але ніколи не можуть бути одночасно в обох.

Досі іншим процесорам (таким, як Pentium II, Pentium III і Pentium 4) не потрібні, щоб дані в кеші першого рівня також розміщувалися в кеші другого рівня, тим не менш, вони продовжують робити. Немає ніякого універсального загальноприйнятого імені для цієї проміжної політики, хоча часто використовується термін '''головним чином інклюзівно''' ({{lang-en|mainly inclusive}}).

Перевага виняткових кешів в тому, що вони зберігають більше даних. Це перевага більше, коли винятковий кеш L1 порівнянний за розміром з кешем L2, і менше, якщо кеш L2 у багато разів більше, ніж кеш L1. Коли L1 пропускає і L2 отримує доступ у разі попадання, рядок кешу попадання в L2 обмінюється з рядком в L1.

==== Victim cache ====
{{Якір|Кеш жертв}}''Victim cache'' або ''Victim buffer'' (дослівно «Кеш жертв») — це невеликий спеціалізований кеш, зберігає ті кеш-лінії, які нещодавно були витіснені з основного кешу мікропроцесора при їх заміщення. Цей кеш розташовується між основним кешем і його {{lang-en|refill path}}. Зазвичай кеш жертв є повністю асоціативним і служить для зменшення кількості конфліктних промахів (''conflict miss''). Багато часто використовувані програми не вимагають повного асоціативного відображення для всіх спроб доступу до пам'яті. За статистикою лише невелика частка звернень до пам'яті вимагає високого ступеня асоціативності. Саме для таких звернень є кеш жертв, що надає високу асоціативність для таких рідкісних запитів. Був запропонований[[ Norman Jouppi]] (DEC) в 1990. Розмір такого кешу може становити від 4 до 16 кеш-ліній.

==== Кеш трас ====
Одним з найбільш екстремальних випадків спеціалізації кешів можна вважати '''кеш трас''' ({{lang-en|trace cache}}), використовуваний в процесорах [[Intel Pentium 4]]. Кеш трас — це механізм для збільшення пропускної здатності завантаження інструкцій і для зменшення тепловиділення (у разі Pentium 4) за рахунок зберігання декодованих трас інструкцій. Таким чином цей кеш виключав роботу декодера при повторному виконанні  коду, що нещодавно виконувався

Однією з ранніх публікацією про кеші трас була стаття колективу авторів ([[Eric Rotenberg]], [[Steve Bennett]] і [[Jim Smith]]), що вийшла в 1996 році під назвою ''«Trace Cache: a Low Latency Approach to High Bandwidth Instruction Fetching.»'' (Кеш трас: низколатентный підхід для забезпечення високої пропускної спроможності завантаження інструкцій).

Кеш трас зберігає декодовані інструкції або після їх декодування, або після закінчення їх виконання. Узагальнюючи, інструкції додаються в кеш трас в групах, що представляють собою або базові блоки, або динамічні траси. Динамічна траса (шлях виконання) складається тільки з інструкцій, результати яких були значимі (використовувалися згодом), і видаляє інструкції, які знаходяться в не які працюють гілках, крім того, динамічна траса може бути об'єднанням декількох базових блоків. Така особливість дозволяє пристрою підвантаження інструкцій у процесорі завантажувати відразу декілька базових блоків без необхідності піклуватися про наявність розгалужень у потоці виконання.

Лінії трас зберігаються в кеші трас за адресами, відповідним лічильника інструкцій першої машинної команди з траси, до яких доданий набір ознак передбачення розгалужень. Така адресація дозволяє зберігати різні траси виконання, що починаються з однієї адреси, але представляють різні ситуації по результату передбачення розгалужень. На стадії підвантаження інструкції (''instruction fetch'') конвеєра інструкцій для перевірки попадання в кеш трас використовується як поточний лічильник інструкцій (''program counter''), так і стан провісника розгалужень. Якщо попадання сталося, лінія траси безпосередньо подається на конвеєр без необхідності опитувати звичайний кеш (L2) або основне ОЗП. Кеш трас подає машинні команди на вхід конвеєра, поки не скінчиться лінія траси, або поки не станеться помилка передбачення в конвеєрі. У разі промаху кеш трас починає будувати таку лінію траси, завантажуючи машинний код з кешу або з пам'яті.

Схожі кеші трас використовувалися в Pentium 4 для зберігання декодованих мікрооперацій і мікрокоду, що реалізує складні x86-інструкції. [https://web.archive.org/web/20080403043445/http://citeseer.ist.psu.edu/rotenberg96trace.html Smith, Rotenberg and Bennett's paper] См повний текст роботи в [[CiteSeer|Citeseer.]]

== Реалізації ==

=== Історія ===
У ранні роки мікропроцесорних технологій доступу в пам'ять був лише трохи повільніше доступу до процесорним регістрів. Але з 1980х розрив у продуктивності між процесорами і пам'яттю став наростати. Мікропроцесори удосконалювалися швидше, ніж пам'ять, особливо в плані частоти функціонування, таким чином, пам'ять ставала вузьким місцем при досягненні повної продуктивності від системи. Хоча було технічно можливим мати основну пам'ять настільки ж швидко, як і процесор, був обраний більш економічний шлях: використовувати надмірну кількість низькошвидкісний пам'яті, але ввести в систему невелику, але швидку кеш-пам'ять, для пом'якшення розриву в продуктивності. В результаті отримали на порядок великі обсяги пам'яті, приблизно за ту ж ціну і з невеликими втратами загальної продуктивності.

Читання даних з кешу для сучасних процесорів зазвичай займає більш одного такту. Час виконання програм є чутливим до затримок читання з кешу даних першого рівня. Багато зусиль розробників, а також потужності і площі кристала при створенні процесора відводиться для прискорення роботи кешів.

Найпростішим кешем є віртуально індексований кеш прямого відображення. Віртуальний адресу підраховується за допомогою суматора, відповідна частина адреси виділяється і використовується для індексування SRAM, який поверне завантажуються дані. Дані можуть бути вирівняні по байтовим кордонів байтовому сдвигателе і потім передані наступної операції. При такому читанні не потрібна якась перевірка тегів, фактично немає навіть необхідності зчитувати тег. На більш пізніх стадіях конвейєра, перед закінченням виконання інструкції читання потрібно читання тегу і його порівняння з віртуальним адресою, щоб упевнитися, що сталося попадання в кеш. Якщо ж був промах, потрібно читання з пам'яті або більш повільного кешу з подальшим оновленням розглянутого кешу і перезапуском конвеєра.

Асоціативний кеш більш складний, тому що певний варіант тегу потрібно вважати для визначення, яку частину кешу вибрати. Кеш N-way set-associative першого рівня зазвичай зчитує одночасно всі N можливих тегів і N даних паралельно, потім проводить порівняння тегів з адресою і вибір даних, асоційованих з збіглася тегом. Кеш 2-го рівня в цілях економії енерговиділення іноді виконують спочатку читання тегів, і тільки потім читання одного елемента даних SRAM-даних.
[[Файл:Cache,associative-read.svg|thumb|Шлях читання для 2-way associative cache]]
Діаграма справа повинна показати, як відбувається використання різних частин адреси. Біт 31 адреси є найбільш значущим бітом (старшим), біт 0 — найменш значущим бітом (молодшим). На діаграмі показані дві SRAM, індексація і мультиплексування для 4 КБ, 2-way set-associative, віртуально індексованого і віртуально тегированного кешу з 64байтними блоками, 32бітною шириною читання і 32битным віртуальним адресою.

Оскільки кеш має розмір 4 КБ і лінії розміром 64 байта, у ньому зберігається 64 лінії, і ми можемо вважати за два рази з тегу SRAM, який містить 32 стовпця, кожен з яких містить кілька 21-бітних тегів. Хоча може бути використана будь-яка функція віртуальної адресації бітів 31 6, щоб індексувати тег і дані SRAM, найпростіше скористатися молодшими розрядами. Так само, тому що обсяг кешу складає 4 кБ, кеш має чотирибайтний шлях для читання і читання проводиться за двома шляхами для кожного доступу, дані SRAM складають 512 рядів шириною 8 байтів.

Більш сучасний кеш, можливо, був би 16-кілобайтним, чотирьохшляховим, набір-асоціативним, віртуально індексовані, віртуально влучаємим і фізично відмічаємим (тегом), з 32-бітовими рядками, 32-бітної шириною шини читання і 36-бітним фізичним адресуванням. Рекурентне співвідношення шляху читання для такого кешу виглядає дуже схоже з розглянутими вище. Замість тегів читаються ''віртуальні потрапляння'' ({{lang-en|vhits}}), і знову проводиться відповідність підмножини віртуального адресою. Пізніше, в конвеєрі, віртуальна адреса переводиться у фізичну адресу TLB, і проводиться читання фізичного тегу (тільки одне, так як віртуальне потрапляння поставляє шлях для читання кешу). В кінці фізична адреса порівнюється з фізичним тегом, щоб визначити, чи відбулося попадання.

Деякі процесори [[SPARC]] мали прискорені на кілька затримок затвора ({{lang-en|gate delay}}) L1 кеш за рахунок використання SRAM-декодерів замість суматора віртуальних адрес. Детальніше див. {{iw|Sum_addressed_decoder|Sum addressed decoder.|en|Sum_addressed_decoder}}

=== В X86 ===
[[Файл:Socket_3_at_SIS496_based_MB.JPG|thumb|Чотири мікросхеми кеш другого рівня на материнській платі для процесорів сімейства i486. Розташовуються в буквальному сенсі між ЦП і ОЗП.

]]
Коли [[x86]] мікропроцесори досягли частот у 20 і більше мегагерц (починаючи з[[ Intel 80386]]), для збільшення продуктивності в них було додано невелику кількість швидкої кеш-пам'яті. Це було необхідно через те, що використовується як системна ОПЕРАТИВНОЇ пам'яті [[DRAM]] мала значні затримки (до 120 нс), і вимагала такти для оновлення. Кеш був побудований на базі дорожчий, але значно більш швидкої [[SRAM]], яка в ті часи мала затримки близько 10 нс. Ранні кеші були зовнішніми по відношенню до процесора і часто розташовувалися на материнській платі як 8 або 9 мікросхем в корпусах [[DIP]], розташовані в сокети для можливості збільшення або зменшення розміру кешу. Деякі версії процесора I386 підтримували від 16 до 64 КБ зовнішнього кешу.

З виходом процесора [[Intel 80486]] 8 КБ кешу було інтегровано безпосередньо на кристал мікропроцесора. Цей кеш був названий L1 (першого рівня, {{lang-en|level 1}}), щоб відрізняти його від більш повільного кешу на материнській платі, названого L2 (другого рівня, {{lang-en|level 2}}). Останні були значно більше, аж до 256 КБ.

В подальшому випадки відділення кешу проводилися, виходячи лише з міркувань маркетингової політики, наприклад, у мікропроцесорі [[Celeron]], побудованому на ядрі [[Pentium II]].

У мікропроцесорі [[Pentium]] використовується роздільний кеш команд і даних. Буфер трансляції адрес (TLB) перетворює адреса в ОЗП відповідний адресу в кеші. Кеш даних Pentium використовує метод зворотного запису ({{lang-en|write-back}}), який дозволяє модифікувати дані в кеші без додаткового звернення до оперативної пам'яті (дані записуються в ОЗП тільки при видаленні з кешу) і протокол MESI (''Modified, Exclusive, Shared, Invalid''), який забезпечує когерентність даних в кешах процесорів і в ОЗП при роботі в мультипроцесорної системи.

Кожен з окремих кешів, даних і команд мікропроцесора [[Pentium MMX]] має обсягом 16 кБ і містить два порти, по одному для кожного виконавчого конвеєра. Кеш даних має буфер трансляції адрес (TLB).

Наступний варіант реалізації кешів у x86 з'явився в [[Pentium Pro]], в якому кеш другого рівня (об'єднаний для даних і команд, розміром 8 кБ) розміщений в одному корпусі з процесором і кешем першого рівня, розміром 8 кБ, роздільним для даних і команд, і підняв його частоту до частоти ядра. Пізніше кеш другого рівня став розміщуватися на тому ж кристалі, що і процесор. [[Подвійна незалежна шина]] (TLB){{lang-en|DIB}}), нова архітектура кеш-пам'яті, використовує різні шини для підключення процесорного ядра з основною оперативною пам'яттю. Кеш першого рівня двухпортовий, неблокуючий, підтримує одну операцію завантаження і одну операцію запису за такт. Працює на тактовій частоті процесора. За такт передається 64 біта.

У мікропроцесорі [[Pentium II]] кеш першого рівня збільшено — 16 кбайт для даних і 16 кбайт для команд. Для кешу другого рівня використовується BSRAM, розташована на одній з процесором платі у картриджі S. E. C. для установки в [[Slot 1]].

З зростанням популярності багатоядерних процесорів на кристал стали додавати кеш третього рівня, названі L3. Цей рівень кешу може бути загальним для декількох ядер і реалізовувати ефективну взаємодію між ядрами. Його обсяг зазвичай більше сумарного обсягу кешу всіх підключених до нього ядер і може досягати 16 МБ.

Популярним кеш на материнській платі залишався до ери виходу Pentium MMX і вийшов з ужитку з введенням [[SDRAM]] і зростанням різниці між частотою шини процесора і частотою ядра процесора: кеш на материнській платі став лише трохи швидше основний ОЗП.

==== Приклад кешу (процесорне ядро К8) ====
Наведена схема кешів ядра мікропроцесорів AMD K8, на якій видно як спеціалізовані кеші, так і їх багаторівневість.

Ядро використовує чотири різних спеціалізованих кешу: кеш інструкцій, TLB інструкцій, TLB даних і кеш даних:
* Кеш інструкцій складається з 64-байтних блоків, які є копією основної пам'яті, і може завантажувати до 16 байтів за такт. Кожен байт у цьому кеші зберігається в 10 бітах, а не у 8, причому в додаткових бітах відзначені кордону інструкцій (т. о. кеш проводить часткове преддекодирование). Для перевірки цілісності даних використовується лише контроль парності, а не ECC, так як біт парності займає менше місця, а в разі збою пошкоджені дані можна оновити правильною версією з пам'яті.
* TLB інструкцій, що містять копії записів з таблиці сторінок. На кожен запит читання команд потрібно трансляція математичних адрес у фізичні. Записи про трансляції бувають 4 — і 8-байтними, і TLB розбитий на 2 частини, відповідно одна для 4 КБ відображень і інша для 2 і 4 МБ відображень (великі сторінки). Таке розбиття спрощує схеми повністю асоціативного пошуку в кожній з частин. ОС і додатки можуть використовувати відображення різного розміру для частин віртуального адресного простору.
* TLB даних є здвоєним, і обидва буфера містять однаковий набір записів. Їх здвоєння дозволяє виробляти кожен такт трансляцію для двох запитів до даних одночасно. Так само, як і TLB інструкцій, цей буфер розділений між записами двох видів.
* Кеш даних містить 64-байтні копії фрагментів пам'яті. Він розділений на 8 банків (банок), кожний з яких містить по 8 кілобайт даних. Кеш дозволяє проводити по два запити до 8-байтовим даними кожен такт, за умови, що запити будуть оброблені різними банками. Тегові структури в кеші продубльовані, так як кожен 64-байтний блок розподілений по всьому 8 банкам. Якщо відбувається 2 запиту в один такт, вони працюють з власною копією теговій інформації.

Також в цьому ядрі використовуються багаторівневі кеші: дворівневі TLB інструкцій і даних (на другому рівні зберігаються лише записи про 4-кб відображеня), і кеш другого рівня (L2), уніфікований для роботи як з кешами даних та інструкцій 1-го рівня, так і для різних TLB. Кеш L2 є ексклюзивним для даних L1 L1 і інструкцій, тобто кожен ваш 8-байтовий фрагмент може знаходитися або в L1 інструкцій, або в даних L1 або L2. Винятком можуть бути лише байти, складові запису PTE, які можуть перебувати одночасно в TLB і в кеші даних під час обробки віртуального відображення з боку ОС. В такому випадку ОС відповідає за своєчасний скидання TLB після оновлення записів трансляції.

=== [[DEC Alpha]] ===
У мікропроцесорі DEC Alpha 21164 (випущений в листопаді 1995 року з тактовою частотою 333 МГц) кеш першого рівня може підтримувати деяка кількість (до 21) необроблених промахів. Є шестиелементний файл адрес необроблених промахів ({{lang-en|miss address file, MAF}}), кожен елемент якого містить адресу та регістр для завантаження при промаху (якщо адреси промаху належать одним рядком кешу, то в MAF вони розглядаються як один елемент).

Крім роздільних кешу L1 зі наскрізним записом, на кристалі процесора розташовані частково-асоціативний кеш L2 зі зворотним записом і контролер кешу L3, який працює як у синхронному, так і в асинхронному режимі.

У випущеному в березні 1997 року DEC Alpha 21164PC зовнішній кеш другого рівня; обсяг кешу команд збільшено до 16 кБ.

У мікропроцесорі DEC Alpha 21264 немає кешу другого рівня (контролер якого, тим не менш, розміщується на кристалі), але кеш першого рівня збільшено до 128 кбайт (по 64 кбайт для кешу команд і кеш даних відповідно).

=== [[PA-RISC]] ===
Розробка Hewlett-Packard для наукових та інженерних обчислень PA-8000 містить буфер переупорядковування адрес ({{lang-en|ARB}}), що відслідковує всі команди завантаження/збереження, який дозволяє скоротити затримку адресування зовнішньої кеш-пам'яті даних і команд, яка в даному процесорі може мати обсяг до 4 МБ. Тим не менш, навіть ефективне управління зовнішнім кешем за допомогою високошвидкісних ліній управління і предвибірки даних і команд з основної пам'яті в кеш не скомпенсировало невисоку швидкість і високу вартість.

Усунути вказані недоліки вдалося PA-8500, в якому за рахунок техпроцесу 0,25 мкм вдалося додати на кристал 512 кБ кешу інструкцій і 1 МБ кешу даних.

=== [[PowerPC]] ===
Побудований на гарвардській архітектурі PowerPC 620 містить два вбудованих кешу, ємністю 32 кБ кожний, які мають власні блоки управління пам'яттю ({{lang-en|MMU}}) і функціонують незалежно один від одного. Команди і адреси переходів зберігається в кеші BTAC ({{lang-en|Branch Target Adress Cache}}).

Шинний інтерфейс процесора включає повну реалізацію підтримки кешу другого рівня (обсягом до 128 МБ, працює на частоті процесора удвічі/вчетверо меншою), і для управління роботою зовнішнього кешу не вимагає додаткових тактів. Реалізована комбінація наскрізний і зворотного запису, а також підтримка протоколу MESI.

=== [[MIPS]] ===
Своя специфіка у кешу L1, застосовуваного в RA-10000, — кожна команда в кеші забезпечена додатковим четырехбитным тегом, який використовується в подальшому декодуванні та класифікації команди.

== Див. також ==
* [[Кеш]]

== Посилання ==
* [http://lwn.net/Articles/252125/ Memory part 2: CPU caches] {{Webarchive|url=https://web.archive.org/web/20210127001617/http://lwn.net/Articles/252125/ |date=27 Січня 2021 }} Стаття на lwn.net (автор Ulrich Drepper) з детальним описом кешів
* [https://web.archive.org/web/20110718154522/http://www.zipcores.com/skin1/zipdocs/datasheets/cache_8way_set.pdf  8-way set-associative кэш] написаний на [[VHDL]]

{{Comp-hardware-stub}}

[[Категорія:Технології процесорів]]


text:
# Ерік Вальтер Ельст
Ерік Вальтер Ельст (англ. Eric Walter Elst; 30 листопада 1936 — 2 січня 2022) — бельгійський астроном, успішний дослідник астероїдів. Відкрив близько 3000 астероїдів (і лише 85 спільно з кимось іншим). Працював до 2001 у Королівській обсерваторії Бельгії.
Ельсту належить честь відкриття таких астероїдів, як 4486 Мітра, 8191 Мерсенн, комети-астероїда 7968 Ельст-Пісарро та понад 25 троянських астероїдів Юпітера.
На честь дослідника названо астероїд 3936 Ельст.

## Деякі відкриті астероїди
- 48909 Лораке
- 49700 Матер
- 56000 Месопотамія
- 31097 Нуччомула
- 30857 Парсек
- 10079 Меньє
- 15273 Румкорфф
- 10111 Фреснел
- 15278 Паке
- 15239 Стенхаммар
- 11314 Шарко
- 15329 Сабена
- 10303 Фрере
- 10347 Муром
- 10350 Спалланцані
- 10354 Ґійомбюде
- 10524 Маневський
- 14016 Штеллер
- 10587 Стріндберг
- 12481 Стреувелс
- 12259 Шукальський
- 15766 Страленберґ
- 10637 Гаймліг
- 10612 Уффаліз
- 19517 Робертокарлос
- 11334 Ріо-де-Жанейро
- 17427 По
- 12718 Ле Жантіль
- 10784 Ноай
- 10771 Ору-Прету
- 12774 Пфунд
- 18449 Рікваутерс
- 10820 Оффенбах
- 16498 Пассау
- 11524 Плейєль
- 19226 Пейреск
- 16479 Паульзе
- 11051 Расін
- 14479 Плеханов
- 12722 Петрарка
- 10934 Польдельво
- 17519 Пріцак
- 16494 Ока
- 11063 Пойнтінг
- 11336 Піранесі
- 12095 Пінель
- 11871 Норж
- 16450 Мессершмідт
- 11302 Рубікон
- 11309 Малус
- 13052 Лас Касас
- 11581 Філіпдеяґер
- 16908 Ґрезеленберґ
- 13011 Лойє
- 11585 Орланділассо
- 11844 Оствальд
- 11984 Мане
- 11384 Сартр
- 12275 Маркельгоффін
- 12320 Лошмідт
- 11897 Лемер
- 12760 Максвелл
- 11875 Рона
- 12491 Мушенбрук
- 11881 Мирстейшен
- 11874 Ґрінґауз
- 11958 Ґаліані
- 11964 Пригожин
- 11966 Плато
- 11926 Оріноко
- 12773 Лиман
- 11942 Ґетар
- 12567 Херревеґе
- 12258 Оскаруайльд
- 12540 Пікандер
- 12340 Сталле
- 12761 Павелс
- 12719 Пінгре
- 12280 Реймс
- 12776 Рейнольдс
- 13088 Філіппортера
- 13647 Рей
- 14872 Хоєр Ліст
- 21087 Петсімпаллас
- 21128 Чапуіс
- 20004 Одрі-Лусієнна
- 20024 Мейремартінез
- 11315 Сальпетрієр
- 16646 Спаррман
- 17543 Сосьва
- 11870 Свеї
- 10769 Мінас Жерайс
- 24709 Мітау
- 26851 Сарапул
- 27792 Фрідакало
- 27709 Оренбург
- 12492 Танаїс
- 11956 Тамаракейт
- 12295 Тассо
- 11278 Телесіо
- 13096 Тіґріс
- 13125 Тобольськ
- 11506 Тулуз-Лотрек
- 19130 Тітгат
- 8676 Люллі
- 8672 Морзе
- 8524 Раолоруффіні
- 8525 Нільсейбел
- 12381 Хугоклаус
- 10866 Перу
- 8154 Шталь
- 8353 Меграйан
- 8395 Рембаут
- 8277 Мачу-Пікчу
- 12380 Шаша
- 7755 От-Прованс
- 8039 Ґрандпризм
- 7933 Магрітт
- 7881 Шифердеккер
- 7871 Тундер
- 7661 Рейнкен
- 7934 Сінастра
- 7425 Лессінг
- 6836 Паранал
- 6143 Піфагор
- 40227 Таїті
- 3860 Пловдів
- 3912 Троя
- 3870 Мейре
- 9879 Мамонт
- 13982 Тунберг
- 12379 Тулін
- 10137 Фукідід
- 9973 Шпільман
- 9880 Стегозавр
- 9797 Раес
- 9639 Шерер
- 9329 Ніколаймедтнер
- 9376 Тьйонвіль
- 9326 Рута
- 9325 Стоунхендж
- 9334 Моеста
- 9377 Мец
- 9395 Сен Мішель
- 9394 Маноск
- 9383 Монтелімар
- 9380 Макон
- 9378 Нансі-Лотарингія
- 9452 Роджерпітерс
- 9203 Міртус
- 9313 Протей
- 9309 Платанус
- 9246 Німейєр
- 9306 Піттоспорум
- 29189 Удінськ
- 8769 Арктиктерн
- 11385 Бовуар
- 12291 Ґогноманн
- 12750 Бертоллет
- 7420 Бюффон
- 10380 Берволд
- 11896 Кемелбік
- 6977 Жокур
- 8644 Бетулапендула
- 10151 Рубенс
- 10069 Фонтенелле
- 12715 Ґодін
- 8857 Серсідіффілум
- 8856 Селаструс
- 7578 Ґеорґбом
- 14831 Ґентілеші
- 9365 Чайнізвілсон
- 11969 Гей-Люссак
- 9757 Феліксдеягер
- 13087 Шастельлюкс
- 9079 Ґеснер
- 11289 Фрескобальді
- 12747 Міхаґеферт
- 7537 Сольве
- 11914 Сінакопулос
- 10185 Ґауді
- 4635 Рембо
- 10806 Мехіко
- 10305 Ґріньяр
- 6317 Дрейфюс
- 12356 Карлшеєле

wikiname: ukwiki

title: Ерік Вальтер Ельст

in_language: uk

wikitext:
{{Науковець
| ім'я               = Ерік Вальтер Ельст
| ім'я_мовою_оригінала = Eric Walter Elst
| портрет            =
| зображення_розмір  =
| зображення_підпис  =
| дата народження    = 30.11.1936
| місце народження   = [[Морцел]], [[Бельгія]]
| дата смерті        = 2.1.2022
| місце смерті       =
| резиденція         =
| громадянство       = [[Бельгія]]
| національність     =
| галузь             = [[астрономія]]
| заклад             =
| Alma Mater         =
| відомий через      =
| звання             =
| ступінь            =
| керівник           =
| Батько             =
| Мати               =
| Дружина            =
| Діти               =
| нагороди           =
| примітки           =
| особиста_сторінка  = http://www.angelfire.com/id/ericelst/
}}
'''Ерік Вальтер Ельст''' ({{lang-en|Eric Walter Elst}}; [[30 листопада]] [[1936]] — [[2 січня]] [[2022]]) — бельгійський [[астроном]], успішний дослідник [[астероїд]]ів. Відкрив близько 3000 астероїдів (і лише 85 спільно з кимось іншим). Працював до 2001 у [[Королівська обсерваторія Бельгії|Королівській обсерваторії Бельгії]].

Ельсту належить честь відкриття таких астероїдів, як [[4486 Мітра]], [[8191 Мерсенн]], [[комета|комети]]-астероїда [[7968 Ельст-Пісарро]] та понад 25 [[Троянці (астероїди)|троянських]] астероїдів [[Юпітер (планета)|Юпітера]].

На честь дослідника названо астероїд [[3936 Ельст]].

== Деякі відкриті астероїди ==
<div class="references-small" style="-moz-column-count:3; column-count:3; -webkit-column-count:3;">
* [[48909 Лораке]]
* [[49700 Матер]]
* [[56000 Месопотамія]]
* [[31097 Нуччомула]]
* [[30857 Парсек]]
* [[10079 Меньє]]
* [[15273 Румкорфф]]
* [[10111 Фреснел]]
* [[15278 Паке]]
* [[15239 Стенхаммар]]
* [[11314 Шарко]]
* [[15329 Сабена]]
* [[10303 Фрере]]
* [[10347 Муром]]
* [[10350 Спалланцані]]
* [[10354 Ґійомбюде]]
* [[10524 Маневський]]
* [[14016 Штеллер]]
* [[10587 Стріндберг]]
* [[12481 Стреувелс]]
* [[12259 Шукальський]]
* [[15766 Страленберґ]]
* [[10637 Гаймліг]]
* [[10612 Уффаліз]]
* [[19517 Робертокарлос]]
* [[11334 Ріо-де-Жанейро]]
* [[17427 По]]
* [[12718 Ле Жантіль]]
* [[10784 Ноай]]
* [[10771 Ору-Прету]]
* [[12774 Пфунд]]
* [[18449 Рікваутерс]]
* [[10820 Оффенбах]]
* [[16498 Пассау]]
* [[11524 Плейєль]]
* [[19226 Пейреск]]
* [[16479 Паульзе]]
* [[11051 Расін]]
* [[14479 Плеханов]]
* [[12722 Петрарка]]
* [[10934 Польдельво]]
* [[17519 Пріцак]]
* [[16494 Ока]]
* [[11063 Пойнтінг]]
* [[11336 Піранесі]]
* [[12095 Пінель]]
* [[11871 Норж]]
* [[16450 Мессершмідт]]
* [[11302 Рубікон]]
* [[11309 Малус]]
* [[13052 Лас Касас]]
* [[11581 Філіпдеяґер]]
* [[16908 Ґрезеленберґ]]
* [[13011 Лойє]]
* [[11585 Орланділассо]]
* [[11844 Оствальд]]
* [[11984 Мане]]
* [[11384 Сартр]]
* [[12275 Маркельгоффін]]
* [[12320 Лошмідт]]
* [[11897 Лемер]]
* [[12760 Максвелл]]
* [[11875 Рона]]
* [[12491 Мушенбрук]]
* [[11881 Мирстейшен]]
* [[11874 Ґрінґауз]]
* [[11958 Ґаліані]]
* [[11964 Пригожин]]
* [[11966 Плато]]
* [[11926 Оріноко]]
* [[12773 Лиман]]
* [[11942 Ґетар]]
* [[12567 Херревеґе]]
* [[12258 Оскаруайльд]]
* [[12540 Пікандер]]
* [[12340 Сталле]]
* [[12761 Павелс]]
* [[12719 Пінгре]]
* [[12280 Реймс]]
* [[12776 Рейнольдс]]
* [[13088 Філіппортера]]
* [[13647 Рей]]
* [[14872 Хоєр Ліст]]
* [[21087 Петсімпаллас]]
* [[21128 Чапуіс]]
* [[20004 Одрі-Лусієнна]]
* [[20024 Мейремартінез]]
* [[11315 Сальпетрієр]]
* [[16646 Спаррман]]
* [[17543 Сосьва]]
* [[11870 Свеї]]
* [[10769 Мінас Жерайс]]
* [[24709 Мітау]]
* [[26851 Сарапул]]
* [[27792 Фрідакало]]
* [[27709 Оренбург]]
* [[12492 Танаїс]]
* [[11956 Тамаракейт]]
* [[12295 Тассо]]
* [[11278 Телесіо]]
* [[13096 Тіґріс]]
* [[13125 Тобольськ]]
* [[11506 Тулуз-Лотрек]]
* [[19130 Тітгат]]
* [[8676 Люллі]]
* [[8672 Морзе]]
* [[8524 Раолоруффіні]]
* [[8525 Нільсейбел]]
* [[12381 Хугоклаус]]
* [[10866 Перу]]
* [[8154 Шталь]]
* [[8353 Меграйан]]
* [[8395 Рембаут]]
* [[8277 Мачу-Пікчу]]
* [[12380 Шаша]]
* [[7755 От-Прованс]]
* [[8039 Ґрандпризм]]
* [[7933 Магрітт]]
* [[7881 Шифердеккер]]
* [[7871 Тундер]]
* [[7661 Рейнкен]]
* [[7934 Сінастра]]
* [[7425 Лессінг]]
* [[6836 Паранал]]
* [[6143 Піфагор]]
* [[40227 Таїті]]
* [[3860 Пловдів]]
* [[3912 Троя]]
* [[3870 Мейре]]
* [[9879 Мамонт]]
* [[13982 Тунберг]]
* [[12379 Тулін]]
* [[10137 Фукідід]]
* [[9973 Шпільман]]
* [[9880 Стегозавр]]
* [[9797 Раес]]
* [[9639 Шерер]]
* [[9329 Ніколаймедтнер]]
* [[9376 Тьйонвіль]]
* [[9326 Рута]]
* [[9325 Стоунхендж]]
* [[9334 Моеста]]
* [[9377 Мец]]
* [[9395 Сен Мішель]]
* [[9394 Маноск]]
* [[9383 Монтелімар]]
* [[9380 Макон]]
* [[9378 Нансі-Лотарингія]]
* [[9452 Роджерпітерс]]
* [[9203 Міртус]]
* [[9313 Протей]]
* [[9309 Платанус]]
* [[9246 Німейєр]]
* [[9306 Піттоспорум]]
* [[29189 Удінськ]]
* [[8769 Арктиктерн]]
* [[11385 Бовуар]]
* [[12291 Ґогноманн]]
* [[12750 Бертоллет]]
* [[7420 Бюффон]]
* [[10380 Берволд]]
* [[11896 Кемелбік]]
* [[6977 Жокур]]
* [[8644 Бетулапендула]]
* [[10151 Рубенс]]
* [[10069 Фонтенелле]]
* [[12715 Ґодін]]
* [[8857 Серсідіффілум]]
* [[8856 Селаструс]]
* [[7578 Ґеорґбом]]
* [[14831 Ґентілеші]]
* [[9365 Чайнізвілсон]]
* [[11969 Гей-Люссак]]
* [[9757 Феліксдеягер]]
* [[13087 Шастельлюкс]]
* [[9079 Ґеснер]]
* [[11289 Фрескобальді]]
* [[12747 Міхаґеферт]]
* [[7537 Сольве]]
* [[11914 Сінакопулос]]
* [[10185 Гауді|10185 Ґауді]]
* [[4635 Рембо]]
* [[10806 Мехіко]]
* [[10305 Ґріньяр]]
* [[6317 Дрейфюс]]
* [[12356 Карлшеєле]]
</div>

== Примітки ==
{{reflist}}

== Посилання ==
* [http://www.minorplanetcenter.org/iau/lists/MPDiscsNum.html Minor Planet Discoverers] {{Webarchive|url=https://www.webcitation.org/669dKVNYj?url=http://www.minorplanetcenter.net/iau/lists/MPDiscsNum.html |date=14 березня 2012 }} {{ref-en}}
* [http://www.angelfire.com/id/ericelst/ Eric's Home Page at Angelfire] {{Webarchive|url=https://web.archive.org/web/20210226070539/https://www.angelfire.com/id/ericelst/ |date=26 лютого 2021 }} {{ref-en}}
{{бібліоінформація}}
{{DEFAULTSORT:Ельст Ерік Вальтер}}
[[Категорія:Бельгійські астрономи]]
[[Категорія:Відкривачі астероїдів]]
[[Категорія:Відкривачі комет]]

title: Eric Walter Elst

Народився: 30 листопада 1936 · Морцел, Бельгія

Помер: 2 січня 2022 (85 років) · Антверпен, Фламандський регіон, Бельгія

Країна: Бельгія

Діяльність: астроном

Галузь: астрономія

Заклад: Королівська обсерваторія Бельгії

Членство: МАС