Московський Державний Інженерно-Фізичний Інститут

(Технічний Університет)

Студентa гр.

Викладач Фісун В.А.

Москва 1998

Класифікація систем паралельної обробки даних

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

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

Паралельні ЕОМ часто поділяються за класифікацією Флінна намашини типу SIMD (Single Instruction Multiple Data - з одним потоком командпри множині потоці даних) і MIMD (Multiple Instruction Multiple Data
- З множинним потоком команд при множині потоці даних). Як ібудь-яка інша, наведена вище класифікація недосконала: існуютьмашини прямо в неї не потрапляють, є також важливі ознаки, які вцієї класифікації не враховані. Зокрема, до машин типу SIMD частовідносять векторні процесори, хоча їх висока продуктивність залежить відіншої форми паралелізму - конвеєрної організації машини.
Багатопроцесорні векторні системи, типу Cray Y-MP, складаються з декількохвекторних процесорів і тому можуть бути названі MSIMD (Multiple SIMD).

Класифікація Флінна не робить розходження з інших важливих дляобчислювальних моделей характеристикам, наприклад, за рівнем "зернистості"паралельних обчислень і методів синхронізації.

Можна виділити чотири основних типи архітектури систем паралельноїобробки:
1) Конвеєрна і векторна обробка.

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

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

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

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

Така архітектура з розподіленою пам'яттю часто згадується якархітектура з паралелізмом даних (data-parallel), тому що паралельністьдосягається при наявності одиночного потоку команд, що діє одночаснона декілька частин даних. Мережа, що з'єднує процесори, звичайно маєрегулярну топологію таку як кільце SLAP:

Мережа з топологією кільце

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

Моделі обчислень на векторних і матричних ЕОМ настільки схожі, щоці ЕОМ часто обговорюються як еквівалентні.
3) Машини типу MIMD.

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

MIMD архітектури далі класифікуються в залежності від фізичноїорганізації пам'яті, тобто чи має процесор свою власну локальнупам'ять і звертається до інших блоків пам'яті, використовуючи комутуючих мережу,або комутуються мережа приєднує всі процесори до загальнодоступної пам'яті.
Виходячи з організації пам'яті, розрізняють наступні типи паралельнихархітектур:
• Комп'ютери з розподіленою пам'яттю (Distributed memory)
Процесор може звертатися до локальної пам'яті, може посилати й одержуватиповідомлення, що передаються по мережі, що з'єднує процесори. Повідомленнявикористовуються для здійснення зв'язку між процесорами або, щоеквівалентно, для читання і запису віддалених блоків пам'яті. Уідеалізованої мережі вартість посилки повідомлення між двома вузлами мережіне залежить як від розташування обох вузлів, так і від трафіку мережі, алезалежить від довжини повідомлення.

• Комп'ютери з загальною (що розділяється) пам'яттю (True shared memory)
Всі процесори спільно звертаються до загальної пам'яті, звичайно, через шину абоієрархію шин. У ідеалізованої PRAM (Parallel Random Access Machine --паралельна машина з довільним доступом) моделі, часто використовується втеоретичних дослідженнях паралельних алгоритмів, будь-який процесор можезвертатися до будь-якої комірки пам'яті за один і той же час. На практицімасштабованість цієї архітектури зазвичай призводить до певної форміієрархії пам'яті. Частота звертань до загальної пам'яті може бути зменшена зарахунок збереження копій часто використовуваних даних у кеш-пам'яті, пов'язаної зкожним процесором. Доступ до цього кеш-пам'яті набагато швидше, ніжбезпосередньо доступ до загальної пам'яті.
• Комп'ютери з віртуальною загальною (що розділяється) пам'яттю (Virtual sharedmemory)

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

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

Мережа з топологією 2D решітка (тор)

Мережа з топологією 2D Гіперкуб (тор)
.

Термін "мультипроцесор" покриває більшість машин типу MIMD і
(подібно до того, як термін "матричний процесор" застосовується до машин типу
SIMD) часто використовується як синонім для машин типу MIMD. Умультипроцесорної системі кожен процесорний елемент (ПЕ) виконує своюпрограму достатньо незалежно від інших процесорних елементів.
Процесорні елементи, звичайно, повинні якось зв'язуватися один з одним,що робить необхідним більш детальну класифікацію машин типу MIMD. Умультипроцесора із загальною пам'яттю (сільносвязанних мультипроцесора)є пам'ять даних і команд, доступна всім ПЕ. Із загальною пам'яттю ПЕзв'язуються за допомогою загальної шини або мережі обміну. На противагу цьомуваріанту в слабосвязанних багатопроцесорних системах (машинах з локальноюпам'яттю) вся пам'ять ділиться між процесорними елементами і кожен блокпам'яті доступний тільки пов'язаному з ним процесора. Мережа обміну пов'язуєпроцесорні елементи один з одним.

Базовою моделлю обчислень на MIMD-мультипроцесорі єсукупність незалежних процесів, епізодично звертаються до поділюванихданими. Існує велика кількість варіантів цієї моделі. На одному кінціспектра - модель розподілених обчислень, в якій програма ділиться надосить велике число паралельних задач, що складаються з безлічіпідпрограм. На іншому кінці спектру - модель потокових обчислень, вяких кожна операція в програмі може розглядатися як окремийпроцес. Така операція чекає на своїх вхідних даних (операндів), якіповинні бути передані їй іншими процесами. За їх отриманні операціявиконується, і отримане значення передається тим процесам, які в ньомупотребують. У потокових моделях обчислень з великим і середнім рівнемшорсткого, процеси містять велику кількість операцій і виконуються впотокової манері.
4) Багатопроцесорні машини з SIMD-процесорами.

Багато сучасних супер-ЕОМ є багатопроцесорнісистеми, в яких як процесорів використовуються векторні процесориабо процесори типу SIMD. Такі машини відносяться до машин класу MSIMD.

Мови програмування та відповідні компілятори для машин типу
MSIMD звичайно забезпечують мовні конструкції, які дозволяютьпрограмісту описувати "грубозернистий" паралелізм. У межах кожноїзавдання компілятор автоматично векторізует відповідні цикли. Машини типу
MSIMD, як можна собі уявити, дають можливість використовувати кращий зцих двох принципів декомпозиції: векторні операції ( "дрібнозернистий"паралелізм) для тих частин програми, які підходять для цього, і гнучкіможливості MIMD-архітектури для інших частин програми.

Багатопроцесорні системи за роки розвитку обчислювальної технікизазнали ряд етапів свого розвитку. Історично першою стала освоюватитехнологія SIMD. Проте в даний час намітився стійкий інтерес доархітектура MIMD. Цей інтерес головним чином визначається двомафакторами:

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

2.Архітектура MIMD може використовувати всі переваги сучасноїмікропроцесорної технології на основі суворого обліку співвідношеннявартість/продуктивність. Насправді практично всісучасні багатопроцесорні системи будуються на тих же мікропроцесори,які можна знайти в персональних комп'ютерах, робочих станціях іневеликих однопроцесорних серверах.

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

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

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

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

Література

[1] ComputerWorld Росія, # 9, 1995.
[2] К. Вільсон, в сб. "Високошвидкісні обчислення". М. Радио и Связь, 1988,сс.12-48.
[3]. Б. А. Головкін, "Паралельні обчислювальні системи". М.. Наука, 1980,
519 с.
[4] Р. Хокні, К. Джессхоуп, "Паралельні ЕОМ. М.. Радіо та зв'язок, 1986, 390с.
[5] Flynn І., 7., IEEE Trans. Comput., 1972, О.С-21, N9, рр.. 948-960.
[6] Russel К.М., Commun. АСМ, 1978, v. 21, # 1, рр.. 63-72.
[7] Т. Мотоока, С. Томіта, Х. Танака, Т. Сайто, Т. Уехара, "Комп'ютери на
НВІС ", m.l. М. Світ, 1988, 388 с.
[8] М. Кузьмінський, Процесор РА-8000. Відкриті системи, # 5, 1995.
[9] Відкриті системи сьогодні, # 11, 1995.
[10] ComputerWorld Росія, # # 4, 6, 1995.
[11] ComputerWorld Росія, # 8, 1995.
[12] Відкриті системи сьогодні, # 9, 1995.
[13] ComputerWorld Росія, # 2, 1995.
[14] ComputerWorld Росія, # 12, 1995.
[15] В. Шнітман, Системи Exemplar SPP1200. Відкриті системи, # 6, 1995.
[16] М. Борисов, UNIX-кластери. Відкриті системи, # 2, 1995,cc.22-28.
[17] В. Шмідт, Системи IBM SP2. Відкриті системи, # 6, 1995.
[18] М. Дубова, Суперкомп'ютери nCube. Відкриті системи, # 2, 1995, сс.42-
47.
[19] Д. Французів, Тест оцінки продуктивності з?? перкомпьютеров.
Відкриті системи, # 6, 1995.
[20] Д. Волков, Як оцінити робочу станцію. Відкриті системи, # 2, 1994, сc.44-48.
[21] А. Волков, Тести ТРС. СУБД, # 2, 1995, сс. 70-78.