Принципи побудови паралельних обчислювальних систем

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

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

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

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

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

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

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

При застосуванні n*n процесорних елементів можна одержати суму двох матриць порядку n*n за час виконання однієї операції складання (за винятком часу, потрібного на зчитування та запис даних). Цьому рівню притаманні засоби векторизації та так званої паралельності даних. Останнє поняття пов'язане з детальністю розпаралелювання, а саме - з його поширенням на оброблювані дані. Майже кожному елементу даних тут підпорядковується свій процесор, завдяки чому ті дані, що в машині фон Неймана були пасивними. перетворюються на “активні обчислювальні пристрої”.^[2]

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

Одне з рішень даної проблеми пов'язане з реалізацією концепції паралелізму на рівні потоків (Паралелізм завдань - TLP). Якщо запущене на виконання завдання не в змозі завантажити роботою всі функціональні пристрої, то можна дозволити процесору виконувати більш ніж одну задачу, створюючи тим самим другий потік, щоб він завантажив простоюючий пристрій. Тут є аналогія з багатозадачною операційною системою(ОС): щоб процесор не простоював, коли завдання перебувають у стані очікування (наприклад, завершення введення-виведення), ОС перемикається на виконання іншої задачі. Найбільш ефективною на сьогодні стала архітектура з одночасним виконанням потоків (Simultaneous Multi-Threading^[en] - SMT). У такій ситуації на кожному новому такті на виконання в який-небудь виконавчий пристрій може направлятися команда будь-якого потоку - залежно від обчислювального алгоритму.

Розпаралелювання на рівні потоків TLP, на відміну від ILP, управляється програмно. Віртуальна багатопоточність створюється в результаті виділення в одному фізичному процесорі двох або більше логічних процесорів. Класичним прикладом такого підходу стала технологія Hyper-Threading (НТ) компанії Intel. Внаслідок того, що протягом такту, як правило, не всі виконавчі модулі процесора задіяні, їх можна завантажити паралельним потоком завдань. Зрозуміло, що вдвічі продуктивність не збільшиться, оскільки паралельні потоки використовують загальні пам'ять, кеш і т.д. (до того ж виникають втрати через синхронізації і розпаралелювання інструкцій), але вона в цілому зростає на 35-50%. Мінусом використання технології TLP є виникнення конфліктів, коли одному потоку потрібні результати виконання іншого договору, що призводить до очікування і зростанню кількості тактів, необхідних для виконання інструкцій.

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

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

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

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

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

При організації паралельних обчислень можливо кілька режимів виконання незалежних частин програми

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

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

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

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

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

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

Є коло обчислювальних задач, що вимагає більших обчислювальних ресурсів. Для задач необхідно:

• більша швидкодія;

• більший об’єм оперативної пам’яті

• велика кількість інформації, що передається;

• обробка і зберігання великого об’єму інформації.

При наявності хоча б однієї з наведених вимог використання паралельної обробки доцільне.

1. Складні, багатовимірні задачі, які необхідно розв’язати протягом досить обмеженого часу, вимагають забезпечення великої швидкодії, наприклад - задачі прогнозу погоди. Область розв’язку (атмосфера) розбивається на окремі просторові зони, причому для розв’язку часових змін обчислень в кожній зоні повторюється багато разів. Якщо об’єм зони рівний 1 км³, то для моделювання 10 км шару атмосфери необхідно 5х10⁸ таких зон. Припустимо, що обчислення в кожній зоні вимагає 200 операцій з плаваючою крапкою, тоді за один часовий крок необхідно виконати 10¹¹ операцій з плаваючою крапкою. Для того, щоб провести розрахунок прогнозу погоди з передбачуванністю 10 днів з 10-ти хвилинним кроком в часу, Комп'ютер продуктивністю 100 Mflops (10⁸ операцій з плаваючою крапкою за секунду) необхідно 10⁷ секунд чи понад 100 днів. Для того, щоб провести розрахунок за 10 хв, необхідна ЕОМ продуктивністю 1.7 Tflops (1.7X10¹² операцій з плаваючою крапкою за секунду).
2. До категорії задач, що вимагають великого об’єму оперативної пам’яті, відносяться, наприклад, задачі гідро- і газодинаміки по розрахунку течій складної просторово-часової структури з врахуванням різних фізичних і хімічних процесів. Такі задачі є, як правило, багатвимірними, і розрахунок по кожному з напрямків хоча б для декількох точок вимагає оперативної пам’яті понад 10 Гбайт. В квантовій хімії неемпіричні розрахунки електронної структури молекул вимагають обчислювальних затрат, пропорційних N⁴ чи N⁵, де N умовно характеризує число молекул. Тому молекулярні системи вимужено досліджуються спрощено, через нестачу обчислювальних ресурсів.
3. Вимога забезпечення великої кількості інформації, що передається характерна для задач гідро- і газодинаміки з змінюючими граничними умовами, коли обчислювальний алгоритм постійно вимагає підведення нової інформації; і задач економічної оптимізації, що описують поведінку системи, яка занурена в середовище з неперервно змінюючими властивостями, від яких залежить стан системи.