372

ється на основі асоціативного пошуку. Тут так само, як це було зроблено для прямого відображення, k-розрядне поле адреси блоку в основній пам'яті розбивається на дві час­тини: поле тега г та поле номера блоку s (рис. 10.12b), причому тег вказує номер секції основної пам'яті, а в полі номера блоку вказується номер блоку в секції основної пам'яті та відповідно в кеш пам'яті.

Для наведеного вище прикладу, коли кількість блоків в основній пам'яті рівна 2²⁵, а в кеш пам'яті - 2⁹, причому кількість блоків в секторі кеш пам'яті рівна 2, маємо: повна розрядність адреси п = ЗО, причому поле адреси блоків основної пам'яті займає k = 25 розрядів, поле номера тега (тобто номера секції в основній пам'яті) г .= 17 розрядів, поле номера блоку в секції (в кеш пам'яті) п = 8 розрядів, поле адреси слова в блоці m = 5 роз­рядів (рис. 10.12b).

Контролер кеш пам'яті за допомогою восьми середніх розрядів слова адреси зверта­ється до визначеного цими розрядами блоку власної пам'яті. Зрозуміло, що шуканий в такий спосіб блок завжди присутній в кеш пам'яті. Адже кеш пам'ять вміщує 512 блоків. Але вміст віднайденого блоку кеш пам'яті може бути копією не одного, а одного з декіль­кох дозволених на копіювання блоків основної пам'яті. Наприклад, до нульового блоку кеш пам'яті дозволено копіювати вміст наступних блоків основної пам'яті: 0, 64, 128, 192, 256 і т. д. Усього до кожного блоку кеш пам'яті можна скопіювати вміст одного з 2¹⁷ = 131072 блоків основної пам'яті, оскільки ємність основної пам'яті в 131072 разів переви­щує ємність кеш пам'яті. Для того, щоб визначити, чи є поточне наповнення вказаного блоку кеш пам'яті відповідним до запиту процесора, використовують вміст старших 17 бітів адреси основної пам'яті.

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

---

373

При даному способі відображення кожен рядок кеш пам'яті вміщує наступну інфор­мацію: тег, який вказує вміст блоку якої секції основної пам'яті переписано до даного блоку кеш пам'яті, розряд достовірності (valid bit V), який вказує, чи вміст даного блоку кеш пам'яті дійсно належить блоку основної пам'яті, вказаному s розрядами поля адре­си, розряд модифікації (dirty bit D), який інформує про внесення змін до вмісту блоку кеш пам'яті, а також вміст блоку основної пам'яті, вказаного s розрядами поля адреси. Коли процесору потрібний операнд із блоку з певною адресою, контролер кеш пам'яті вибирає з секторів пам'яті тегів відповідні номеру блоку в кеш пам'яті теги, та порівнює 'їх з відповідними г розрядами адреси, в яких вказано тег. При наявності в кеш пам'яті відповідного тега, та при одиничному значенні розряду достовірності, кеш пам'ять ви­дає сигнал підтвердження попадання та надає доступ до відповідного блоку.

10.2.5. Порядок заміщення блоків в кеш пам'яті з асоціативним відображенням

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

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

---

374

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

Найбільш ефективним є алгоритм заміщення LRU (Least Recently Used), який пе­редбачає заміщення блоків з найдавнішим використанням, оскільки він базується на властивості часової локальності. За цим алгоритмом заміщується вміст того блоку кеш пам'яті, до якого найдовше не було звернення. Найвідоміші два способи апаратурної реалізації цього алгоритму. У першому з них за кожним блоком кеш пам'яті закріплюють лічильник. До вмісту всіх лічильників через певні інтервали часу додається одиниця. При зверненні до блоку його лічильник встановлюється в нульовий стан. Таким чином, найбільше число буде в лічильнику того блоку, до якого найдовше не було звернень, і вміст цього блоку є першим кандидатом на заміщення. Другий спосіб реалізується за до­помогою черги, куди у порядку заповнення блоків кеш пам'яті заносяться посилання на ці блоки. При кожному зверненні до блоку посилання на нього переміщується в кінець черги. В результаті першим в черзі кожного разу опиняється посилання на блок, до якого найдовше не було звернень. Вміст саме цього блоку перш за все і заміщується.

Інший можливий алгоритм заміщення - алгоритм, що працює за принципом "пер­ший увійшов, перший вийшов" (FIFO - First In First Out). Тут заміщується вміст блоку, що найдовше знаходився в кеш пам'яті. Алгоритм легко реалізується за допомогою роз­глянутої раніше черги, з тією лише різницею, що після звернення до блоку положення відповідного посилання в черзі не змінюється.

Ще один алгоритм - заміна вмісту блоку, що найменше використовувався (LFU - Le­ast Frequently Used). Заміщується вміст того блоку в кеш пам'яті, до якого було менше всього звернень. Принцип можна реалізувати, пов'язавши кожен блок з лічильником звернень, до вмісту якого після кожного звернення додавати одиницю. Головним пре­тендентом на заміщення є вміст блоку, лічильник якого містить найменше число.

Простий алгоритм заміщення - довільний вибір блоку для заміни його вмісту. Блок, вміст якого замінюється, вибирається випадковим чином. Це може бути реалізовано, наприклад, за допомогою лічильника, вміст якого збільшується на одиницю з кожним тактовим імпульсом, незалежно від того, що мало місце - попадання чи промах. Значен­ня в лічильнику визначає блок, вміст якого буде замінено в повністю асоціативній кеш пам'яті, або воно визначає блок в межах сектора, вміст якого буде замінено в частково-асоціативній кеш пам'яті. Даний алгоритм використовується вкрай рідко.

Частіше попереднього використовують алгоритм випадкового заміщення вмісту блоків кеш пам'яті за значенням лічильника випадкових чисел, оскільки за ефективніс­тю він є близьким до алгоритму LRU та простішим за нього в реалізації.

---

70.2.6. Підвищення ефективності кеш пам'яті

Характеристики, які використовують при оцінці ефективності ієрархічної організа­ції пам'яті, підходять і для оцінки ефективності кеш пам'яті. До цих характеристик на­лежать наступні:

• коефіцієнт попадань - відношення числа попадань до загального числа звернень процесора до основної пам'яті, де під попаданням розуміється виявлення в кеш пам'яті потрібної інформації, при зверненні до основної пам'яті;

• коефіцієнт промахів - відношення числа промахів до загального числа звернень процесора до основної пам'яті, де під промахом розуміється відсутність в кеш пам'яті

---

375

потрібної інформації, при зверненні до основної пам'яті. Якщо позначити коефіцієнт попадань через k_h, а коефіцієнт промахів через k_m, то залежність між ними можна ви­разити наступною формулою: k_m= 1 - k_h;

• час звернення при попаданні - час, необхідний для пошуку потрібної інформації в кеш пам'яті (включаючи з'ясування, чи є звернення попаданням), плюс час на фактич­не зчитування даних;

• втрати на промах - час, потрібний для заміни блоку в кеш пам'яті на блок з по­трібними даними, розташований в основній пам'яті;

■ середній час доступу до основної пам'яті, який визначається з виразу:
t_av = t_h + k_mt_p, де t_h- час звернення при попаданні, t_p- втрати на промах.

Таким чином, чим менше промахів, тим вища ефективність використання кеш пам'яті. Розглянемо типи промахів до кеш пам'яті та підходи до зменшення їх кількості й пов'язаних з ними втрат. Існує три типи промахів: обов'язкові, ємнісні та конфліктні. Обов'язкові промахи - це промахи, які виникають при початковому зверненні до основної пам'яті. Зрозуміло, що перший доступ до кеш пам'яті обов'язково буде прома­хом. Для зменшення кількості цього типу промахів потрібно збільшувати розмір блоків в кеш пам'яті.

Ємнісні промахи пов'язані з обмеженим розміром кеш пам'яті. Для зменшення кіль­кості цього типу промахів потрібно збільшувати розмір кеш пам'яті.

Конфліктні промахи пов'язані з ефективністю алгоритму заміщення блоків в кеш пам'яті. Для зменшення кількості цього типу промахів потрібно збільшувати асоціатив­ність кеш пам'яті, аж до використання для її реалізації повністю асоціативної пам'яті.

На рис. 10.14 наведено залежність величини коефіцієнта промахів від ємності кеш пам'яті та від кількості блоків в одному секторі кеш пам'яті з використанням частково-асоціативного відображення при виконанні набору тестових програм SPEC 92.

Таким чином, збільшення розміру блоку кеш пам'яті понижує кількість обов'язко­вих промахів, але збільшує втрати на промах, через зростання часу пересилання блоку інформації. Крім того, якщо ємність кеш пам'яті невелика, то збільшення розміру блоку збільшує кількість конфліктних промахів через зменшення кількості блоків та секторів.

---

Смотрите также файлы

• Екологія посібник.doc

• LR3_[5405].doc

• Питання до модуля 1 з АК.doc

• Питання до 1 модуля з КЕ.doc

• ДБН В.3.2-2-2009_Жил_здания_реконст_кап_ремонт.doc