Принципи організації стекової та кеш-пам’яті

Збільшення ємності пам'яті МПС зумовлює зниження швидкодії операцій обміну інформацією між процесором і модулем пам'яті. Навіть за час звернення до пам'яті, що дорівнює 70 нc, неможливо отримати потрібну інформацію за один цикл шини. Це призводить до необхідності виконання тактів очікування у процесі роботи процесора для того, щоб тривалість звернення до пам'яті була узгоджена з тривалістю виконання команди у процесорі. Підвищення швидкодії обміну інформацією можливе через реалізацію додаткової пам'яті порівняно невеликої ємності, звернення до якої здійснюється на тактовій частоті процесора. Таку пам'ять називають кеш-пам'яттю, або буферною пам'яттю. Кеш-пам'ять реалізується на базі ВІС ОЗП статичного типу. Інфор­маційна ємність і принцип організації кеш-пам'яті є одними з основних чинників, що визначають продуктивність роботи МПС.

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

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

Згідно з принципом часової локальності інформацію у кеш-пам'яті краще зберігати впродовж деякого часу, а принцип просторової локальності вказує на доцільність розміщення у кеш-пам'яті вмісту кількох сусідніх комірок, тобто певного блока інформації. Лінійні ділянки програм (без переходів) здебільшого не перевищують 3 — 5 команд, тому нераціональ­но використовувати блоки інформації, ємність яких переви­щує ємність пам'яті, потрібну для зберігання 3 — 5 команд. Як правило, інформація з основної пам'яті завантажується у кеш-пам'ять блоками по 2—4 слова і зберігається там деякий час.

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

Залежно від способу відображення інформації з основної пам'яті на кеш-пам'ять розрізняють такі типи кеш-пам'яті:

•  кеш-пам'ять з прямим відображенням;

• повністю асоціативна кеш-пам'ять;

• множинна асоціативна кеш-пам'ять.

Кеш-пам'ять з прямим відображенням є найпростішим типом кеш-пам'яті (рис. 1). Кеш-пам'ять містить дві час­тини — кеш-пам'ять даних і кеш-пам'ять ознак. Припусти­мо, що ємність ОЗП МПС становить 4 Гбайт. Ця ємність розбивається на 64 ´ 1024 рівних частин по 64 Кбайт. Блок даних ємністю 4 байт пересилається з кожної із цих частин оперативної пам'яті в один 32-розрядний рядок кеш-пам'яті даних. Ємність кеш-пам'яті даних становить 64 Кбайт, тому кількість рядків дорівнює 64 Кбайт/4 байт = 16 ´ 1024. Отже, під кожну з 64 ´1024 частин ОЗП у кеш-пам'яті від­водиться один рядок: 32-розрядна адреса чотирибайтового блока в ОЗП поділяється на дві частини. Молодші 16 роз­рядів адреси А15—А0 називають індексом, старші 16 розря­дів А31—А16 — ознакою. Ознака пересилається у кеш-па­м'ять ознак, яка містить 16´1024 рядків і має загальну ємність 32 Кбайт.

Для визначення адреси одного рядка кеш-пам'яті ознак треба 14 адресних розрядів А15—А2. Для визначення адре­си одного рядка кеш-пам'яті даних також необхідно 14 адрес­них розрядів А15—А2, а для визначення одного байта у ряд­ку — 2 розряди А1, А0.

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

Рисунок 1 - Структурна схема кеш-пам'яті з прямим відображенням

 

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

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

Структурну схему повністю асоціативної кеш-пам'яті по­казано на рисунку 2.

У цій схемі усунено недолік кеш-пам'яті з прямим відобра­женням, оскільки будь-який блок ОЗП може відображатися у будь-якому рядку кеш-пам'яті. У кеш-пам'ять ознак записується 30-розрядна ознака, тобто старші 30 розрядів А31 — А2 адреси чотирибайтового блока ОЗП. У рядок кеш-пам'я­ті даних записується чотирибайтовий блок. 

Рисунок  2 - Структурна схема повністю асоціативної кеш-пам'яті

 

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

Множинна асоціативна кеш-пам'ять поєднує переваги обох попередніх типів. Рядки цієї кеш-пам'яті об'єднані в групи по 2, 4 і більше (згідно з цим розрізняють дво-, чотири-і більше входову множинну асоціативну кеш-пам'ять). Структурну схему двовходової множинної асоціативної кеш-пам'яті зображено на рисунку 3.

Кеш-пам'ять даних складається з 8´1024 груп, кожна з яких містить два рядки. Індекс, тобто 16 молодших розрядів адреси ОЗП, адресує байт у кеш-пам'яті даних (13 розрядів адресують одну з 8´1024 груп, 1 розряд — рядок у групі та 2 розряди — байт у рядку). Ознака, тобто 16 старших адрес­них розрядів, записується в рядок пам'яті ознак. Тому для блоків з одним і тим самим індексом відводиться два рядки буфера. Отже, якщо один з рядків групи зайнято деяким блоком, то наступний блок з таким самим індексом розмі­щується у вільний рядок. Всередині групи кеш-пам'ять є повністю асоціативною. Кількість порівнянь адрес ОЗП з ознаками дорівнює двом.

Зростання ємності кеш-пам'яті (тобто кількості рядків у групі) збільшує ефективність її роботи, але зростає кількість порівнянь адреси, отже, тривалість оброблення запиту комір­ки ОЗП. Ефективність роботи кеш-пам'яті характеризуєть­ся коефіцієнтом удалих звернень. Кеш-пам'ять з прямим відображенням інформаційною ємністю N´п має такий са­мий коефіцієнт вдалих звернень, що й двовходова множинна асоціативна кеш-пам'ять ємністю (N ´ п)/2.

Рисунок 3 - Структурна схема двовходової множинної асоціативної кеш-пам'яті

 

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

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

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

Рисунок 4 -  Розміщення трибайтових слів без вирівнювання по межі блока

 

Рисунок 5 - Розміщення трибайтових слів з вирівнюванням по межі чотирибайтового рядка кеш-пам'яті

 

Без вирівнювання даних досить часто трапляються невдалі звернення до кеш-пам'яті. На рисунку 5 показано запис три­байтових слів D1 — D4, вирівняних по межі чотирибайтового рядка кеш-пам'яті. Це дає змогу значно зменшити кількість невдалих звернень до кеш-пам'яті.