Багатопроцесорні системи з загальною пам'яттю
Вимоги, що пред'являються сучасними процесорами до смуги пропускання пам'яті можна істотно скоротити шляхом застосування великих багаторівневих кешей. Тоді, якщо ці вимоги знижуються, то кілька процесорів зможуть розділяти доступ до однієї і тієї ж пам'яті. Починаючи з 1980 року ця ідея, підкріплена широким поширенням мікропроцесорів, стимулювала багатьох розробників на створення невеликих мультипроцессоров, в яких кілька процесорів поділяють одну фізичну пам'ять, з'єднану з ними за допомогою розділяється шини. Через малого розміру процесорів і помітного скорочення необхідної смуги пропускання шини, досягнутого за рахунок можливості реалізації досить великий кеш-пам'яті, такі машини стали виключно ефективними за вартістю. У перших розробках подібного роду машин вдавалося розмістити весь процесор і кеш на одній платі, яка потім вставлялася в задню панель, за допомогою якої реалізовувалася шинна архітектура. Сучасні конструкції дозволяють розмістити до чотирьох процесорів на одній платі. На рис. 10.1 показана схема саме такої машини.
У такій машині кеші можуть містити як колективні, так і приватні дані. Приватні дані - це дані, які використовуються одним процесором, в той час як колективні дані використовуються багатьма процесорами, по суті забезпечуючи обмін між ними. Коли кешируєтся елемент приватних даних, їх значення переноситься в кеш для скорочення середнього часу доступу, а також необхідної смуги пропускання. Оскільки жоден інший процесор не використовує ці дані, цей процес ідентичний процесу для однопроцессорной машини з кеш-пам'яттю. Якщо кешуються колективні дані, то їх поділяє значення реплицируется і може міститися в декількох кешах. Крім скорочення затримки доступу і необхідної смуги пропускання така реплікація даних сприяє також загальне скорочення кількості обмінів. Однак кешування поділюваних даних викликає нову проблему: когерентність кеш-пам'яті.
Мультипроцессорная когерентність кеш-пам'яті
Проблема, про яку йде мова, виникає через те, що значення елемента даних в пам'яті, що зберігається в двох різних процесорах, є цим процесорам тільки через їх індивідуальні кеші. На рис. 10.3 показаний простий приклад, який ілюструє цю проблему.
Проблема когерентності пам'яті для мультипроцессоров і пристроїв введення / виводу має багато аспектів. Зазвичай в малих мультипроцесорах використовується апаратний механізм, званий протоколом, що дозволяє вирішити цю проблему. Такі протоколи називаються протоколами когерентності кеш-пам'яті. Існують два класи таких протоколів:
- Протоколи на основі довідника (directory based). Інформація про стан блоку фізичної пам'яті міститься тільки в одному місці, званому довідником (фізично довідник може бути розподілений по вузлах системи). Цей підхід буде розглянуто в розд. 10.3.
- Протоколи спостереження (snooping). Кожен кеш, який містить копію даних деякого блоку фізичної пам'яті, має також відповідну копію службової інформації про його стан. Централізована система записів відсутня. Зазвичай кеші розташовані на загальною (що розділяється) шині і контролери всіх кешей спостерігають за шиною (переглядають її) для визначення того, чи не містять вони копію відповідного блоку.
Мал. 10.3. Ілюстрація проблеми когерентності кеш-пам'яті
У мультипроцесорних системах, що використовують мікропроцесори з кеш-пам'яттю, під'єднані до централізованої загальної пам'яті, протоколи спостереження набули популярності, оскільки для опитування стану кешів вони можуть використовувати заздалегідь існуюче фізичне з'єднання - шину пам'яті.
Неформально, проблема когерентності пам'яті полягає в необхідності гарантувати, що будь-який зчитування елемента даних повертає останнім за часом записане в нього значення. Це визначення не зовсім коректно, оскільки неможливо вимагати, щоб операція зчитування миттєво бачила значення, записане в цей елемент даних деяким іншим процесором. Якщо, наприклад, операція запису на одному процесорі передує операції читання тієї ж осередки на іншому процесорі в межах дуже короткого інтервалу часу, то неможливо гарантувати, що читання поверне записане значення даних, оскільки в цей момент часу записуються дані можуть навіть не залишити процесор. Питання про те, коли точно записується значення має бути доступне процесору, що виконує читання, визначається обраною моделлю узгодженого (несуперечливого) стану пам'яті і пов'язаний з реалізацією синхронізації паралельних обчислень. Тому з метою спрощення припустимо, що ми вимагаємо лише, щоб записане операцією запису значення було доступно операції читання, що виникла трохи пізніше записи і що операції записи даного процесора завжди видно в порядку їх виконання.
З цим простим визначенням узгодженого стану пам'яті ми можемо гарантувати когерентність шляхом забезпечення двох властивостей:
- Операція читання комірки пам'яті одним процесором, яка слідує за операцією запису в ту ж комірку пам'яті іншим процесором отримає записане значення, якщо операції читання і запису досить відокремлені один від одного за часом.
- Операції запису в одну і ту ж комірку пам'яті виконуються строго послідовно (іноді кажуть, що вони серіалізовані): це означає, що дві поспіль йдуть операції записи в одну і ту ж комірку пам'яті спостерігатимуться іншими процесорами саме в тому порядку, в якому вони з'являються в програмі процесора, що виконує ці операції записи.
Перше властивість очевидно пов'язано з визначенням когерентного (погодженого) стану пам'яті: якби процесор завжди б зчитував тільки старе значення даних, ми сказали б, що пам'ять некогерентного.
Необхідність строго послідовного виконання операцій запису є більш тонким, але також дуже важливою властивістю. Уявімо собі, що строго послідовне виконання операцій запису не дотримується. Тоді процесор P1 може записати дані в клітинку, а потім в цей осередок виконає запис процесор P2. Строго послідовне виконання операцій запису гарантує два важливих наслідки для цієї послідовності операцій запису. По-перше, воно гарантує, що кожен процесор в машині в певний момент часу буде спостерігати запис, виконувану процесором P2. Якщо послідовність операцій записи не дотримується, то може виникнути ситуація, коли який-небудь процесор буде спостерігати спочатку операцію записи процесора P2, а потім операцію записи процесора P1, і буде зберігати це записане P1 значення необмежено довго. Більш тонка проблема виникає з підтриманням розумної моделі порядку виконання програм і когерентності пам'яті для користувача: уявіть, що третій процесор постійно читає ту ж саму комірку пам'яті, в яку записують процесори P1 і P2; він повинен спостерігати спочатку значення, записане P1, а потім значення, записане P2. Можливо він ніколи не зможе побачити значення, записаного P1, оскільки запис від P2 виникла раніше читання. Якщо він навіть бачить значення, записане P1, він повинен бачити значення, записане P2, при подальшому читанні. Подібним чином будь-який інший процесор, який може спостерігати за значеннями, записуваними як P1, так і P2, повинен спостерігати ідентичне поведінка. Найпростіший спосіб домогтися таких властивостей полягає в строгому дотриманні порядку операцій записи, щоб всі записи в одну і ту ж комірку могли спостерігатися в тому ж самому порядку. Це властивість називається послідовним виконанням (сериализацией) операцій записи (write serialization). Питання про те, коли процесор повинен побачити значення, записане іншим процесором досить складний і має помітний вплив на продуктивність, особливо в великих машинах.
Альтернативою протоколу записи з анулюванням є оновлення всіх копій елемента даних в разі запису в цей елемент даних. Цей тип протоколу називається протоколом записи з оновленням (write update protocol) або протоколом записи з трансляцією (write broadcast protocol). Зазвичай в цьому протоколі для зниження вимог до смуги пропускання корисно відстежувати, чи є слово в кеш-пам'яті, що розділяється об'єктом, чи ні, а саме, чи міститься воно в інших кешах. Якщо немає, то немає ніякої необхідності оновлювати інший кеш або транслювати в нього оновлені дані.
Різниця в продуктивності між протоколами записи з оновленням і з анулюванням визначається трьома характеристиками:
- Кілька послідовних операцій записи в один і той же слово, що не перемежовуються операціями читання, вимагають декількох операцій трансляції при використовуванні протоколу запису з оновленням, але тільки однієї початкової операції анулювання при використанні протоколу записи з анулюванням.
- При наявності багатослівних блоків в кеш-пам'яті кожне слово, що записується в блок кешу, вимагає трансляції при використовуванні протоколу запису з оновленням, в той час як тільки перший запис в будь-яке слово блоку потребує генерації операції анулювання при використанні протоколу записи з анулюванням. Протокол запису з анулюванням працює на рівні блоків кеш-пам'яті, в той час як протокол записи з оновленням повинен працювати на рівні окремих слів (або байтів, якщо виконується запис байта).
- Затримка між записом слова в одному процесорі і читанням записаного значення іншим процесором зазвичай менше при використанні схеми запису з оновленням, оскільки записані дані негайно транслюються в процесор, що виконує читання (передбачається, що цей процесор має копію даних). Для порівняння, при використанні протоколу записи з анулюванням в процесорі, що виконує читання, спочатку відбудеться анулювання його копії, потім буде проводитися читання даних і його припинення до тих пір, поки оновлена копія блоку не стане доступною і не повернеться в процесор.
На додаток до анулювання або оновлення відповідних копій блоку кеш-пам'яті, в який проводився запис, ми повинні також розмістити елемент даних, якщо під час запису відбувається промах кеш-пам'яті. У кеш-пам'яті з наскрізною записом останнє значення елементу даних знайти легко, оскільки всі записувані дані завжди посилаються також і в пам'ять, з якої останнім записане значення елементу даних може бути вибрано (наявність буферів запису може привести до деякого ускладнення).
Для реалізації процесу спостереження можуть бути використані звичайні теги кеша. Більш того, згадуваний раніше біт достовірності (valid bit), дозволяє легко реалізувати анулювання. Промахи операцій читання, викликані або анулюванням, або яким-небудь іншим подією, також не складні для розуміння, оскільки вони просто засновані на можливості спостереження. Для операцій запису ми хотіли б також знати, чи є інші кешированниє копії блоку, оскільки в разі відсутності таких копій, запис можна не посилати на шину, що скорочує час на виконання записи, а також необхідну смугу пропускання.
Щоб відстежити, чи є блок розділяються, ми можемо ввести додатковий біт стану (shared), пов'язаний з кожним блоком, точно також як це робилося для бітів достовірності (valid) і модифікації (modified або dirty) блоку. Додавши біт стану, що визначає чи є блок розділяються, ми можемо вирішити питання про те, чи повинна запис генерувати операцію анулювання в протоколі з анулюванням, або операцію трансляції при використанні протоколу з оновленням. Якщо відбувається запис в блок, що знаходиться в стані "розділяється" при використанні протоколу записи з анулюванням, кеш формує на шині операцію анулювання і позначає блок як приватний (private). Ніяких подальших операцій анулювання цього блоку даний процесор посилати більше не буде. Процесор з винятковою (exclusive) копією блоку кеш-пам'яті зазвичай називається "власником" (owner) блоку кеш-пам'яті.
При використанні протоколу записи з оновленням, якщо блок знаходиться в стані "розділяється", то кожен запис в цей блок має транслюватися. У разі протоколу з анулюванням, коли посилається операція анулювання, стан блоку міняється з "розділяється" на "неподілюваний" (або "приватний"). Пізніше, якщо інший процесор запитає цей блок, стан знову має змінитися на "розділяється". Оскільки наш спостерігач кеш бачить також всі промахи, він знає, коли цей блок кеша запитується іншим процесором, і його стан повинен стати "розділяється".
Стратегія записи в пам'ять
Оновлення пам'яті під час трансляції
Мал. 10.4. Приклади протоколів спостереження
Якщо процесор використовує багаторівневий кеш з властивостями охоплення, тоді кожен рядок в основному кеші є і у вторинному кеші. Таким чином, активність по спостереженню може бути пов'язана з кешем другого рівня, в той час як більшість активностей процесора можуть бути пов'язані з первинним кешем. Якщо механізм спостереження одержує попадання у вторинний кеш, тоді він повинен виконувати арбітраж за первинний кеш, щоб оновити стан і можливо знайти дані, що зазвичай буде призводити до припинення процесора. Таке рішення було прийнято в багатьох сучасних системах, оскільки багаторівневий кеш дозволяє істотно знизити вимог до смуги пропускання. Іноді може бути навіть корисно дублювати теги у вторинному кеші, щоб ще більше скоротити кількість конфліктів між активностями процесора і механізму спостереження.
У реальних системах існує багато варіацій схем когерентності кеша, в залежності від того чи використовується схема на основі анулювання або оновлення, чи побудована кеш-пам'ять на принципах наскрізний або зворотного запису, коли відбувається оновлення, а також чи має місце стан "володіння" і як воно реалізується. На рис. 10.4 представлені кілька протоколів з наглядом і деякі машини, які використовують ці протоколи.