Асоціативна пам'ять ЕОМ. Віртуальна пам'ять. Архітектурні засоби підтримки віртуальної пам'яті. Стьова організація пам'яті

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

Асоціативна теорія пам'яті

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

У той самий час, з своїх принципів, кожна з теорій пам'яті по-своєму пояснює суть і закономірності цього процесу.

Однією з таких теорій є асоціативна теорія пам'яті. Вона виходить з уявлення, що асоціація – нічим іншим як зв'язок, що має місце між психічними явищами. Такі зв'язки при запам'ятовуванні встановлюються між частинами матеріалу, що запам'ятовується або відтворюється. Справа в тому, що в процесі пригадування людина завжди шукає якісь зв'язки, встановлені тим часом матеріалом, який є і тим, який необхідно відтворити.

Було виявлено деякі закономірності, на основі яких утворюються асоціації:

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

— За схожістю. Чи помічали, що, наприклад, деякі люди когось нагадують? Може, Вам траплялося, глянувши на незнайому людину, знайти в ній якийсь «типаж» або виявити, що її риси (обличчя, манера поведінки, постави тощо) Вам запам'ятаються, оскільки вона схожа на…? Наприклад, незграбний, кудлатий, з ходою, що перевалюється, - як ведмідь; маленька, непоказна, полохлива і беззахисна на вигляд – як горобець; яскравий, важливий, з розправленими плечима та повільними важливими рухами – як павич.

- За контрастом. Нам дуже легко асоціювати "біле - чорне", "добрий - злий", "товстий - худий". Їх теж виробляє наша асоціативна пам'ять і використовує закріплення образу. І тут сприймаються образи витягують з свідомості протилежні уявлення. Так, зіткнувшись із роздратованою сусідкою, Ви згадуєте, якою спокійною здається її сестра.

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

Розвиток асоціативної пам'яті, як і асоціативного мислення, дуже важливий: асоціації допомагають нам запам'ятовувати та згадувати, генерувати ідеї. Асоціативна пам'ять дозволяє запам'ятовувати не пов'язані один з одним слова та складні тексти, завдяки їй ми легше витягуємо з пам'яті потрібну інформацію і чим ширша мережа асоціативних зв'язків, тим краще вона запам'ятовується і тим легше пригадується при необхідності. Наші судження про те чи інше питання, наші погляди, уподобання, система цінностей ґрунтуються на асоціативній пам'яті. З нею також пов'язане наше мислення, сприйняття миру та прийняття рішень.

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

1. Підготуйте 2 аркуші паперу та ручку. На 1 аркуші в стовпчик по вертикалі впишіть усі натуральні числа від 1 до 100.

2. Виберіть будь-які 10-15 з них, з якими у Вас пов'язані стійкі асоціації, та випишіть їх у довільному порядку на 2 аркуші. Наприклад, 8 – сніговик, 17 – номер Вашої улюбленої маршрутки, 18 – вік повноліття у країні, де Ви живете (якщо це), тощо. Після того, як закінчите роботу, зачекайте 5-7 хвилин, візьміть 1 листок з числами та запишіть усі події, які запам'ятали, навпроти відповідного числа.

3. Наступного разу проробіть те саме з іншими, не задіяними раніше числами. Не форсуйте події, не надто підганяйте себе спочатку, постарайтеся максимально вдало підібрати таку асоціацію, яка надійно займе своє місце у списку.

4. Коли весь список чисел буде заповнено, перевірте себе, вказавши всі асоціації, пов'язані з числами від 1 до 100.

Крім того, що потренували пам'ять, Ви створили додаткові асоціації, які допоможуть за потреби запам'ятовувати коди, номери телефонів і т.д. Просто намагайтеся використовувати свої особисті асоціації, не боячись залучати образи. Наприклад, 40 можна запам'ятати, представивши 4 як квадрат, "телевізор" і 0 як вписане в нього коло, "колобок". Вийде смішна асоціація «колобок у телевізорі». Придумайте свої асоціації, прийнятні для Вас.

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

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

Бажаємо Вам успіхів у саморозвитку!

Фото: Laurelville - Camp & Retreat Center

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

Відповідно до властивості локальності більшість програм протягом деякого проміжку часу звертаються до невеликої кількості сторінок, тому активно використовується лише невелика частина таблиці сторінок.

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

Один запис таблиці в асоціативній пам'яті (один вхід) містить інформацію про одну віртуальну сторінку: її атрибути та кадр, в якому вона знаходиться. Ці поля точно відповідають полям у таблиці сторінок.

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

Розглянемо функціонування менеджера пам'яті за наявності асоціативної пам'яті.

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

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

Число вдалих пошуків номера сторінки в асоціативній пам'яті по відношенню до загального числа пошуків називається hit (збіг) ratio (пропорція, відношення). Іноді також використовується термін "відсоток попадань у кеш". Таким чином, hit ratio – частина посилань, яка може бути зроблена з використанням асоціативної пам'яті. Звернення до тих самих сторінок підвищує hit ratio. Чим більший hit ratio, тим менший середній час доступу до даних, що знаходяться в оперативній пам'яті.

Припустимо, наприклад, що визначення адреси у разі кеш-промаху через таблицю сторінок необхідно 100 не, а визначення адреси у разі кеш-попадання через асоціативну пам'ять - 20 не. З 90% hit ratio середнє визначення адреси - 0,9x20 + 0,1x100 = 28 не.

Цілком прийнятна продуктивність сучасних ОС доводить ефективність використання асоціативної пам'яті. Високе значення ймовірності знаходження даних в асоціативної пам'яті пов'язане з наявністю даних об'єктивних властивостей: просторової і тимчасової локальності.

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

Розглянута дворівнева (асоціативна пам'ять + таблиця сторінок) схема перетворення адреси є яскравим прикладом ієрархії пам'яті, що ґрунтується на використанні принципу локальності, про що йшлося у введенні до попередньої лекції.

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

Адресна пам'ять.У пам'яті з адресною організацією розміщення та пошук інформації в ЗМ засновані на використанні адреси зберігання слова (числа, команди тощо), адресою служить номер осередку ЗМ, в якому це слово розміщується.

При записі (або зчитуванні) слова в ЗМ команда, що ініціює цю операцію, повинна вказувати адресу (номер осередку), за якою проводиться запис (зчитування).

Типова структура адресної пам'яті показана на рис. 4.2, містить запам'ятовуючий масив з N n-розрядних осередків та його апаратурне обрамлення, що включає регістр адреси РГА, має k (k> log 2 N)розрядів, інформаційний регістр РДІ,блок адресної вибірки БАВ,блок підсилювачів зчитування БУС,блок розрядних підсилювачів-формувачів сигналів запису БУЗта блок управління пам'яттю БУП.

Рис.4.2.Структура адресної пам'яті.

За кодом адреси в РГА БАВформує у відповідній комірці пам'яті сигнали, що дозволяють зробити в комірці зчитування або запис слова.

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

Далі при зчитуванні БАВдешифрує адресу, посилає сигнали зчитування в задану адресою комірку ЗМ,при цьому код записаного в осередку слова зчитується підсилювачами зчитування БУСі передається в РДІ.Потім у пам'яті з руйнівним зчитуванням (при зчитуванні всі елементи, що запам'ятовують, осередки встановлюються в нульовий стан). проводиться регенерація інформації в осередку шляхом запису в неї з РгІліченого слова. Операція зчитування завершується видачею слова з РгІна вихідну інформаційну шину ШИВих.

При записі, крім виконання зазначеної вище загальної частини циклу звернення, проводиться прийом записуваного слова з вхідної інформаційної шини ШІВхв РДІ.Сам запис складається з двох операцій: очищення осередку (скидання в 0) та власне запису. Для цього БАВспочатку здійснює вибірку та очищення осередку, заданої адресою в РГА.Очищення виконується сигналами зчитування слова в комірці, але при цьому блокуються підсилювачі зчитування БУСв РгІінформація не надходить. Потім у вибрану БАВосередок записується слово з РДІ.

Блок керування БУПгенерує необхідні послідовності сигналів, що керують, ініціюють роботу окремих вузлів пам'яті. Ланцюги передачі сигналів, що управляють, показані тонкими лініями на рис. 4.2.

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

Типова структура асоціативної пам'яті представлена ​​на рис. 4.3. Запам'ятовуючий масив містить N(п + 1)-розрядних осередків. Для вказівки зайнятості осередку використовується службовий n-й розряд (0 - осередок вільний, 1 - в осередку записано слово).

По вхідній інформаційній шині ШІВху регістр асоціативної ознаки РгАПу розряди 0-і-1 надходить п-розрядний асоціативний запит, а регістр маски РГМ - код маски пошуку, причому п-й розряд РГМвстановлюється в 0. Асоціативний пошук здійснюється лише для сукупності розрядів РДАП,яким "відповідають 1 в РГМ(Незамасковані розряди РгАП).Для слів, у яких цифри у розрядах збіглися із незамаскованими розрядами РДАП,комбінаційна схема КСвстановлює 1 відповідні розряди регістра збігу РгСвта 0 в інші розряди. Таким чином, значення j-roрозряду в РгСввизначається виразом

РгСв(j) =

де РгАП[i], РГМ[i] та ЗМ - значення i-го розряду відповідно РгАП, РгМта j-й комірки ЗМ.

Комбінаційна схема формування результату асоціативного звернення ФСформує зі слова, що утворилося в РгСв,сигнали  0 ,  1 ,  2 , що відповідають випадкам відсутності слів у ЗМ,що задовольняють асоціативну ознаку, наявність одного і більш ніж одного такого слова. Для цього ФСреалізує такі булеві функції:

 0 =

 1 = РгСв

 2 =  0  1

Формування вмісту РгСвта сигналів  0 ,  1 ,  2 за вмістом РгАП, РгМі ЗМназивається операцією контролю асоціації. Ця операція є складовоюоперацій зчитування та запису, хоча вона має й самостійне значення.

При зчитуванні спочатку проводиться контроль асоціації за асоціативною ознакою РДАП.Потім при  0 = 1 зчитування скасовується через відсутність шуканої інформації, при  1 = 1 зчитується в РгІзнайдене слово, при  2 = 1 в РгІзчитується слово з комірки, що має найменший номер серед осередків, зазначених 1 в РгСв.З РгІлічене слово видається на ШИВих.

Мал. 4.3. Структура асоціативної пам'яті

При запису спочатку знаходиться вільна комірка. Для цього виконується операція контролю асоціації при РгАП= 111. ..10 та РГМ== 00... 01. При цьому вільні осередки відзначаються 1 в РгСв.Для запису вибирається вільний осередок із найменшим номером. У неї записується слово, що надійшло з ШІВхв РДІ.

Мал. 4.4. Стьова пам'ять

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

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

Стьова пам'ять,так само як і асоціативна, є безадресною. У стекової пам'яті(Рис. 4.4) осередки утворюють одномірний масив, в якому сусідні осередки пов'язані один з одним розрядними ланцюгами передачі слів. Запис нового слова проводиться у верхню комірку (комірку 0), при цьому всі раніше записані слова (включаючи слово, що знаходилося в комірці 0), зрушуються вниз, у сусідні комірки з більшими на 1 номери. Зчитування можливе тільки з верхнього (нульового) осередку пам'яті, при цьому, якщо проводиться зчитування з видаленням, всі інші слова в пам'яті зсуваються вгору, сусідні осередки з великими номерами. У пам'яті порядок зчитування слів відповідає правилу: останнім вчинив - першим обслуговується.У ряді пристроїв розглянутого типу передбачається також операція простого зчитування слова з нульової комірки (без його видалення та зсуву слова у пам'яті). Іноді стікова пам'ять забезпечується лічильником стека. СчСт,показує кількість занесених на згадку слів. Сигнал СчСт = 0 відповідає порожньому, стеку, СчСт = N - 1 – заповненому стеку.

Часто стекову пам'ять організують, використовуючи адресну пам'ять. Широке застосування стекова пам'ять знаходить під час обробки вкладених структур даних.

У наступних параграфах глави описуються різні типи ЗП з адресною організацією. Асоціативна пам'ять використовується в апаратурі динамічного розподілу ГП, а також для побудови КЕШ-пам'яті.

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

Принцип роботи АЗУ пояснює схему, представлену на рис. 3.8.Запам'ятовуючий масив, як і в адресних ЗУ, розділений на m-розрядні осередки, кількість яких n. Як правило, до складу АЗУ входять:

· Запам'ятовує масив (ЗМ);

· Регістр асоціативних ознак (РгАП);

· Регістр маски (РгМ);

· Регістр індикаторів адреси зі схемами порівняння на вході.

В АЗУ можуть бути інші елементи, наявність і функції яких визначаються способом використання АЗУ.

Мал. 3.8. Асоціативний пристрій

Вибір інформації з АЗУ відбувається в такий спосіб. У регістр асоціативних ознак пристрою управління передається зразок для пошуку - код ознаки шуканої інформації(іноді його називають компарандом). Код може мати довільну кількість розрядів – від 1 до m. Якщо код ознак використовується повністю, він без зміни надходить на схему порівняння, якщо необхідно використовувати лише частина коду, тоді непотрібні розряди маскуються з допомогою регістру маски. Перед початком пошуку інформації в АЗУ всі розряди регістру індикаторів адреси встановлюються 1 .Після цього проводиться опитування першого розряду всіх осередків запам'ятовуючого масиву, і вміст порівнюється з першим розрядом регістру асоціативних ознак. Якщо вміст першого розряду i-й осередку не збігається із вмістом першого розряду РгАП, то відповідний цій осередку розряд регістру індикаторів адреси Т iскидається у стан 0 , якщо збігається – розряд Т iзалишається 1 . Потім ця операція повторюється з другим, третім та наступними розрядами доти, доки не буде зроблено порівняння з усіма розрядами РгАП. Після порозрядного опитування та порівняння у стані 1 залишаться ті розряди регістру індикаторів адреси, які відповідають осередкам, що містять інформацію, що збігається із записаною в регістрі асоціативних ознак. Ця інформація може бути прочитана в тій послідовності, яка визначається пристроєм управління.

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

Запис нової інформаціїу ЗМ проводиться без вказівки номера комірки. Зазвичай один із розрядів кожного осередку використовується для вказівки її зайнятості, тобто. якщо комірка вільна для запису, то в цьому розряді записано 0 , а якщо зайнята, - 1 . Тоді під час запису в АЗУ нової інформації встановлюється ознака 0 у відповідному розряді регістру асоціативних ознак і визначаються всі осередки ЗМ, які вільні для запису. В одну з них пристрій керування містить нову інформацію.

Нерідко АЗУ будуються таким чином, що, крім асоціативної, допускається і пряма адресація даних, що представляє певні зручності при роботі.

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

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

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

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

Кеш-пам'ять

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

Новий видпам'яті отримав назву кеш-пам'ять(Від англ. cache– «схованка, притулок»), оскільки така пам'ять прихована, «невидима» для ЦП, який може безпосередньо звернутися до неї. У свою чергу програміст може взагалі не знати про існування кеш-пам'яті. У серійних ЕОМ кеш-пам'ять вперше було застосовано в системах моделі 85 сімейства IBMS/360. Сьогодні кеш-пам'ять є в будь-якому класі ЕОМ, причому часто має багаторівневу структуру.

Усі терміни, визначені раніше, можуть бути використані і для кеш-пам'яті, хоча слово « рядок» ( line) часто вживається замість слова « блок» ( block).

Як правило, кеш-пам'ять будується на основі надшвидкодійних та дорогих ОЗУ статичного типу, при цьому її швидкодія в 5-10 разів перевищує швидкодію ВП, а обсяг – у 500-1000 разів менше. Зауважимо, що збільшення обсягу кеш-пам'яті по відношенню до ємності ВП перешкоджає не тільки і не так висока вартість статичних ОЗУ. Річ у тім, що зі збільшенням ємності кеш-пам'яті зростає складність схем управління, що, своєю чергою, веде до падіння швидкодії. Численні дослідження показали, що зазначене співвідношення обсягів кеш-пам'яті та ВП є оптимальним і зберігатиметься у процесі розвитку ЕОМ зі збільшенням швидкодії обох видів пам'яті.

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

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

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

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

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

Стратегії розміщення

Існує такі способи розміщення даних у кеш-пам'яті:

· Прямий розподіл;

· повністю асоціативний розподіл;

· Частково (множинно) асоціативний розподіл.

Допустимо, розрядність шини адреси nтоді ємність ВП V ОП = 2 nслів. Без обмеження спільності визначимо розмір кеш-рядка в 256 слів, таким чином, вся ВП буде поділена на 2 n-8блоків. В адресі ВП старші n-8бітів визначатимуть адресу блоку, а молодший байт – адресу слова у блоці. Нехай ємність кеш-пам'яті V кешу 1024 рази менше ємності ГП, тобто. V кеш = 2 n-10слів або 2 n-18блоків (кеш-рядок).

Прямий розподіл

Якщо кожен блок основної пам'яті має тільки одне фіксоване місце, на якому він може з'явитися в кеш-пам'яті, така кеш-пам'ять називається кешем із прямим розподілом(Direct mapped cache). Це найпростіша організація кеш-пам'яті, коли для відображення адрес блоків ВП на адреси кеш-пам'яті просто використовуються молодші розряди адреси блоку. Отже, все блоки ОП, мають однакові молодші розряди у своїй адресі, потрапляють у одну кеш-рядок, тобто.

(Адреса кеш-рядка) = (Адреса блоку ВП) mod (число блоків в кеш-пам'яті)

У нашому прикладі адреса кеш-рядку cстановитимуть молодші n-18біт адреси блоку ОП (див. рис. 3.9). Перетворення адреси блоку ВП на адресу кеш-рядка здійснюється шляхом вибірки цих молодших n-18біт. За цією адресою кеш-рядки може бути поміщений будь-який із 1024 блоків ВП, що мають однакові n-18молодших біт. Між собою ці блоки відрізнятимуться старшими 10 бітами tзваними тегом. Для того, щоб визначити, який саме блок ОП зберігається в даний часу кеш-пам'яті, використовується ще одна пам'ять – так звана пам'ять тегів (тег пам'ять). Тегова пам'ять адресується послівно, причому кожне слово має розмір, що дорівнює розміру тега. Місткість пам'яті тегів - це добуток розміру тега на загальну кількість кеш-рядків, для нашого прикладу складає 10·2 n-18біт. Адресою пам'яті тегів є адреса кеш-рядка з. На відміну від пам'яті тегів, пам'ять, у якій зберігаються блоки, вміщені в кеш, називається пам'яттю даних. Пам'ять даних адресується послівно, її адреса утворюється з адреси кеш-рядка та адреси слова всередині блоку (кеш-рядка).

Мал. 3.9. Структура адреси пам'яті під час прямого розподілу

Мал. 3.10. Організація кеш-пам'яті з прямим розподілом

При доступі до A-й адресою ВП (рис. 3.10) молодші n-18біт адреси блоку (поле c), де міститься ця адреса, використовуються як адреса кеш-рядка. За адресою кеш-рядка з тегової пам'яті зчитується тег (поле t). Паралельно з цим здійснюється доступ до пам'яті даних за допомогою n-10молодших біт адреси A(поля cі w). Якщо лічені теги і старші 10 біт адреси Aзбігаються, це означає, що блок, що містить адресу A, існує в пам'яті даних, і в слові, до якого здійснюється доступ, зберігається копія A-ї адреси ВП.

Якщо тег відрізняється від старших 10 біт адреси A, то з основної пам'яті зчитується блок, що містить адресу A, а з кеш-пам'яті видаляється кеш-рядок, адреса якого визначається полем c(молодшими n-18бітами) адреси зчитуваного блоку. На місце віддаленого кеш-рядка поміщається зчитаний з ОП блок, при цьому оновлюється відповідний тег пам'яті тегів.

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

Зазвичай у пристрої, що запам'ятовують, доступ до інформації вимагає вказівки адреси комірки. Однак значно зручніше шукати інформацію не за адресою, а спираючись на якийсь характерний ознака, що міститься в самій інформації. Такий принцип лежить в основі ЗП, відомого як асоціативний пристрій (АЗУ). У літературі зустрічаються й інші назви подібного ЗП: пам'ять, адресована за змістом (content addressable memory); пам'ять, адресована за даними (data addressable memory); пам'ять із паралельним пошуком (parallel search memory); каталогова пам'ять (catalog memory); інформаційне ЗП (information storage); тегована пам'ять (tag memory).

Асоціативне ЗУ– це пристрій, здатний зберігати інформацію, порівнювати її з деяким заданим зразком та вказувати на їхню відповідність або невідповідність один одному.

На відміну від звичайної машинної пам'яті (пам'яті довільного доступу або RAM), в якій користувач задає адресу пам'яті та ОЗУ повертає слово даних, що зберігається на цій адресі, АП розроблена таким чином, щоб користувач задавав слово даних, і АП шукає його у всій пам'яті, щоб з'ясувати, чи зберігається воно десь у ньому. Якщо слово даних знайдено, АП повертає список однієї або більше адрес зберігання, де слово було знайдено (і в деяких архітектурах, також повертає саме слово даних, або інші пов'язані частини даних). Таким чином, АП – апаратна реалізація того, що в термінах програмування назвали б асоціативним масивом.

Асоціативна ознака – ознака, яким здійснюється пошук інформації.

Ознака пошуку – кодова комбінація, яка у ролі зразка для пошуку.

Асоціативна ознака може бути частиною шуканої інформації або додатково надаватись їй. У разі його прийнято називати тегом чи ярликом.

Структура асоціативного ЗУ

АЗУ включає:

• запам'ятовує масив для зберігання N m-розрядних слів, у кожному з яких кілька молодших розрядів займає службова інформація;
• регістр асоціативної ознаки, куди міститься код шуканої інформації (ознака пошуку). Розрядність регістру kзазвичай менше довжини слова т;
• схеми збігу, використовувані для паралельного порівняння кожного біта всіх слів, що зберігаються з відповідним бітом ознаки пошуку і вироблення сигналів збігу;
• регістр збігів, де кожному осередку запам'ятовуючого масиву відповідає один розряд, в який заноситься одиниця, якщо всі розряди відповідного осередку збіглися з однойменними розрядами ознаки пошуку;
• регістр маски, що дозволяє заборонити порівняння певних бітів;
• комбінаційну схему, що на підставі аналізу вмісту регістру збігів формує сигнали, що характеризують результати пошуку інформації.

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

• а0 – не знайдено;
• а1 - міститься в одному осередку;
• а2 - міститься більш ніж в одному осередку.

Формування вмісту регістру збігів і сигналів a0, a1, а2 зветься операції контролю асоціації. Вона є складовою операцій зчитування і записи, хоча може мати самостійне значення.

При зчитуванні спочатку здійснюється контроль асоціації за аргументом пошуку. Потім, при а0=1 зчитування скасовується через відсутність шуканої інформації, приa1 =1 зчитується слово, яке вказує одиниця у регістрі збігів, а при а2= 1 скидається найстарша одиниця у регістрі збігів і витягується відповідне їй слово. Повторюючи цю операцію, можна послідовно рахувати всі слова.

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

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

Спільність ідеї асоціативного пошуку інформації не виключає різноманітності архітектур АЗУ. Конкретна архітектура визначається поєднанням чотирьох факторів:

1. виду пошуку інформації;
2. техніки порівняння ознак;
3. способу зчитування інформації при множинних збігах;
4. способу запису інформації.

У кожному конкретному застосуванні АЗУ завдання пошуку інформації може формулюватися по-різному.

Види пошуку інформації:

• Простий (потрібний повний збіг всіх розрядів ознаки пошуку з однойменними розрядами слів, що зберігаються в масиві, що запам'ятовує).
• Складний:
• Пошук всіх слів, більших чи менших від заданого. Пошук слів у заданих межах.
• Пошук максимуму чи мінімуму. Багаторазова вибірка з АЗУ слова з максимальним або мінімальним значенням асоціативної ознаки (за винятком його з подальшого пошуку), по суті, є впорядкованою вибіркою інформації. Упорядковану вибірку можна забезпечити й іншим способом, якщо вести пошук слів, асоціативна ознака яких щодо ознаки опитування є найближчим більшим чи меншим значенням.

Очевидно, що реалізація складних методів пошуку пов'язана з відповідними змінами в архітектурі АЗУ, зокрема з ускладненням схеми ЗП та введенням до неї додаткової логіки.

Техніка порівняння ознак:

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

Спосіб зчитування інформації при множинних збігах:

• З ланцюгом черговості (за допомогою досить складного пристрою, де фіксуються слова, що утворюють багатозначну відповідь. Ланцюг черговості дозволяє зчитувати слова в порядку зростання номера осередку АЗУ незалежно від величини асоціативних ознак).
• Алгоритмічно (в результаті серії опитувань).

Спосіб запису інформації:

1. За адресою.
2. C сортуванням інформації на вході АЗУ за величиною асоціативної ознаки (місце розташування комірки, куди буде вміщено нове слово, залежить від співвідношення асоціативних ознак новозаписуваного слова і слів, що вже зберігаються в АЗУ).
3. За збігом ознак.
4. З ланцюгом черговості.

Через відносно високої вартостіАЗУ рідко використовують як самостійний вид пам'яті.