Основні етапи проектування паралельних та розподілених алгоритмів

Декомпозиція

Декомпозиція — це процес розбиття завдання і його рішення на частини. Іноді частини групуються в логічні області (тобто пошук, сортування, обчислення, введення і виведення даних і т.д.). У інших випадках частини групуються по логічних ресурсах (тобто файл, зв'язок, принтер, база даних і т.д.). Декомпозиція програмного рішення часто зводиться до декомпозиції робіт (work breakdown structure — WBS). Декомпозиція робіт визначає, що повинні робити різні частини ПЗ. Одна з основних проблем паралельного програмування — ідентифікація природної декомпозиції робіт для програмного вирішення. Не існує простого і однозначного підходу до ідентифікації WBS. Розробка ПЗ — це процес перекладу принципів, ідей, шаблонів, правил, алгоритмів або формул в набір інструкцій, які виконуються, і даних, які обробляються комп'ютером. Це, в основному, і складає процес моделювання. Програмні моделі — це відтворення у вигляді ПЗ деякого реального завдання, процесу або ідеалу. Мета моделі — проімітувати або скопіювати поведінку і характеристики деякої реальної суті в конкретній області. Процес моделювання розкриває природну декомпозицію робіт програмного рішення. Чим краще модель зрозуміла і розроблена, тим більше природною буде декомпозиція робіт. Наша мета — виявити паралелізм і розподіл за допомогою моделювання. Якщо природний паралелізм не спостерігається, не варто його нав'язувати насильно. На питання, як розбити програму на паралельно виконувані частини, необхідно знайти відповідь під час проектування, і правильність цієї відповіді повинна стати очевидною в моделі рішення. Якщо модель завдання і рішення не припускає паралелізму і розподілу, слід спробувати знайти послідовне рішення. Якщо послідовне рішення виявляється невдалим, ця невдача може дати ключ до потрібного паралельного рішення.

Зв'язок

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

 

Синхронізація

Декомпозиція робіт, як вже було відмічено вище, визначає, що повинні робити різні частини ПЗ. Коли безліч компонентів ПЗ працюють в рамках одного завдання, їх функціонування необхідно координувати. Певний компонент повинен "уміти" визначити, коли досягається рішення всієї задачі. Необхідно також скоординувати порядок виконання компонентів. При цьому виникає безліч питань. Чи всі частини ПЗ повинні одночасно приступати до роботи або тільки деякі, а інші можуть знаходитися поки в стані очікування? Яким двом (або більше) компонентам необхідний доступ до одного і того ж ресурсу? Хто має право одержати його першим? Якщо деякі частини ПЗ завершать свою роботу набагато раніше за інших, то чи потрібно їм "доручати" нову роботу? Хто повинен давати нову роботу в таких випадках? ДЗС (декомпозиція, зв'язок і синхронізація) — це той мінімум питань, які необхідно вирішити, приступаючи до паралельного або розподіленого програмування. Крім суті проблем, складових ДЗС, важливо також розглянути їх прив'язку. Існує декілька рівнів паралелізму в розробці програм, і в кожному з них ДЗС-складові застосовуються по-різному.

8.1. Декомпозиція Декомпозиція — це процес розбиття завдання і його рішення на частини. Іноді частини групуються в логічні області (тобто пошук, сортування, обчислення, введення і виведення даних і т.д.). У інших випадках частини групуються по логічних ресурсах (тобто файл, зв'язок, принтер, база даних і т.д.). Декомпозиція програмного рішення часто зводиться до декомпозиції робіт (work breakdown structure — WBS). Декомпозиція робіт визначає, що повинні робити різні частини ПЗ. Одна з основних проблем паралельного програмування — ідентифікація природної декомпозиції робіт для програмного вирішення. Не існує простого і однозначного підходу до ідентифікації WBS. Розробка ПЗ — це процес перекладу принципів, ідей, шаблонів, правил, алгоритмів або формул в набір інструкцій, які виконуються, і даних, які обробляються комп'ютером. Це, в основному, і складає процес моделювання. Програмні моделі — це відтворення у вигляді ПЗ деякого реального завдання, процесу або ідеалу. Мета моделі — проімітувати або скопіювати поведінку і характеристики деякої реальної суті в конкретній області. Процес моделювання розкриває природну декомпозицію робіт програмного рішення. Чим краще модель зрозуміла і розроблена, тим більше природною буде декомпозиція робіт. Наша мета — виявити паралелізм і розподіл за допомогою моделювання. Якщо природний паралелізм не спостерігається, не варто його нав'язувати насильно. На питання, як розбити програму на паралельно виконувані частини, необхідно знайти відповідь під час проектування, і правильність цієї відповіді повинна стати очевидною в моделі рішення. Якщо модель завдання і рішення не припускає паралелізму і розподілу, слід спробувати знайти послідовне рішення. Якщо послідовне рішення виявляється невдалим, ця невдача може дати ключ до потрібного паралельного рішення. 8.2. Зв'язок Після декомпозиції програмного рішення на ряд паралельно виконуваних частин звичайно виникає питання про зв'язок цих частин між собою. Як же реалізувати зв'язок, якщо ці частини рознесли по різних процесах або різних комп'ютерах? Чи повинні різні частини ПЗ спільно використовувати загальну область пам'яті? Яким чином одна частина ПЗ дізнається про те, що інша справилася з своїм завданням? Яка частина повинна першою приступити до роботи? Звідки один компонент дізнається про відмову іншого компоненту? На ці і багато інші питання необхідно знайти відповіді при проектуванні паралельних і розподілених систем. Якщо окремим частинам ПЗ не потрібно зв'язуватися між собою, значить, вони насправді не утворюють єдиної програми. 8.3. Синхронізація Декомпозиція робіт, як вже було відмічено вище, визначає, що повинні робити різні частини ПЗ. Коли безліч компонентів ПЗ працюють в рамках одного завдання, їх функціонування необхідно координувати. Певний компонент повинен "уміти" визначити, коли досягається рішення всієї задачі. Необхідно також скоординувати порядок виконання компонентів. При цьому виникає безліч питань. Чи всі частини ПЗ повинні одночасно приступати до роботи або тільки деякі, а інші можуть знаходитися поки в стані очікування? Яким двом (або більше) компонентам необхідний доступ до одного і того ж ресурсу? Хто має право одержати його першим? Якщо деякі частини ПЗ завершать свою роботу набагато раніше за інших, то чи потрібно їм "доручати" нову роботу? Хто повинен давати нову роботу в таких випадках? ДЗС (декомпозиція, зв'язок і синхронізація) — це той мінімум питань, які необхідно вирішити, приступаючи до паралельного або розподіленого програмування. Крім суті проблем, складових ДЗС, важливо також розглянути їх прив'язку. Існує декілька рівнів паралелізму в розробці програм, і в кожному з них ДЗС-складові застосовуються по-різному.