Анотація: Основними етапами розробки паралельних програм є: декомпозиція, виявлення інформаційних залежностей між подзадачами, масштабування подзадач і балансування навантаження для кожного процесора.
декомпозиція
Під декомпозицією розуміється розбиття завдання на відносно незалежні частини (підзадачі). Декомпозиція задачі може бути проведена кількома способами: за завданнями, за даними, по інформаційних потоків.
Декомпозиція за завданнями (функціональна декомпозиція) передбачає присвоєння різним потокам різних функцій. Наприклад, додаток виконує правку документа включає наступні функції: перевірка орфографії CheckSpelling. перевірка пунктуації CheckPuncto. форматування тексту у відповідність з вибраними стилями Format. підрахунок статистики по документу CalcStat. збереження змін у файлі SaveChanges і відправка документа по електронній пошті SendDoc.
Функціональна декомпозиція розбиває роботу програми на підзадачі таким чином, щоб кожна подзадача була пов'язана з окремою функцією. Але не всі операції можуть виконуватися паралельно. Наприклад, збереження документа і відправка документа виконуються тільки після завершення всіх попередніх етапів. Форматування і збір статистики можуть виконуватися паралельно, але тільки після завершення перевірки орфографії і пунктуації.
Декомпозиція за інформаційним потокам виділяє підзадачі, що працюють з одним типом даних. У розглянутому прикладі можна виділити такі підзадачі:
- Робота з чорновим документом (орфографія і пунктуація):
- Робота з виправленим документом (форматування і збір статистики);
- Робота з готовим документом (збереження і відправка);
При декомпозиції за даними кожна подзадача працює зі своїм фрагментом даних, виконуючи весь перелік дій. У розглянутому прикладі декомпозиція за даними може застосовуватися до завдань, що допускають роботу з фрагментом документа. Таким чином, функції CheckSpelling. CheckPuncto. CalcStat. Format об'єднуються в одну підзадачу, але створюється кілька примірників цієї підзадачі, які паралельно працюють з різними фрагментами документа. Функції SaveChanges і SendDoc становлять окремі підзадачі, так як не можуть працювати з частиною документа.
Декомпозиція за даними
При декомпозиції за даними кожна подзадача виконує одні й ті ж дії, але з різними даними. У багатьох задачах, паралельних за даними, існує кілька способів поділу даних. Наприклад, завдання матричного множення допускає поділ по рядках - кожен потік обробляє одну або кілька рядків матриці, за стовпцями - кожен потік обробляє один або декілька стовпців, а також по блокам заданого розміру.
Два основних принципи поділу даних між подзадачами - статичний і динамічний. При статичної декомпозиції фрагменти даних призначаються потокам до початку обробки і, як правило, містять однакове число елементів для кожного потоку. Наприклад, поділ масиву елементів може здійснюватися по рівним діапазонами індексу між потоками (range partition).
Основною перевагою статичної поділу є незалежність роботи потоків (немає проблеми гонки даних) і, як наслідок, немає необхідності в засобах синхронізації для доступу до елементів. Ефективність статичної декомпозиції знижується при різній обчислювальної складності обробки елементів даних. Наприклад, обчислювальна навантаження обробки i-елементів може залежати від індексу елемента.
Поділ за діапазоном призводить до незбалансованості навантаження різних потоків. Незбалансованість навантаження знижує ефективність розпаралелювання. У деяких випадках декомпозиція може бути поліпшена і при статичному розбитті, коли заздалегідь відомо які елементи мають більшу обчислювальної трудомісткістю, а які меншою. Наприклад, в разі залежності обчислювальної трудомісткості від індексу елемента, застосування кругової декомпозиції вирівнює завантаженість потоків. Перший потік обробляє всі парні елементи, другий потік обробляє всі непарні.
У загальному випадку, коли обчислювальна складність обробки елементів заздалегідь не відома, збалансованість завантаження потоків забезпечує динамічна декомпозиція.
/ При динамічної декомпозиції кожен потік. бере участь в обробці, звертається за блоком даних (порцією). Після обробки блоку даних потік звертається за наступною порцією. Динамічна декомпозиція вимагає синхронізації доступу потоків до структури даних. Розмір блоку визначає частоту звернень потоків до структури. Деякі алгоритми динамічної декомпозиції збільшують розмір блоку в процесі обробки. Якщо потік швидко обробляє елементи, то розмір блоку для нього збільшується.
масштабування подзадач
Властивість масштабованості полягає в ефективному використанні всіх наявних обчислювальних ресурсів. Паралельне застосування повинне бути готове до того, що завтра воно буде запускатися на системі з великими обчислювальними можливостями. Властивість масштабованості додатки тісно пов'язане з обраним алгоритмом рішення задачі. Один алгоритм дуже добре распараллеливается, але тільки на дві підзадачі, інший алгоритм дозволяє виділити довільне число подзадач.
Обов'язковою умовою масштабованості додатки є можливість параметризації алгоритму в залежності від числа процесорів в системі і в залежності від поточної завантаженості обчислювальної системи. Така параметризація дозволяє змінювати число виділених підзадач при конкретних умовах виконання алгоритму. Сучасні платформи паралельного програмування надають кошти для автоматичного балансування навантаження (пул потоків).
Проблема гонки даних
Проблема гонки даних виникає при наступних умовах:
- Кілька потоків працюють з ресурсом.
- Кінцевий результат залежить від черговості виконання командних послідовностей різних потоків.
Для ілюстрації проблеми гонки даних розглянемо наступний фрагмент. Два потоку виводять на екран значення загальної змінної Msg.
Мінлива Msg є спільною - зміна змінної в одному потоці будуть видні в іншому потоці. При паралельній роботі потоків висновок визначається конкретної послідовністю виконання операторів.
Якщо оператори першого потоку виконуються до операторів другого потоку, тобто при послідовності (1) - (2) - (3) - (4), то ми отримуємо:
Якщо ж в виконання операторів одного потоку втрутяться оператори іншого потоку, наприклад, при послідовності (1) - (3) - (2) - (4), то отримаємо наступне:
Проблема гонки даних виникає не тільки при виконанні декількох операторів, але і при виконанні одного оператора. Розглянемо наступний випадок. Обидва потоки виконують один оператор над загальною змінної x типу int:
Даний оператор передбачає виконання таких дій:
При виконанні командних послідовностей одного потоку на одному виконавчому пристрої в роботу може втрутитися інший потік. Кінцевий результат залежить від черговості виконання командних послідовностей. Якщо потоки здійснюють підсумовування послідовно, то отримуємо кінцевий результат: 10. Якщо потоки здійснюють підсумовування одночасно, то раннє зміна буде затерто пізнім:
Ще однією "пасткою" в багатопотокової обробці є робота з динамічними структурами даних (списки, словники). Додавання і видалення елементів в динамічні структури даних здійснюється за допомогою одного методу:
Реалізація методів включає кілька дій. Наприклад, при додаванні елемента в список необхідно записати елемент за поточним індексом (вказівником) і зрушити індекс на наступну позицію. Для коректного здійснення додавання елемента одним потоком необхідно, щоб інші потоки дочекалися завершення маніпуляцій зі списком.
Для вирішення проблеми гонки даних необхідно забезпечити взаємно винятковий доступ до тих командним послідовностям, в яких здійснюється робота з ресурсом. Взаємна винятковість означає, що в кожен момент часу з ресурсом працює тільки один потік. інші потоки блокуються в очікуванні завершення роботи першого потоку. Фрагмент коду, до якого повинен бути забезпечений взаємно винятковий доступ. називається критичною секцією.
Проблема гонки даних не завжди виникає при роботі із загальною змінної. Наприклад, в наступному фрагменті два потоку перед завершенням здійснюють зміна розділяється змінної, а третій потік читає це значення.
У цьому прикладі третій потік в циклі "очікує" завершення хоча б одного потоку. Проблеми гонки даних не виникає, незважаючи на роботу трьох потоків із загальною змінної. Порядок виконання потоків не впливає на кінцевий результат. Зміни, що вносяться потоками, не суперечать один одному.