Міністерство освіти Російської Федерації
Марійський державний технічний університет
Факультет ФІОТ
Кафедра ІТТ
Механізм когерентності узагальненого кільцевого гіперкуба з безпосередніми зв'язками
ПОЯСНЮВАЛЬНА ЗАПИСКА
до курсової роботи з дисципліни
паралельних обчислювальних системах.
Виконав:студент групи ВМ-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 такту; < p> • кеш 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 необхідне забезпечення вищевказаногопорядку виконання транзакцій. Кожен рядок кеш-пам'яті ВМ може знаходитисяв одному з наступних станів:
М - рядок модифікована (доступна з читання і запису тільки в цьому
ВМ, тому що модифікована командою запису в порівнянні з рядкомосновної пам'яті);
Е - рядок монопольно копіювати (доступна з читання і запису в цьому
ВМ і в основній пам'яті);
S - рядок множественно копіювати або Колективна (доступна зачитання і запису в цьому ВМ, в основній пам'яті і в кеш-пам'яті інших ВМ, вяких міститься її копія);
1 - рядок, неможлива до використання (рядок не доступна ні почитання, ні за записом).
Стан рядка використовується, по-перше, для визначення процесором
ВМ можливості локального, без виходу на шину, доступу до даних у кеш -пам'яті, а, по-друге, - для управління механізмом когерентності.
Для управління режимом роботи механізму підтримки когерентностівикористовується біт WT, стан 1 якого задає режим наскрізний (write -through) запису, а стан 0 - режим зворотного (write-back) записи в кеш -пам'ять.
Промах читання в кеш-пам'яті змушує викликати рядок з основноїпам'яті і зіставити їй стан Е або 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)
;
2. Ступінь (S)
S = 2n = 6;
3. Кількість вузлів (N)
4. Загальне число зв'язків
5. Відмовостійкість
2. Алгоритми механізму когерентності для узагальненого кільцевого гіперкуба
Для КС типу узагальнений кільцевої гіперкуба можна реалізувати алгоритммеханізму підтримки когерентності - DASH, описаний вище в п.1.2.2.2.
Так як вузол гіперкуба можна розуміти як ЦП розділений на:
2.1 Операція читання
2.2 Операція запису
Висновок
У даній роботі ми вивчили механізм підтримки когерентності. Алгоритми їх роботи. Розглянули КС типу узагальнений кільцевої Гіперкуб, розрахували основні оцінки параметрів даного гіперкуба (Мал. 1). Більш докладно ми зупинилися на алгоритмі DASH, який найбільшою мірою підходить до КС типу узагальнений кільцевої Гіперкуб. При побудові алгоритму ми бачимо, що для даної КС з безпосередніми зв'язками, чим більше структура, тим довше очікування ЦП на запити заборони рядка. Оскільки зі збільшенням структури буде збільшуватися діаметр і до останнього вузла повідомлення буде доходити з великим запізненням, що викличе простих запитів процесора.
У той же час, якщо б ми використовували структуру з магістральними зв'язками, даний алгоритм підтримки когерентності буде працювати набагато ефективніше, т. к. діаметр буде постійний.
Список літератури
1. Артамонов Г.Т. «Топологія регулярних обчислювальних мереж і середовищ. №» М.:
Радіо і зв'язок, 1985.
2. Власов А.А. «Комутаційні структури та комунікаційні середовища:
Лабораторний практикум.» - Йошкар-Ола: МарГТУ, 2002.
3. Горяшко А.П. «Спеціалізовані обчислювальні структури.»
/Штучний інтелект, Кн.3. Програмні та апаратні засоби. М.:
Радіо і зв'язок, 1987.
4. Корнєєв В.В. «Паралельні НД», М., Нолидж, 1999.
5. www.narod.nov.ru/par.html «Мультипроцесорна когерентність кеш-пам'яті»
-----------------------
Операційний процесор
Комутаційний процесор
КЕШ
Виконує всі обчислення але не може зв'язуватися з іншим процесором
Здійснює зв'язок з іншими процесорами
Зберігає копії строк
ПОЧАТОК
Запит на читання
Рядок змінена або Колективна
немає
так
Неможлива до використання
Запит у резидентний модуль, "промах читання"
1
Читання
2
1
Некешірованная або віддалено-розділена рядок
ПОЧАТОК
2
КІНЕЦЬ
Установка стану рядки в «віддалено-рспределенная»
Пересилання цього рядка в запросив. модуль і в резидентних.
Запит «промах читання» прямує в модуль вмісту. зм. рядок
Рядок «віддалено-змінена»
так
немає
Пересилання копії рядка в запитав модуль
так
немає
Запит на запис
Рис. 1
змінена
Запис
КІНЕЦЬ
некешірованная
так
немає
Пересилання рядка запиту модулю
Неможлива до використання
Запит у резидентний модуль на захоплення рядки
так
немає
листи розсилаються модулів, що мають копію рядки, запиту на переклад рядка встан «неможливого до використання»
