Обчислення в мпд

Програма в МПД може бути представлена як орієнтований граф. Дуги в ньому бувають двох типів:

1. неперервні (такі дуги переносять числову та строкову інформацію) – зв’язки даних

2. перервані (переносять булеві змінні) – зв’язки керування

Вершинами такого графу є актори, які бувають 5 типів:

• розмножувачі

• блоки виконання операцій

• блоки прийняття рішень

• змішувачі

• клапани або вентилі

Конфігурація схеми потоку даних

Обчислення графу потоку операндів описується послідовністю змін стану графу. Кожен стан відображає потік операндів програми з ознаками і відповідними значеннями, що розміщенні на дугах графа програми [6]. Обчислення переходить від одного стану до іншого за рахунок спрацьовування вершин обох типів, яке стає можливим після виконання попереднього кроку.

Конфігурацією схеми потоку даних для інтерпретації з областю визначення D є:

1. Зіставлення значення з D або символу null кожній дузі даних схеми S.

2. Зіставлення одного з символів {true, false, null} кожній управляючій дузі схеми.

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

Обчислення С по схемі S є послідовність конфігурацій х₀, x₁, ..., x_n, …, задовільняюча властивостям:

1. х₀ є початкова конфігурація.

2. x_i+1 виходить з x_i, - згідно одному з правил спрацьовування, визначених на мал.4, де над рискою виписана умова застосованості правила, а під — одержана в результаті спрацьовування нова конфігурація. Будь-яка вершина, готова до спрацьовування в конфігурації x_i, може бути вибрана для запалення. Оскільки одночасно готові всі вершини, для яких обчислені вхідні запалення, і оскільки всі готові вершини можуть запалитися, паралель дії є внутрішнім аспектом схеми потоку даних. Більш того, ці схеми є «максимально паралельними» конструкціями, так - послідовність виконання функцій і предикатів визначається залежністю за даними.

9. Декомпозиція задач за вхідними даними.

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

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

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

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

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

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

| 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₂₂|

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

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

Приклад: визначення мінімуму або максимуму з набору чисел