10.3.4 Декомпозиція даних

На відміну від функціональної декомпозиції, коли між процесорами розподіляються різні завдання, декомпозиція даних передбачає виконання на кожному процесорі однієї і тієї ж задачі, але над різними наборами даних. Частини даних спочатку розподілені між процесорами, які обробляють їх, після чого результати підсумовуються деяким чином в одному місці (зазвичай на консолі кластера). Дані повинні бути розподілені так, щоб обсяг роботи для кожного процесора був приблизно однаковий, тобто декомпозиція повинна бути збалансованою. У разі дисбалансу ефективність роботи кластеру може бути знижена.

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

 

10.3.5 Regular Domain Decomposition

Дуже багато завдань базуються на обробці великих масивів даних, структурованих в регулярну матрицю. Як один з числених прикладів можна згадати чисельне моделювання газодинамічних процесів. У тому випадку, коли оброблювана решітка даних може бути розбита на регулярні (не перетинаються) програми підрешіток (областей), завдання може бути розподілене між програмованим кластером та вирішена в програмованому режимі. Це дозволить або скоротити час розв'язання задачі, або поставити задачу для більш суттєвих програм даних (наприклад зробити різницеву сітку більш дрібною).

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

 

Рисунок 10.6 – Регулярна декомпозиція вихідної решітки

 

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

 

10.3.6 Сітка процесів

Метод регулярної декомпозиції складається в розбитті вихідної великої сітки даних на непересічні регулярні області і розподілі цих подсіток між процесорами, де ці частини даних можуть бути паралельно оброблені. Іншими словами глобальний набір даних декомпозується на секції і кожна секція передається під контроль окремого процесу так, як це показано на наступному рисунку 10.7.

 

 

Рисунок 10.7 – Глобальний набір даних декомпозиції

 

Перед тим, як сітка даних буде розприділена між процесами, самі процеси повинні бути організовані в логічну структуру, відповідну структуру даних. Іншими словами процеси не є копіями однієї і тієї ж програми, хоча і можуть виконувати однакові по суті дії. Кожен процес має, по-перше, враховувати якого типу дані він обробляє. У тому ж прикладі з газодинаміка процеси можна розділити на ті, які обчислюють щільність, швидкість або гравітацію. По-друге, процес повинен враховувати звідки беруться дані, з центру глобальної сітки або з її краю. Набір даних, розподіленого процесу надалі будемо називати блоком даних цього процесу.