Архітектура паралельних обчислювальних систем

Класифікація комп'ютерних систем

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

Системи із спільною (такою, що розділяється) пам'яттю (shared memory) — (мультипроцесори), у яких є одна віртуальна пам'ять, а всі процесори мають однаковий доступ до даних та командам, що зберігаються в цій пам'яті (uniform memory access або UMA). За цим принципом побудовані векторні паралельні процесори (parallel vector processor або PVP) та симетричні мультипроцесори (symmetric multiprocessor або SMP).

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

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

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

Історично самою ранньою є класифікація М. Флінна (1966 р.). класифікація заснована на понятті потоку, під яким розуміється послідовність команд або даних, що обробляються процесором. На основі числа потоків команд та потоків даних відокремлюють чотири класи архітектур (рисунок 1.1):

Рисунок 1.1 — Класифікація Флінна.

SISD (Single Instruction, Single Data) — системи, в яких існує одиночний потік команд і одиночний потік даних; до даного типу систем можна віднести звичайні послідовні ЕОМ;
SIMD (Single Instruction, Multiple Data) — системи з одним потоком команд і множинним потоком даних; подібний клас систем складають системи, в яких в кожний момент часу може виконуватися одна й та ж команда для обробки декількох інформаційних елементів;
MISD (Multiple Instruction, Single Data) — системи, в яких існує множинний потік команд і одиночний потік даних; прикладів конкретних ЕОМ, що відповідають даному типу обчислювальних систем, не існує; введення подібного класу робиться для повноти системи класифікації;
MIMD (Multiple Instruction, Multiple Data) — системи з множинним потоком команд і множинним потоком даних; до подібного класу систем належить більшість паралельних багатопроцесорних (багатоядерних) обчислювальних систем.

Більша частина теперішніх «серйозних» комп'ютерів реалізовані в класі MIMD-архітектур. При цьому розглядають наступні основні підкласи.

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

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

Симетричні мультипроцесори (SMP) складаються з сукупності процесорів, що мають спільну пам'ять з єдиним адресним простором та функціюють під керівництвом однієї операційної системи. Недолік — число процесорів, що мають доступ до спільної пам'яті, не можна збільшити. Існує межа нарощування числа процесорів, перевищення якої веде до швидкого зростання втрат на міжпроцесорний обмін даними.

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

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

Векторно-конвеєрні комп'ютери

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

Класичним представленням світу суперкомп'ютерів є перший векторно-конвеєрний комп'ютер Cray-1 (1976 р.). Основні особливості архітектури цього класу комп'ютерів наступні.

Конвеєризація виконання команд.
Незалежність функціональних пристроїв, тобто декілька операцій можуть виконуватись одночасно.
Векторна обробка (набір даних обробляється однією командою).
Зачеплення функціональних пристроїв (виконання декількох векторних операцій в режимі «макроконвеєру»).
Багатопроцесорна обробка (наявність незалежних процесорів дозволяє виконувати декілька незалежних програм).

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

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

Рисунок 2.1 — Приклади алгоритмів, що векторизуются та невекторизуються.

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

Обчислювальні системи з розподіленою пам'яттю

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

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

Рисунок 3.1 — Архітектура багатопроцесорних систем з розподіленою пам'яттю.

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

Паралельні комп'ютери із спільною пам'яттю

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

Зокрема спільна пам'ять може бути фізично розподіленою, але всі процесори мають доступ до пам'яті будь-якого процесору. Основна проблема, яку необхідно при цьому вирішувати — забезпечення когерентності кеш-пам'яті окремих процесорів. Реалізація заходів щодо забезпечення когерентності кешів дозволяє значно збільшити число паралельно працюючих процесорів у порівнянні з SMP-комп'ютером. Такий підхід має назву неоднорідного доступу до пам'яті (non-uniform memory access або NUMA). Серед систем з таким типом пам'яті виділяють:

системи, в яких для представлення даних використовується тільки локальна кеш-пам'ять процесорів (cache-only memory architecture або COMA);
системи, в яких забезпечується когерентність локальних кешів різних процесорів (cache-coherent NUMA або CC-NUMA);
системи, в яких забезпечується спільний доступ до локальної пам'яті різних процесорів без підтримки на апаратному рівні когерентності кешу (non-cache coherent NUMA або NCC-NUMA).

Рисунок 4.1 — Архітектура багатопроцесорних систем із спільною пам'яттю: системи з однорідним (а) та неоднорідним (б) доступом до пам'яті.

На рисунку 4.1 наведено деякі типові схеми зв'язків елементів в мульпроцесорних системах.

Використання розподіленої спільної пам'яті (distributed shared memory чи DSM) спрощує проблеми створення мультипроцесорів (відомі приклади з тисячами процесорів). Але при побудові паралельних алгоритмів в даному випадку необхідно враховувати, що час доступу до локальної та віддаленої пам'яті може різнитися на декілька порядків. Для забезпечення ефективності алгоритму в цьому випадку слід в явному виді планувати розподіл даних і схему обміну даними між процесорами таким чином, щоб мінімізувати звернення до віддаленої пам'яті.

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

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

Кластери

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

Один з перших кластерних проектів — Beowulf-кластери. Перший кластер було зібрано в 1994 році в центрі NASA Goddard Space Flight Center (GSFC). Він включав 16 процесорів Intel 486DX4/100 МГц. На кожному вузлі було встановлено по 16 Мбайт оперативної пам'яті та мережеві карти Ethernet. Пізніше був зібраний кластер TheHIVE (Highly-parallel Integrated Virtual Environment). Цей кластер містив в собі 332 процесори і два виділених хост-комп'ютери. Всі вузли кластеру працювали від керуванням Red Hat Linux.

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

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

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

Концепція GRID та метакомп'ютинг

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

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

З вказаних особливостей слідує, що метакомп'ютер — це не тільки і не на стільки самі обчислювальні пристрої, скільки інфраструктура. В даному випадку в комплексі повинні розглядатися моделі програмування, розподіл та диспетчеризація завдань, організація доступу, інтерфейс з користувачем, безпека, надійність, політика адміністрування, засоби та технології розподіленого зберігання даних та інше. Необхідно підкреслити, що розвиток ідей метакомп'ютингу пов'язаний з актуальними проблемами переробки великих об'ємів інформації. Характерною задачею є створення інформаційної інфраструктури для підтримки експериментів у фізиці високих енергій в Європейському центрі ядерних досліджень (CERN). Для обробки великого об'єму даних доцільно створення ієрархічно розподіленої системи, що включає ряд зв'язаних високошвидкісними телекомунікаційними каналами центрів різного рівня. При цьому центри можуть бути віддалені один від одного на значні відстані. Основою для побудови інфраструктури вказаного типу є GRID-технології. GRID-технології — це тип паралельно розподіленої системи, яка дозволяє розділення, вибір та накопичення географічно розподілених «автономних» ресурсів в реальному часі в залежності від їх придатності, можливостей, роботи, ціни та вимогам якості обслуговування користувачів. Це технологія сумісного використання обчислювальних потужностей та сховищ даних, універсальна програмно-апаратна інфраструктура, що об'єднує розрізнені комп'ютери у єдину територіально-розподілену інформаційно-обчислювальну систему.

Література

Ian Foster. Designing and Building Parallel Programs. Addison-Wesley, 1995.
Jonathan M. D. Hill. An introduction to the data-parallel paradigm. Department of Computer Science, 1994.
P. Mehrotra and J. Van Rosendale. Programming distributed memory architectures. In Advances in Languages and Compilers for Parallel Computing. MIT Press, 1991.
Rajkumar Buyya. High Performance Cluster Computing: Architectures and Systems, Prentice Hall PTR, 1999.
Graham E. Fagg, Jack J. Dongarra. PVMPI: An integration of the PVM and MPI systems. Calculateurs Paralleles, 1996.