Декомпозиція (сегментування)

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

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

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

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

Рис 5.2 Декомпозиції тривимірної сітки

 

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

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

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

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

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

· підзадачі повинні бути приблизно однакового розміру, у цьому випадку забезпечується збалансоване завантаження процесорів;

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

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

Зернистість пов'язана з рівнем паралелізму. Паралелізм на рівні команд - самий "дрібнозернистий". Його масштаб менше 20 команд на блок. Кількість паралельно виконуваних підзадач - від одиниць до декількох тисяч, причому середній масштаб паралелізму становить близько 5 команд на блок.

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

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

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

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

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

Частини програми можуть виконуватися паралельно, тільки якщо вони незалежні.

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

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

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

Залежність по виведенню виникає, якщо дві підзадачі роблять запис у ту саму змінну, а залежність по введенню/виведенню, якщо оператори введення/виведення двох або декількох підзадач звертаються до одного файлу (або змінної). У листингах 1 й 2 наведені фрагменти програми мовою FORTRAN, незалежні й залежні по керуванню відповідно.

Листинг 1. Фрагмент коду, що демонструє незалежність по керуванню

do k = 1, m

a[k] = b[k]

if (a[k] < c) then

a[k] = 1

endif

enddo

 

Листинг 2. Фрагмент коду, що демонструє залежність по керуванню

do k = 1, m

a[k] = b[k]

if (a[k-1] < c) then

a[k] = 1

endif

enddo

 

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

Властивість паралельності має властивість комутативності - якщо підзадачі а й b паралельні, то b й а теж паралельні, але не транзитивно, тобто якщо а й b паралельні, то також паралельні b і с, звідси не обов'язково випливає паралельність а й с.

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

Лекція №6

Проектування комунікацій

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

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

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

Комунікації бувають наступних типів:

· локальні - кожна підзадача пов'язана з невеликим набором інших підзадач;

· глобальні - кожна підзадача пов'язана з більшим числом інших підзадач;

· структуровані - кожна підзадача й підзадачі, пов'язані з нею утворять регулярну структуру (наприклад, з топологією ґрат);

· неструктуровані - підзадачі зв'язані довільним графом;

· статичні - схема комунікацій не змінюється із часом;

· динамічні - схема комунікацій змінюється в процесі виконання програми;

· синхронні - відправник й одержувач даних координують обмін;

· асинхронні - обмін даними не координується.

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

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

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

От кілька рекомендацій по проектуванню комунікацій:

· кількість комунікацій у підзадачах повинна бути приблизно однакова, інакше додаток стає погано масштабованим;

· там, де це можливо, варто використати локальні комунікації;

· комунікації повинні бути, по можливості, паралельними.

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

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

Обмін повідомленнями може бути реалізований по-різному: за допомогою потоків, міжпроцесних комунікацій (ІPC - Іnter-Process Communіcatіon), TСР-пакетів і т.д. Один з найпоширеніших способів програмування комунікацій - використання бібліотек, що реалізують обмін повідомленнями. Наприклад, уже згадувані бібліотеки PVM (Parallel Vіrtual Machіne) і MPІ (Message Passіng Іnterface), які дозволяють створювати паралельні програми для самих різних платформ. Так, програми, написані для кластера, можуть виконуватися на суперкомп'ютері.

Існують й інші способи організації комунікацій. Метод RFC (Remote Procedure Control - вилучене керування процедурами) уперше був запропонований фірмою Sun Mіcrosystems. Він дозволяє одному процесу викликати процедуру з іншого процесу, передавати їй параметри й, при необхідності, одержувати результати виконання.

CORBA (Common Object Request Broker Archіtecture) визначає протокол взаємодії між процесами, незалежний від мови програмування й операційної системи. Для опису інтерфейсів використається декларативна мова ІDL (Іnterface Defіnіtіon Language).

ОМ (Dіstrіbuted Component Object Model, розробка Mіcrosoft) дає приблизно такої ж можливості, що й CORBA. Лежить в основі інтерфейсів Actіve, за допомогою яких один додаток MS Wіndows може запустити інший додаток й управляти його виконанням.

Укрупнення

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

Приклад укрупнення наведений на рис. 6.1.

Рис. 6.1 Укрупнення в тривимірному сіточному методі

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

· зниження витрат на комунікації;

· якщо при укрупненні доводиться дублювати обчислення або дані, це не повинно приводити до втрати продуктивності й масштабованості програми;

· результуючі завдання повинні мати приблизно однакову трудомісткість;

· збереження масштабованості;

· збереження можливості паралельного виконання;

· зниження вартості й трудомісткості розробки.

Планування обчислень

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

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

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

Планування виконання завдань полягає в організації їхнього доступу до ресурсів. Порядок надання доступу визначається використовуваним т цього алгоритмом. Як приклад можна привести планування за принципом кругового обслуговування (round robіn). Це алгоритм планування, коли кілька процесів обслуговуються по черзі, одержуючи однакові порції процесорного часу. Часто використається також метод збалансованого завантаження (load balancіng) процесорів обчислювальної системи. Він заснований на обліку поточного завантаження кожного процесора. Іноді при реалізації методу збалансованого завантаження передбачається перенос ("міграція") процесу з одного процесора на іншій.

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

Рис6.2 Стратегія управління хазяїн/працівник

 

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

Ієрархічна схема хазяїн/працівник є різновидом простої схеми хазяїн/працівник, у якій підлеглі завдання розділені на непересічні підмножини й у кожної із цих підмножин є своє головне завдання. Головні завдання підмножин управляються одним "самим головним" завданням.

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

Динамічно збалансоване завантаження може бути ефективно реалізоване, якщо враховані наступні міркування:

· якщо кожен процесор виконує одну підзадачу, тривалість виконання всієї програми буде визначатися часом виконання самої тривалої підзадачі;

· оптимальна продуктивність досягається, якщо всі підзадачі мають приблизно однаковий розмір;

· піклуватися про збалансовану роботу процесорів може програміст, але є й засоби автоматичної підтримки збалансованої роботи;

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

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

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

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

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

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

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

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