Тема 3. Основні моделі паралельних та розподілених обчислень.

1. Основні типи паралельних програм.

2. Ітеративний паралелізм.

3. Рекурсивний паралелізм.

4. Модель „виробники-споживачі".

5. Паралельна парадигма „клієнт - сервер".

6. Паралельна модель „Взаємодіючі рівні".

1. Основні типи паралельних програм.

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

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

• віконні системи на персональних комп'ютерах або робочих станціях;

• багатопроцесорні операційні системи і системи з розділенням часу;

• системи реального часу, керівники електростанціями, космічними апаратами і т.д.

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

• файлові сервери в мережі;

• системи баз даних для банків, замовлення авіаквитків і т.д.;

• Web-сервери мережі Internet;

• підприємницькі системи, об'єднуючі компоненти виробництва;

• відмовостійкі системи, які продовжують працювати незалежно від збоїв в компонентах.

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

Синхронні паралельні обчислення — третій широкий клас програм. Їх мета — швидко вирішити дане завдання або за той же час вирішити велике завдання. Приклади синхронних обчислень:

• наукові обчислення, які моделюють та імітують такі явища, як глобальний клімат, еволюція сонячної системи або результат дії нових ліків;

• графіка і обробка зображень, включаючи створення спецефектів в кіно;

• крупні комбінаторні або оптимізаційні завдання, наприклад, планування авіаперельотів або економічне моделювання.

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

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

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

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

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

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

Клієнти і сервери — найбільш поширена модель взаємодії в розподілених системах, від локальних мереж до World Wide Web. Клієнтський процес запрошує сервіс і чекає відповіді. Сервер чекає запитів від клієнтів, а потім діє відповідно до цих запитів. Сервер може бути реалізований як одиночний процес, який не може обробляти одночасно декілька клієнтських запитів, або (при необхідності паралельного обслуговування запитів) як багатопотокова програма. Клієнти і сервери представляють собою паралельне програмне узагальнення процедур і їх викликів: сервер виконує роль процедури, а клієнти її викликають. Але якщо код клієнта і код сервера розташовані на різних машинах, звичайний виклик процедури використовувати не можна. Натомість необхідно використовувати віддалений виклик процедури або рандеву.

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