Механизм когерентності узагальненого кільцевого гиперкуба й з безпосередніми связями

Міністерство освіти Російської Федерации.

Марійський державний технічний университет.

Факультет ФИВТ.

Кафедра ИВС.

Механізм когерентності узагальненого кільцевого гиперкуба й з безпосередніми связями.

ПОЯСНЮВАЛЬНА ЗАПИСКА.

до курсової роботу з дисциплине.

ПАРАЛЕЛЬНІ ОБЧИСЛЮВАЛЬНІ СИСТЕМЫ.

Выполнил: студент групи ВМ-42 Трохимец Г. М.

(дата) (підпис) Перевірив: к.т.н., доцент Власов А.А.

(дата) (подпись).

Оценка:

р. Йошкар-Ола.

2002 г.

Аннотация.

У цьому роботі було розглянуто механізми підтримки когерентності в многопроцессорной ЗС. Також розглянута комутаційна структура типу узагальненого кільцевого гиперкуба, до котрої я підібрали свій механізм когерентности.

Зміст Запровадження 4 Технічне завдання 5 1. Загальна частина 6 1.1. Механізми підтримки когерентності 6 1.2. Механізми неявній реалізації когерентності 7 1.2.1. Однопроцессорный підхід 8 1.2.2. Многопроцессорный підхід 10 1.2.2.1. Зосереджена пам’ять 10 1.2.2.2. Фізично розподілена пам’ять 12 1.3. КС типу узагальненого кільцевого гиперкуба 15 1.3.1. Розрахунок основних параметрів 16 2. Алгоритми механізму когерентності для узагальненого кільцевого гиперкуба 17 2.1 Операція читання 17 2.2 Операція записи 19 Укладання 20 Список літератури 21.

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

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

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

Сучасна технологічна база СБИС дозволяє створювати обчислювальні системи, містять у собі мільйони процессорных елементів (ПЭ). Перешкодою по дорозі створення таких систем є проблеми, пов’язані улаштуванням управління і обмінів даними під час вирішення завдань широкого класу. У цьому основна складність залежить від організації комутаційної структури з високим рівнем регулярності і високої пропускною спроможністю при порівняно невеликих апаратних затратах.

Відомі комутаційні структури над повною мірою відповідають цим вимогам. Усі комутаційні структури можна розділити на великі групи: КС й з безпосередніми зв’язками і КС з магістральними зв’язками. Ми розглядаємо першу групу — КС й з безпосередніми зв’язками. Зокрема КС узагальненого кільцевого гиперкуба.

Технічне задание.

1. Вивчити механізми підтримки когерентности.

2. Розглянути КС типу узагальнений кільцевої гиперкуб.

3. Скласти алгоритм механізму когерентності КС типу узагальнений кільцевої гіперкуб й з безпосередніми связями.

1. Загальна часть.

1 Механізми підтримки когерентности.

Механізми реалізації когерентності може бути як явними, і неявними для прикладного программиста.

За такої розгляді архітектури ЗС можна класифікувати по способу розміщення даних в ієрархічної пам’яті і способу доступу до цих данным.

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

Неявний розміщення даних; неявний вказівку доступу до даних. У ВР із поділюваної пам’яттю механізм реалізації когерентності прозорий для прикладного програміста, й у програмах відсутні будь-які інші команди звернення до пам’яті, крім команд «читання «(load) і «запис «(store). Використовується єдине фізичне простір чи віртуальний адресу. Архітектура ВР із поділюваної пам’яттю має багато привабливих черт:

• однорідність адресного простору пам’яті, що дозволяє при створенні додатків нехтувати тимчасові співвідношень між зверненнями до різним блокам ієрархічної памяти;

• створення додатків у звичних програмних средах;

• легке масштабирование додатків виспівати на різному числі процесорів і різноманітних ресурсах памяти.

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

Явна розміщення даних із зазначенням поділюваних модулями сторінок; неявний вказівку доступу до даних у вигляді команд load, store.

Існує технологія MEMORY CHANNEL ефективної організації кластерных систем з урахуванням моделі поділюваної пам’яті. Суть технології ось у чому. У кожному комп’ютері кластера передбачається організація пам’яті з урахуванням механізму віртуальної адресації. Адреса при цьому і двох частин: групи бітов, службовців визначення номери сторінки, та власне адреси всередині сторінки. У кожному комп’ютері під час ініціалізації виділяється запропоноване, можливо різне, до повного відсутності, кількість фізичних сторінок пам’яті, поділюваних цим комп’ютером коїться з іншими комп’ютерами кластера.

Після встановлення переважають у всіх комп’ютерах відображення сторінок пам’яті, доступом до віддаленим пам’ятям виконується у вигляді звичайних команд читання (load) і запис (store) як до звичайних сторінкам віртуальної пам’яті без інтерпретацій операційній системі чи бібліотекам часу исполнения.

1.2. Механізми неявній реалізації когерентности.

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

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

1.2.1. Однопроцессорный подход.

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

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

Типова сучасна ієрархія пам’ятей для однопроцессорных ЗС має таку структуру:

• регістри 64 — 256 слів згодом доступу 1 такт процессора;

• кеш 1 рівня — 8к слів з часом доступу 1—2 такта;

• кеш 2 рівня — 256к слів з часом доступу 3—5 тактов;

• основна пам’ять — до запланованих 4 Гигаслов з часом доступу 12−55 тактів. Кеш має сукупність рядків (cache-lines), кожна з яких складається з фіксованого кількості адресованих одиниць пам’яті (байтів, слів) з послідовними адресами. Типовий розмір строки:

16, 32, 64, 128, 256 байтов.

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

Це правда звані, кеш-пам'ять з прямим відображенням (direct-mapped, cache), частково асоціативна кеш-пам'ять (set-associative cache) і асоціативна кеш-пам'ять (fully associative cache).

Реалізація механізму когерентності найчастіше здійснюється з використанням відстежування (snooping) запитів на шині, яка зв’язує процесор, пам’ять і інтерфейс ввода/вывода. Контролер кешу відстежує адреси пам’яті, видані процесором, і якщо адресу відповідає даним, які мають одній з рядків кешу, то відзначається «потрапляння до кеш », і дані з кешу направляють у процесор. Якщо даних в кэше немає, то фіксується «промах «і ініціюються дії з доставці в кеш з пам’яті необхідної рядки. У багатьох процесорів, виконують одночасно сукупність команд, допускається кілька промахів, як буде задіяно механізм заміни строк.

1.2.2. Многопроцессорный подход.

У середовищі сучасних мікропроцесорах, що використовуються побудови мультипроцессорных систем, ідентичність даних в кэшах ВМ (когерентність кэшей) підтримується з допомогою межмодульных пересилань. Існує кілька радикальних способів реалізації когерентності, що застосовуються у залежність від типу використовуваної комунікаційної середовища проживання і зосередженості чи фізичної распределенности пам’яті між процессорными модулями.

1.2.2.1. Зосереджена память.

Розглянемо реалізацію однієї з алгоритмів підтримки когерентності кэшей, відомий як MESI (Modified, Exclusive, Shared, Invalid) [б]. Алгоритм MES1 є організацію когерентності кэшпамяти з зворотної записом. Цей алгоритм запобігає зайві передачі між кэш-памятью і основний пам’яттю. Тож якщо дані в кеш-пам'яті не змінювалися, то нема чого їх пересилати. Поставимо деякі початкові умови і введемо визначення. Отже, кожен ВМ має власну локальну кеш-пам'ять, є спільна розділюваний основна пам’ять, все ВМ під'єднані до основний пам’яті у вигляді шини. До шині підключені також зовнішні устрою. Важливо розуміти, що це дії з допомогою транзакцій шини, вироблені ВМ зовнішніми пристроями, з копіями рядків, як і кожної кеш-пам'яті, і в основний пам’яті, доступні для відстежування всім ВМ. Це є наслідком те, що у кожний момент на шині передає лише одне, а сприймають все, підключені шині абоненти. Тому, для об'єднання ВМ використовується не шина, а інший тип комутаційної середовища, то для працездатності алгоритму MES1 необхідно забезпечення вищевказаного порядку виконання транзакцій. Кожний рядок кеш-пам'яті ВМ може бути у одному з наступних состояний:

М — рядок модифікована (доступна читання і запис лише цього ВМ, оскільки модифікована командою записи порівняно з рядком основний памяти);

Є - рядок монопольно копированная (доступна читання і запис у тому ВМ й у основний памяти);

P.S — рядок множинне копированная чи розділюваний (доступна по читання і запис у тому ВМ, в основний пам’яті й у кэш-памятях інших ВМ, в яких міститься її копия);

1 — рядок, неможлива для використання (рядок недоступна ні з читання, ні з записи).

Стан рядки використовується, по-перше, визначення процесором ВМ можливості локального, не маючи виходу на шину, доступу до даних в кешпам’яті, а, по-друге, — керувати механізмом когерентности.

Для управління режимом роботи механізму підтримки когерентності використовується біт WT, стан 1 якого задає режим наскрізний (writethrough) записи, а стан 0 — режим зворотної (write-back) запис у кешпамять.

Промах читання в кеш-пам'яті змушує викликати рядок із основний пам’яті і зіставити їй стан Є чи P. S. Кеш-пам'ять заповнюється лише при промахи читання. При промаху записи транзакція записи міститься у буфер і посилається в основну пам’ять при наданні шины.

Для підтримки когерентності рядків кеш-пам'яті під час операції ввода/вывода і зверненнях в основну пам’ять інших процесорів на шині генеруються спеціальні цикли опитування стану кэш-памятей. Ці цикли опитують кеш-пам'яті щодо зберігання ЕВР у них рядки, котра має адресу, вживаний у операції, яка ініціювала цикли опитування стану. Можливий режим примусового перекладу рядки у стан I, який задається сигналом INV.

1.2.2.2. Фізично розподілена память.

Прямолінійний підхід до підтримки когерентності кэшей в мультипроцессорной системі, основна пам’ять якій розподілена по ВМ, у тому, що з кожному промаху в кеш у кожному процесорі ініціюється запит необхідної рядки того блоку пам’яті, у якому ця рядок розміщена. Надалі цього блоку пам’яті буде стосовно цієї рядку називатися резидентным. Запит передається через комутатор в модуль з резидентным для рядки блоком пам’яті, з яких потім необхідна рядок через комутатор пересилається в модуль, де відбувся промах. Отже, зокрема, забезпечується початкова заповнення кэшей. При цьому кожному модулі кожної резидентной рядки ведеться список модулів, в кэшах яких ця рядок розміщається, або організується розподілений по ВМ список цих рядків. Рядок, розміщена в кэше більш як одного модуля, в надалі називатися разделяемой.

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

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

З кожної рядком в резидентном нею модулі пов’язані три її можливих глобальних состояния:

1) «некэшированная », якщо копія рядки не в кэше якогоабо іншого модуля, крім, можливо, резидентного з цією строки;

2) «удаленно-разделенная », якщо копії рядки розміщені в кэшах інших модулей;

3) «удаленно-измененная », якщо рядок змінена операцією запис у якомусь модуле.

Крім цього, кожна рядок кешу перебуває у одному із трьох локальних состояний:

1) «неможлива для використання » ;

2) «розділюваний », если. есть неизмененная копія, яка, можливо, размешается й у інших кэшах;

3) «змінена », якщо копія змінена операцією записи. Кожен процесор може читати зі свого кешу, якщо вже стан читаних рядки «розділюваний «чи «змінена ». Якщо рядок немає у кэше чи перебуває у стані «неможлива для використання », то посилається запит «промах читання », які направляють в модуль, резидентный для необхідної строки.

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

Якщо стан рядки «удаленно-измененная », то запит «промах читання «перенаправляється в модуль, у якому змінену рядок. Цей модуль пересилає необхідну рядок в запросивший модуль й у модуль, резидентный з цією рядки, й встановлює в резидентном модулі з цією рядки стан «удаленно-распределенная » .

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

Якщо глобальне стан рядки у резидентном модулі «некэшированная », то рядок відсилається запросившему модулю, і це модуль продовжує призупинені вычисления.

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

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

1.3. КС типу узагальненого кільцевого гиперкуба.

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

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

Кожен вузол середовища має 6 двунаправленных каналів ввода/вывода, які використовуються у ролі безпосередніх зв’язку з сусідніми вузлами (Мал.1). Можливо, застосування двох зустрічних односпрямованих каналів замість одного двунаправленного, що дозволяє збільшити пропускну здатність при незначному збільшенні апаратних витрат. Кожен вузол також має 6 магістральних каналів ввода/вывода — дві у кожному вимірі. Комунікаційний процесор виробляє прием/передачу інформації каналами ввода/вывода, причому придатна як комутація пакетів, і комутація каналов.

1.3.1. Розрахунок параметров.

Розрахуємо оцінки параметрів кільцевого гиперкуба при n=3, m=3. Де n — кількість вимірів, а m — размерность.

1. Діаметр (D).

[pic];

2. Ступінь (S).

S=2n = 6;

3. Кількість вузлів (N).

[pic].

4. Загальна кількість связей.

[pic].

5. Отказоустойчивость.

[pic].

2. Алгоритми механізму когерентності для узагальненого кільцевого гиперкуба.

Для КС типу узагальнений кільцевої гиперкуба можна реалізувати алгоритм механізму підтримки когерентності - DASH, описане вище в п. 1.2.2.2. Оскільки вузол гиперкуба можна розуміти як ЦП розділений на:

2.1 Операція чтения.

2.2 Операція записи.

Заключение

.

У цьому роботі ми вивчили механізми підтримки когерентності. Алгоритми його роботи. Розглянули КС типу узагальнений кільцевої гіперкуб, розрахували основні оцінки параметрів даного гиперкуба (Рис. 1). Докладніше ми зупинилися на алгоритмі DASH, що у найбільшою мірою наближається до КС типу узагальнений кільцевої гіперкуб. При побудові алгоритму бачимо, що з даної КС й з безпосередніми зв’язками, що більше структура, тим довше очікування ЦП на запити заборони рядки. Т.к. зі збільшенням структури збільшуватиметься діаметр до останнього вузла повідомлення буде доходити з великим запізненням, що викликає простий запросившего процесора. У водночас, якщо б ми використовували структуру з магістральними зв’язками, даний алгоритм підтримки когерентності працюватиме значно ефективніше, т.к. діаметр буде постоянен.

1. Артамонов Г. Т. «Топологія регулярних обчислювальних мереж, і середовищ.№» М.:

Радіо і зв’язок, 1985. 2. Власов А. А. «Комутаційні структури та комунікаційні среды:

Лабораторний практикум." - Йошкар-Ола: МарГТУ, 2002. 3. Горяшко О. П. «Спеціалізовані обчислювальні структуры.».

/Штучний інтелект, Кн.3. Програмні і апаратні кошти. М.:

Радіо і зв’язок, 1987. 4. Корнєєв В.В. «Паралельні ЗС», М., Нолидж, 1999. 5. internet «Мультипроцессорная когерентність кеш-памяти».

———————————;

Операційний процессор

Комутаційний процессор

КЕШ.

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

Здійснює зв’язку з іншими процессорами.

Зберігає копії строк.

НАЧАЛО.

Запит на чтение.

Рядок змінена чи разделяемая нет да.

Неможлива до использованию.

Запит в резидентный модуль, «промах чтения».

Чтение.

Некешированная чи удаленно-разделенная строка.

НАЧАЛО.

КОНЕЦ

Установка стану рядки у «удаленно-рспределенная».

Пересилання даної рядки у запросивши. модуль й у резидентн.

Запит «промах читання» направляють у модуль содерж. ізм. строку.

Рядок «удаленно-измененная».

да нет.

Пересилання копії рядки у запросивший модуль.

да нет.

Запит на запись.

Рис. 1.

измененная.

Запись.

КОНЕЦ

некешированная да нет.

Пересилання рядки запросившему модулю.

Неможлива до использованию.

Запит в резидентный модуль захоплення строки.

да нет Рассылка всім модулями, у яких копію рядки, запиту перевести рядки у стан «неможливого до использованию».