Зв'язок між елементами паралельних обчислювальних систем

Комунікаційна мережа пов’язує процесори з оперативною пам’яттю, процесами між собою, іншими пристроями. Вона впливає на працездатність системи. Трафік в такій мережі складається х пересилання даних і команд. Комунікаційна мережа – це найважливіший елемент архітектури будь-якого комп’ютера. Основна характеристика – пропускна здатність, яка вимірюється в біт/с. Багатопроцесорний комп’ютер – це набір вузлів (процесорних елементів, модулів пам’яті, перемикачі) і з’єднань між вузлами.

Організація внутрішніх комунікацій обчислювальної системи називається її топологією.

Дві вузла іменуються сусідніми, якщо між ними є пряме з’єднання.

Порядком вузла називається кількість його сусідів.

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

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

Є два типи топології комп’ютерної мережі:

· Статичні

· Динамічні

У випадку статичної мережі всі з’єднання фіксовані, а в динамічній мережі в мікропроцесорних з’єднаннях використовують перемикачі.

 

Методи комутації (перемикання)

Методи комутації (перемикання) визначають, як повідомлення передаються від вузла джерела до вузла приймача.

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

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

Виділяють три основні методи комутації в комутаційних мережах паралельних обчислювальних систем (КОС):

1) комутація з проміжним зберіганням (зберігання-і-передача або “store-and-forward”);

2) комутація ланцюгів;

3) «метод віртуальних каналів».

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

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

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

 

Лекція №4

Пам'ять багатопроцесорних обчислювальних систем

Оперативна пам'ять (характеристики і особливості будови)

Час циклу роботи з пам’яттю t_m зазвичай значно більший, ніж час циклу центрального процесора (ЦП) t_c. Якщо процесор ініціалізує звернення до пам’яті, то вона буде зайнята на протязі часу t_c+ t_m і впродовж цього відрізку часу жоден з пристроїв, у тому числі і сам процесор, не зможе працювати з оперативною пам’яттю. Таким чином, виникає проблема доступу до пам'яті. Ця проблема вирішується спеціальною організацією оперативної пам'яті (ОП).

Прийнята наступна класифікація паралельних комп’ютерів за архітектурою підсистем ОП:

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

2) системи з розподіленою пам’яттю, в яких кожен процесор маю свою власну локальну ОП і до цієї пам'яті в інших процесорів немає доступу.

Різниця між розділяючою і розподіленою пам’яттю полягає у засобі інтерпретації адреси. Наприклад, нехай один з процесорів виконує команду load r1,і (завантаження в регістр r1 даних з комірки пам'яті «і»). Якщо команда виконується на комп’ютері з розділяючою пам’яттю, то номер комірки «і» має однаковий зміст для всіх процесорів, тобто «і» - глобальна адреса. В системах з розподіленою пам’яттю, то комірка «і» різна для різних процесорів і в регістр r1 за цією командою будуть завантажені різні значення.

Розділяюча пам'ять

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

Кеш-пам'ять

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

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

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

Обчислювальною системою (ОС) з розділяючою пам'яттю є комп’ютери фірми Kendall Square Research.

Чередуюча пам'ять

Чергуюча пам'ять розділяється на банки пам'яті. Прийнято, що комірка пам'яті з номером «і» знаходиться в банкові пам'яті i mod n, де n – це кількість банків пам’яті, mod – операція обчислення залишку від ділення. Якщо є 8 банків пам'яті, то першому будуть належати комірки пам'яті з номерами 0, 8, 16, …, другому – 1, 9, 17, …, і т.д. Запити до різних банків пам'яті можуть оброблюватись одночасно.

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

Комірки пам'яті можуть бути пронумеровані і неперервним чином, тобто в першому банку знаходяться комірки з номерами від 0 до 255, в другому – від 256 до 511 і т.д. В векторних комп’ютерах зазвичай використовується перший спосіб адресації, а в багатопроцесорних комп’ютерах з розділяючою пам'яттю – другий.

Розподілена пам'ять

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

Програмування для систем з розподіленою пам'яттю потребує розбиття вихідної задачі на підзадачі, виконання яких може бути доручено різним процесорам. Одним з комп’ютерів такого типу є СМ-5 фірми Thinking Machines. Ця система складається з процесорних елементів, побудованих за допомогою мікропроцесора SPARC і з’єднаних мережею зі спеціальною топологією типу «дерево». У кожного процесорного елемента є своя локальна пам'ять об’ємом 32Мб.

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