12. Декомпозиція задач за проміжними даними.

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

Застосовується до даних, які оперують великими масивами чисел. Проводиться в два етапи:

3. розділення даних

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

Секціонування здійснюється різними способами, буває різних типів:

• за вихідними даними – такий тип розподілу задач можливий, коли кожний вихідний елемент може бути обчислений як функція входу не залежно від решти вихідних елементів. Приклад матричного множення

| A₁₁ A₁₂| * | B₁₁ B₁₂| = | C₁₁ C₁₂|

| A₂₁ A₂₂| * | B₂₁ B₂₂| | C₁₁ C₁₂|

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

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

| A_11|| * | B₁₁ B₁₂|

| A₂₁|

… = | C₁₁ C₁₂|

| A₁₂| * | B₂₁ B₂₂| | C₁₁ C₁₂|

|A₂₂|

Правило власника обчислень – кожне секціонування має виконувати обчислення над всіма даними, якими володіє.

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

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

Реструктуризація первинного алгоритму дала змогу отримати вищий ступінь паралелізму програми, але це прискорення було досягнуто за рахунок використання додаткового об’єму пам’яті.

13. Граф машин потоків даних (мпд) і його основні елементи.

Програма машини ПД може бути представлена як дводольний орієнтований граф, вузлами якого є актори, виконувані над даними, а орієнтовані дуги вказують шлях, по яким між акторами перетікають токени [3].

Основні елементи графу ПД

Рис.1. Типи вершин і ліній зв’язку.

Існує два види інформації: числова і керуюча. Лінії зв’язку - це аналог понять „змінна”, „пам’ять”[4]. Дуги є каналами, по яким пересилаються потоки значень між вершинами. Множина дуг складається із дуг даних і керуючих дуг, в залежності від типу вершин, з яких вони виходять. Отже, при графічному представленні програми на мові потоків даних використовується два типи ліній зв’язку: даних і керування (Рис.1). Значення, що переносяться дугами керування – булеві, а ті, які переносяться дугами даних – цілочисельні, дійсні або символьні.

а) б)

Рис.2. Розмножувачі

Існує п’ять типів акторів: розмножувачі (Рис.2); оператори або блоки виконання операцій (Рис.3а); які включають в себе вершини, що реалізують логічні функції (Рис.3д); розпізнавачі або блоки прийняття рішення (Рис.3б); клапани або вентилі типу „true” і „false” (Рис.3в); вершини злиття або змішувачі (Рис.3г).

д)

Рис.3. Типи акторів

Розглянемо детально принцип роботи основних акторів:

Рис. 4. Принцип роботи основних акторів