Етапи розробки паралельного алгоритму

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

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

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

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

4. Планування обчислень. На цьому кроці виконується розподіл підзадач між процесорами. Основний критерій вибору способу розміщення підзадач – ефективне використання процесорів з мінімальними затратами часу на обмін даними.

Розглянемо ці етапи детальніше.