ДонНТУ   Портал магістрів

Лебединський Олександр Олександрович

Факультет комп'ютерних наук та технологій

Кафедра комп'ютерної інженерії

Спеціальність Сиcтемне програмування

Дослідження кешування в мікропроцесорних системах

Науковий керівник: к.т.н., доц. Самощенко Олександр Вікторович

Резюме Біографія Реферат

Реферат за темою випускної роботи

Зміст

• Вступ
• 1. Структурa кешування в мікропроцесорній системі
• 2. Структура навчально-налагоджувального стенда EV8031/AVR
• 3. Моделювання роботы кеш-пам`яті за допомогою стенду EV8031/AVR
• Висновки
• Список джерел

Вступ

У сучасних комп'ютерних системах операція кешування використовується скрізь. Ідеї кешування виникли досить давно і розвиваються до цих пір. Кешування застосовується ЦПУ, жорсткими дисками, браузерами, веб-серверами, службами DNS і WINS.

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

Кеш-пам'ять може мати кілька рівнів, має різну структуру та алгоритми роботи.

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

1. Структурa кешування в міркопроцессорній системі

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

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

Вперше слово "кеш" в комп'ютерному контексті було використано в 1967 році під час підготовки статті для публікації в журналі “IBM Systems Journal”. Стаття стосувалася вдосконалення пам'яті в такій, що розробляється, моделі 85 з серії IBM System/360. Редактор журналу Лайл Джонсон попросив придумати більш описовий термін, ніж “високошвидкісний буфер”, але через відсутність ідей сам запропонував слово “кеш”.

Кеш-пам'ять є одним їх верхніх рівнів ієрархії пам'яті, між регістрами загального призначення і оперативним запам'ятовуючим пристроєм. Швидкість роботи кеш-пам'яті порівнянна зі швидкістю роботи мікропроцесора. Ієрархія пам'яті з двома рівнями кеш-пам'яті представлена на рис.1 [1].

Ідея використання швидкої буферної пам'яті між мікропроцесором і основною пам'яттю з'явилася давно і в IBM System/360 вона була використана вже не вперше. У радянських ЕОМ функцію кешу виконувала пам'ять на надшвидких регістрах, які так само розміщувалися між основною пам'яттю і процесором прикладом є машини БЕСМ [2]. Кеш використовує невелику, дуже швидку пам'ять (зазвичай типу SRAM).

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

Успіх чи невдача операції звернення до кеш пам'яті називається кеш-попаданням (hit ratio) або кеш-промахом (miss ratio) [3]. Ці операції прямо залежать від того які саме слова знаходяться в кеш-пам'яті. Відомим фактом є те, що програми не звертаються до пам'яті довільно. Найчастіше після деякої адреси А і з дуже високою ймовірністю можна припустити що наступною буде якась адреса в районі адреси А. Переважна більшість команд які використовуються у звичайній програмі викликаються з послідовної області пам'яті. Так само відомо, що велика частина часу роботи програм займають виконання однотипних наборів команд, які виконуються в циклі [7].

Основу всіх систем кеш-пам'яті становить принцип локальності. Це коли при послідовному зверненні до пам'яті протягом певного часу використовується тільки її частину. Ідея полягає в тому що при зверненні до будь-якого слова воно разом з сусідніми переноситься в кеш-пам'ять, що дозволить швидко до них звернутися при наступному запиті [1].

В даний час використовується багаторівнева структура кеш-пам'яті. Як правило, використовується три рівні кеш-пам'яті (L1, L2, L3), при чому кеш-пам'ять третього рівня в масових процесорах почала використовуватися недавно. Кеш-пам'ять першого рівня (L1) розташовується прямо на кристалі процесора і має обсяг від 16 до 64 Кбайт, але при цьому є найшвидшою. Кеш-пам'ять другого рівня (L2) розташовується в одному корпусі з мікропроцесором і має обсяг від 512 Кбайт до 1Мбайт, але при цьому вона в два три рази повільніше її. Кеш-пам'ять третього рівня (L3) знаходиться дальше за всього від процесора і має обсяг кілька мегабайт і так само є самою повільною кеш-пам'яті. Кеш-пам'ять третього рівня є загальною для ядер мікропроцесора. Але все ж його швидкість, набагато вище швидкості системної пам'яті [5],[1]. Прикладом трирівневої кеш-пам'яті можна навести структуру пам'яті в AMD K10 [4] рис. 4.

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

Ще кеш-пам'ять може бути об'єднаною (unified cache) або розділеною (split cache). В об'єднаній зберігаються як команди так і інструкції. (U-cache). У розділеної кеш-пам'яті існує кеш команд (I-cache) і кеш даних (D-cache). Це дозволяє проводити паралельну обробку даних і команд. У більшості процесорів розділеної буває лише кеш-пам'ять першого рівня. А кеш пам'ять другого і третього рівня є уніфікованими. Іноді кеш-пам'ять третього рівня називають T-cache (ternary - третьорядна). Структура розташування кеш-пам'яті різних рівнів рис. 5.

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

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

Основна пам'яті і кеш-пам'ять діляться на блоки фіксованого розміру з урахуванням принципу локальності [1]. Блоки всередині кеш-пам'яті зазвичай називають рядками кеша. Рядок кеш-пам'яті складається з декількох байтів. Рядки нумеруються починаючи з нуля. Наприклад якщо рядок кеш пам'яті 4 байта то - нульова рядок це байти з нульового по третій, другий рядок з четвертого по сьомий і так далі. В будь-який момент часу в кеш-пам'яті знаходиться кілька рядків.[5]

2. Структура навчально-налагоджувального стенда EV8031/AVR

Навчально-налагоджувальний стенд EV8031/AVR призначений для роботи з мікроконтролерами AT89C51, AT89C52, AT90S8515 (ATmega8515) (корпус DIP-40). Структурна схема стенда наведена на рис 1. Стенд оснащений ОЗУ ємністю 32 Кб, з яких 16 Кб пам'ять даних і 16 Кб пам'яті команд. Стенд має послідовний порт (RS-232), інтерфейс RS-485, матричну клавіатуру 3 * 4, дискретні кнопки (лінії INT0, INT1). Через I2C можна отримати доступ до таймеру реального часу (DS1307), інтегрального цифрового датчика температури (DS1621) і EEPROM (AT24C02). Також можлива статична чотирирозрядна індикація. До стенду може бути підключений рідкокристалічний індикатор 4 * 10 (BC1004A) [8].

Є можливість підключення до стенду плат розширень EV8031/АN або EV8031/АU. Дані плати розширення дозволяють вимірювати аналогові й частотні сигнали, регулювати роботу вентилятора і вимірювати температуру. На платах розширення знаходиться восьмирозрядний цифро-аналоговий перетворювач (AD7801), динамічний і знакосінтезірующіе індикатори, генератор з фіксованою і змінною частотою, динамік, N-кодер, датчик Холла (SS4433), датчик температури (ТMP03), інтегральний аналого-цифровий перетворювач (AD7813)[9] .

Після перепрошивки мікросхеми ALTERA з'являється можливість активації плати розширення EV8031/RF, яка дозволяє працювати з модулями GSM SIM300 або SIM900 (утримувач SIM карти, аудіо-роз'єм Jack-3.5 мм), інфрачервоним прийомо-передавачем (ТFDU4100), протоколом однопроводной зв'язку (роз'єм 1 -Wire (DS9094), ідентифікатор (DS1990A)). Також на платі розширення присутні GPS модуль SSF-1919P, гібридний модуль на 433МГц частотної модуляції (передавач RTFQ1, приймач RRFQ1).[9]

3. Моделювання роботи кеш-пам'яті за допомогою стенда EV8031/AVR

Виконано моделювання роботи кеш-пам'яті прямого відображення (одноканальної кеш-пам'яті). Область пам'яті, яка кешується, розбивається на блоки, розмір яких дорівнює обсягу кеш-пам'яті. Адреса рядка кеш-пам'яті, на яку відображається блок з основної пам'яті, однозначно визначається виразом: i = j mod m, де m - загальне число рядків в кеш-пам'яті.

Кеш-пам'ять прямого відображення - простий тип кеш-пам'яті, ефективно використовується в кеш-команд (I-cache).

Достоїнствами кеш-пам'яті прямого відображення є:

• Висока швидкість визначення факту попадання / промах,
• Простота пошуку рядка-кандидата на видалення, тому що присутня жорстка прив'язка до адрес.

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

У моделі реалізована пам'ять розміром 16 байт і кеш-пам'ять розміром рядка 1 байт з чотирма рядками. Таким чином, нульовий рядку кеш-пам'яті можуть відповідати байти пам'яті з номерами 0,4,8,12; першому рядку з номерами 1,5,9,13 і т.д. При цьому в кеш-пам'яті крім даних зберігається тег, який вказує на комірку пам'яті, зіставлення в поточний момент активної рядку кеш-пам'яті. Структура кеш-пам'яті прямого відображення [1], [5] показана на рис 7.

Запис рядка в кеш-пам'ять супроводжується записом в пам'ять тегів номера відповідної сторінки основної пам'яті.

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

У моделі реалізований режим зворотного запису в кеш-пам'ять (WB - Write Back). Для вказівки на факт зміни рядки без її копіювання в основну пам'ять використовується ознака модифікації M (Modified). Рядок з ознакою M не відповідає вмісту зіставленої осередки основної пам'яті. Ознака скидається в нуль при первісної завантаженні рядка в кеш-пам'ять і встановлюється в одиницю при запису оновленого рядка. Таким чином, для забезпечення когерентності даних перезаписувати в основну пам'ять необхідно тільки рядки з одиничним значенням ознак модифікації. Режим зворотного запису раціональний, але допускає тимчасове відмінність даних кеша і основної пам'яті.

При читанні з пам'яті в кеш рядок позначається ознакою S (Shared), що вказує на повну відповідність вмісту пам'яті. Рядки кеш-пам'яті, які не містять достовірну інформацію, позначаються ознакою I (Invalid), а звернення до такої рядку призводить до кеш-промаху.

Для вказівки кожної ознаки відводиться по одному біту, тегу - 3 біта. Структура одного рядка кеш-пам'яті представлена на рис. 8.

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

Модель дозволяє оцінити ефективність роботи кеш-пам'яті прямого відображення зі зворотним записом, для чого розраховується коефіцієнт кеш-влучень. В якості вихідних показників приймається кількість кеш-влучень і загальна кількість звернень до слова в пам'яті. Наприклад, до слова з адресою А було 15 звернень, з них 10 раз мав факт кеш-влучень. Таким чином, коефіцієнт дорівнюватиме 10/15 = 0,66, що вказує на 66% випадків кеш-влучень.

Як наслідок, можна розрахувати показник усередненого часу доступу до даних:

Припустимо, що час спрацювання кеш-пам'яті 2 мкс, а час звернення до основної пам'яті 200мкс, при цьому коефіцієнт кеш-промахів дорівнює 3%. Отже, середній час доступу до даних буде дорівнювати 2 + 200 * 0,03 = 8 мкс.

Висновки

У мікропроцесорних системах кеш-пам'ять використовується з комп'ютерних мірками дуже давно. Початок її використання було пов'язано з низькою швидкодією основної пам'яті. І основні ідеї її функціонування не змінилися дотепер. Сучасна кеш-пам'ять може працювати з швидкодією порівнянним з процесорним (L1).

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

Магістерська робота присвячена актуальній науковій задачі дослідити роботу кеш-пам'яті. І розробити модель кеш-контролера за допомогою стенду EV 8031

1. Модель кеш-пам'яті,що реалізована на стенді, дозволяє детально вивчити режим роботи зі зворотним записом, а також переконатися в достоїнствах і недоліках кеш-пам'яті прямого відображення.
2. На підставі аналізу літературних джерел виділено основні алгоритми кеш-пам'яті.

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

Список джерел

1. Таненбаум Э. Архитектура компьютера / Таненбаум. Э. – Питер, 2010. – 5е издание. – 844с.
2. Королев Л.Н. Архитектура ЭВМ БЭСМ-6 [Электронный ресурс]. – Режим доступа: http://www.parallel.ru/history/besm6.html
3. Касперский К. Кэш-память, как она есть [Электронный ресурс]. – Режим доступа: http://www.insidepro.com/kk/008/008r.shtml
4. Пахомов С. Долгожданные процессоры с микроархитектурой AMD K10/ Пахомов. С. – КомпьютерПресс 10'2007
5. Гук М.Ю. Апаратные средства IBM PC. Энциклопедия / Гук М.Ю. – Питер 2006. – 1072 с.
6. Anand Lal Shimpi The Cache Debate, LGA-1156 and the 32nm Future [Электронный ресурс]. – Режим доступа: http://www.anandtech.com/show/2671
7. Жмакин А.П. Архитектура ЭВМ / Жмакин. А. П. - СПб. – 2006 – С. 259
8. Учебно-отладочный стенд EV8031/AVR / Техническое описание. Инструкция по эксплуатации.
9. Учебный-отладочный стенд "EV8031/AVR"[Электронный ресурс]. – Режим доступа: http://opensys.com.ua/Stend/Ev8031