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

1. Принципи організації кеш-пам'яті

Збільшення ємності пам'яті МПС зумовлює зниження швидкодії операцій обміну інформацією між процесором і модулем пам'яті. Навіть за час звернення до пам'яті, що дорівнює 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, вирівняних по межі чотирибайтового рядка кеш-пам'яті. Це дає змогу значно зменшити кількість невдалих звернень до кеш-пам'яті.

2. Принципи організації стекової пам'яті

Стековою пам'яттю, або стеком, називають пам'ять, в якій реалізовано принцип: останній увійшов — перший вийшов {LIFO — Last Input First Output), тобто дані, записані останніми, зчитуються першими. У МПС стекова пам'ять вико­ристовується для викликів підпрограм, в тому числі і вкладе­них, та оброблення переривань.

За способом реалізації розрізняють апаратний і апаратно-програмний стеки.

Апаратний стек — сукупність регістрів, зв'язок між якими організовано так, що під час записування і зчитування даних вміст стеку автоматично зсувається. Принцип роботи апаратного 8-рівневого стеку наведено на рисунку 6.

Під час записування слова 1 у стек воно розміщується у першій вільній комірці пам'яті (у першому регістрі) — вершині стеку. Наступне слово зсуває попереднє на одну комірку вгору, займає його місце і т. д. Запис слова 9 при­зводить до переповнення стеку і втрати слова 1. Зчитуван­ня слів зі стеку здійснюється у зворотному порядку, тобто спочатку зчитується слово 9, що записано останнім. Зчиту­вання відбувається у зворотному порядку, наприклад, зчитування слова 6 неможливе, доки не будуть зчитані слова 7, 8,9.

 

Рисунок 6 - Принцип роботи апаратного стеку

 

Рисунок 7 - Принцип роботи апаратно-програмного стеку

 

Інформаційна ємність апаратного стеку визначається як N´ п, де кількість n-розрядних слів  дорівнює кількості регістрів, яка може бути кілька десятків. Апаратні стеки, що застосовуються у РIС- процесорах, мають 2, 8 або 16 регістрів (N = 2,8,16), в яких розміщуються 12-, 14-, 16-розрядні сло­ва (п = 12,14,16). Основною перевагою апаратного стеку є висока швидкодія, а недоліком — обмежена інформаційна ємність.

Апаратно-програмний стек реалізується через вико­ристання частини ОЗП статичного типу та спеціального ре­гістра SP (Stack Pointer — покажчик стеку), який містить адресу останньої зайнятої комірки стеку. Принцип роботи апаратно-програмного стеку для МП мікропроцесорів 80 ´ 86 показано на рисунку 7. В апаратно-програмному стеку під час запису і зчитування фізичного зсуву даних не відбуваєть­ся. Зсув даних буває після зміни значення регістра SP. На початку програми в регістр SP заносять адресу вершини стеку. Після кожної операції запису (зчитування) вміст регістра SP змінюється. Для МП 80 ´ 86 одночасно можна записувати у стек або зчиту­вати з нього двобайтові сло­ва, тому значення регістра SP змінюється на два.

 

Рисунок 8 - Робота стеку під час виклику підпрограм

 

Під час запису в стек зна­чення регістра SP зменшу­ється на два (стек «зростає» в область малих адрес), а під час зчитування зі стеку — збільшується на два. Отже, по­кажчик стеку SP завжди містить адресу комірки, до якої відбулося останнє звернення. У деяких командах, наприклад, у командах викликів підпрограм CALL, переривань ІNT, по­вернень з підпрограм RET, звернення до стеку здійснюється автоматично. Під час виклику підпрограми (рис. 8) у стеку запам'ятовується адреса команди, наступної після виклику команди ADD, тобто вміст програмного лічильника PC запа­м'ятовується у верхній незайнятій комірці стеку, а покажчик стеку зменшується на два.

Після повернення з підпрограми за командою RET вміст верхньої комірки стеку перезаписується у програмний лічиль­ник PC, покажчик стеку SP збільшується на два. Після цьо­го починає виконуватися команда ADD. Крім команд CALL, INT і RET, для роботи зі стеком використовуються також команди PUSH і POP, призначені для тимчасового запам'я­товування у стек умісту регістрів і відновлення, тобто пере­силання інформації зі стеку в регістри. У МП Intel, починаючи з МП i286, існують команди PUSHA і РОРА (PUSH All і POP All), призначені для тимчасового запам'ятовування у стеку і відновлення вмісту всіх регістрів МП. До апаратно-програмного стеку можна звернутися також як до ОЗП з довільною вибіркою. У МП i80´86 для цього використову­ють непряму адресацію за допомогою регістра ВР. Тому в стек можна записати значення параметрів підпрограм перед їх безпосереднім викликом.

Використання стекової пам'яті дає змогу підвищити швид­кодію МПС, зменшуючи тривалість однієї з найповільніших операцій — звернення до зовнішньої пам'яті.