4.3. Кеш пам’ять

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

Розумним компромісом для побудови економічних і продуктивних систем з'явився ієрархічний спосіб побудови оперативної пам'яті, прийшов в архітектуру PC з появою процесора 386, у якого тактова частота вже значно відривалася від можливостей мікросхеми DRAM того часу. Ідея цього способу полягає в поєднанні основної пам'яті великого обсягу на DRAM з відносно невеликою кеш-пам'яттю на швидкодіючих мікросхемах SRAM. Ідея, звичайно, далеко не нова – надоперативна пам'ять застосовувалася давно, ще у «великих» комп’ютерах.

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

Зазвичай кешується тільки основна динамічна пам'ять системної плати (пам'ять, встановлена на адаптерах, не кешується), і з цієї пам'яті кешується тільки частина (поширені версії чипсетів для Pentium часто дозволяють кешувати тільки перші 64 Мбайт ОЗУ).

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

У сучасних комп'ютерах кеш зазвичай будується за дворівневою схемою. Первинний кеш (L1Cache) вбудований в усі процесори класу 486 і старше, він є й у деяких моделях 386. Обсяг його невеликий (8-32 Кбайт), і для підвищення продуктивності для даних і команд часто використовується роздільний кеш (так звана Гарвардська архітектура - протилежність Прістонській, що використовує загальну пам’ять для команд і даних). Швидкодія його така, що він працює на внутрішній тактовій частоті процесора (CPU Clock), уже досягла 333 МГц . Вторинний кеш (L2 Cache) зазвичай встановлюється на системній платі. Типовим для комп'ютерів на процесорі i486 вважається обсяг 64-256 Кбайт, для Pentium - 256-512 Кбайт, нові чипсети підтримують до 2 Мбайт L2 Cache. Його швидкодія забезпечує роботу на зовнішній тактовій частоті процесора - частоті системної шини (Host Bus Clock), типове значення якої від діапазону 50-66 МГц вже переходить до 75, 83 і навіть 100-125 МГц. У Pentium Pro синхронний L2 Cache розташований в одному корпусі з процесором і працює на його внутрішній частоті.

Кеш-контролер повинен забезпечувати когерентність (coherency) - узгодження даних кеш-пам'яті обох рівнів з даними в основній пам'яті, причому звернення до цих даних може здійснюватися не тільки з боку процесора (а процесорів може бути і декілька, і в кожного може бути свій внутрішній кеш), але і з боку інших активних (bus-master) адаптерів, підключених до шин (PCI, VLB, ISA ...).

Контролер кеша оперує рядками (cache line) фіксованої довжини. Рядок може зберігати копію блоку основної пам'яті, розмір якого збігається з довжиною рядка. З кожним рядком кеша пов'язана інформація про адресу скопійованого в неї блоку основної пам'яті і ознаки її стану. Рядок може бути дійсним (valid) - це означає, що в поточний момент часу вона достовірно відображає відповідний блок основної пам’яті, або недійсною (порожній).

Інформація про те, який саме блок займає даний рядок (тобто старша частина адреси чи номер сторінки), і її стан називається тегом (tag) і зберігається у зв'язаній з даною рядком комірці спеціальної пам'яті тегів (tag RAM). В операціях обміну з основною пам'яттю зазвичай рядок бере участь цілком (несекційний кеш), для процесора i486 і старше довжина рядка збігається з обсягом даних, переданих за один пакетний цикл (для 486 це 4x4 = 16 байт, для Pentium - 4x8 = 32 байт ). Можливий і варіант секційного (sectored) кеша, при якому один рядок містить кілька суміжних осередків - секторів, розмір яких відповідає мінімальній порції обміну даних кеша з основною пам'яттю. При цьому в записі каталогу, відповідної кожному рядку, повинні зберігатися біти дійсні для кожного сектора даного рядка. Секціювання дозволяє економити пам'ять, необхідну для зберігання каталогу при збільшенні обсягу кешу, оскільки більша кількість біт каталогу відводиться під тег і вигідніше використовувати додаткові біти дійсності, ніж збільшувати глибину індексу (кількість елементів) каталогу.

Рядки кешу під відображення блока пам'яті звичайно виділяються тільки при операціях читання. Запис блоку, що не має копії в кеші, проводиться тільки в основну пам'ять (для підвищення швидкодії вона може проводитися через буфер відкладеного запису, але це окремий механізм, який не має безпосереднього відношення до даного кешування ). Поведінка кеш-контролера при операції запису в пам'ять, коли копія області, що необхідна, знаходиться у деякому рядку кеша, визначається його політикою запису (Write Policy). Існують два основні алгоритми запису даних з кеша в основну пам'ять: наскрізний запис WT (Write Through) і зворотний запис WB (Write Back). Алгоритм WT передбачає виконання кожної операції запису (навіть однобайтної), що потрапляє у керуючий блок, одночасно і в рядок кеша, і в основну пам'ять. При цьому, процесор при кожній операції запису має чекати закінчення щодо тривалого запису в основну пам'ять. Алгоритм досить простий в реалізації і легко забезпечує цілісність даних за рахунок постійного збігу копій даних в кеші і основній пам'яті. Для нього немає необхідності зберігання ознаки стану і модифікації цілком, достатньо лише інформації тега (при цьому вважається, що будь-який рядок завжди відображає блок, на який саме - вказує тег). Але ця простота оплачується низькою ефективністю запису

Існують варіанти цього алгоритму із застосуванням відкладеного буферізованого запису, при цьому дані в основну пам'ять переписуються через FIFO-буфер під час вільних тактів шини.

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

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

Залежно від способу визначення взаємної відповідності рядка кеша і області основної пам'яті розрізняють три архітектури кеш-пам'яті, а саме: кеш прямого відображення (direct-mapped cache); повністю асоціативний кеш (fully associative cache) та їх комбінація - частково - або набірно-асоціативний кеш (set-associative cache).

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

Рисунок 4.2.- Структура кешу прямого відображення

Основна пам'ять, що керується, умовно розбивається на сторінки (в даному випадку 256), розмір яких збігається з розміром кеш-пам'яті. Кеш пам'ять (і знову-таки умовно сторінки основної пам'яті) ділиться на рядки (256К/32 = 8К рядків). Архітектура прямого відображення має на увазі, що кожен рядок кеша може відображати з будь-якої сторінки пам'яті, що керується, тільки відповідний їй рядок (на рисунку 4.3.1. вони знаходяться на одному горизонтальному рівні). Оскільки обсяг основної пам'яті значно більше обсягу кешу, на кожен рядок кеша може претендувати безліч блоків пам'яті з однаковою молодшою частиною адреси (зміщенням всередині сторінки).

Один рядок в певний момент може містити копію тільки одного з цих блоків. Номер (адреса) рядка в кеш-пам'яті називається індексом (index). Інформація про те, який саме блок займає даний рядок (тобто старша частина адреси чи номер сторінки), називається тегом (tag) і зберігається у зв'язаній з даним рядком комірці спеціальної пам'яті тегів (tag RAM). Наймолодші біти адреси визначають положення байта в банку пам'яті (А [0:2]) і в рядку (A3, А4), але для роботи кеш-контролера вони несуттєві. Пам'ять тегів повинна мати кількість осередків, дорівнює кількості рядків кеша, а її розрядність повинна вміщати старші біти адреси пам'яті,що кешується, що не потрапили на шину адреси кеш-пам'яті. Крім адресної частини тега з кожним рядком кеша пов'язані біти ознак дійсності і модифікуванні даних.

На початку кожного звернення до пам'яті, що керується, контролер насамперед зчитує комірку каталогу із заданим індексом, порівнює біти адрес тега зі старшими бітами адреси пам'яті та аналізує ознаку дійсності. Цей аналіз виконується в спеціальному циклі стеження (snoop cycle), іноді його називають циклом запиту (inquire). Якщо в результаті аналізу з'ясувалося, що потрібний блок не знаходиться в кеші, то генерується (або продовжується ) цикл звернення до основної пам'яті (випадок кеш-промаху); у разі потрапляння запит обслуговується кеш-пам'яті. У разі промаху після зчитування з основної пам'яті нові дані містяться і в рядку кеша (якщо вона чиста), а в її тег поміщаються старші біти адреси і встановлюється ознака дійсності даних. Незалежно від обсягу даних, що потребується, в кеш з основної пам'яті, рядок переписується цілком (оскільки ознака дійсності належить до всіх її байтів). Якщо контролер кеша реалізує випереджаюче зчитування (read ahead), то в наступні вільні цикли шини оновиться і наступний за нею рядок (якщо він був чистий). Це читання «про запас» дозволить при необхідності здійснювати пакетний цикл зчитування з кешу через межі рядка.

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

Іноді в описі кеша прямого відображення фігурує поняття набір (set), що може збити з пантелику. Воно застосовується замість терміна рядок (line) в секційному кеші прямого відображення, а сектор тоді називають рядком. З набором (як і рядком несекційного кешу) пов'язана інформація про теги, що відноситься до всіх елементів набору (рядках або секторам).