Методи та засоби ефективної обробки паралельних задач в комп’ютерних кластерних системах (стр. 20 )

Під задачею Т0 в даній моделі програмування будемо розуміти множину послідовностей дій {t0,i}, які необхідно виконати над деяким набором вхідних даних D:

T0 = ({t0,i } , D). (2.9)

В даному підрозділі для компактності запису будемо опускати вхідні дані D під час запису задач та підзадач.

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

Вихідна задача Т0 може бути розділена на множину під задач:

,

так, що множини послідовностей дій підзадач не перетинаються, а їх об’єднання дає вихідну множину послідовностей для Т0.

Формально: нехай j-та під задача є

,

тоді перетин дій підзадач є пуста множина:

(2.10)

а об’єднання дає вихідну задачу:

(2.11)

Більш строгим варіантом обмеження (2.10) є:

(2.12)

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

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

Визначення 2. Порядком підзадачі називається невід’ємне число, що дорівнює кількості поділів, які були виконання для отримання даної підзадачі з вихідної задачі.

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

Розглянемо підзадачі з точки зору кількості послідовностей дій, які вони містять. Представляють інтерес три варіанти:

-

-

-

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

(2.13)

так як пуста підзадача не має смислу (і не потребує виконання).

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

(2.14)

Як наслідок (2.10), (2.11) та (2.14) можна отримати узагальнені умови для підзадач першого і другого порядку:

Розбиття підзадач може бути продовжено рекурсивно до отримання підзадач порядку z. Критерієм неможливості поділу (а значить, і зупинки рекурсії) є отримання такої множини задач, з якої через умову (2.13) можна отримати тільки такі підзадачі (z + 1)-го порядку, для яких:

Таку задачу назвемо неподільною.

Визначення 3. Неподільна підзадача – підзадача, яка містить тільки одну послідовність дій.

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

2.8.2. Узагальнений оператор поділу

Введемо узагальнений оператор поділу gsplit над підзадачами. Даний оператор викопує поділ підзадачі порядку z на непусту множину підзадач (z + 1)-го порядку:

(2.15)

де – кількість підзадач, на які була розділена вихідна під задача .

Поділ не є завжди єдино можливим. Іноді існують кілька варіантів. Оператор виконує поділ будь-яким способом за умови, що виконуються наступні обмеження:

(2.16)

які є узагальненням (2.10), (2.11) та (2.13) для підзадачі довільного порядку.

2.8.3. Вхідні дані для підзадачі. Поняття проміжку

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

Дуже часто всі неподільні підзадачі вихідної задачі T0 передбачають виконання однієї і тієї ж самої послідовності дій над даними {ri}Î D, де D – повний набір вихідних даних. Звичайно повний набір даних D вихідної задачі є впорядкованим (якщо ні – можна ввести деякий довільний порядок, що не вплине на розв’язок). Тому можна говорити що кожна підзадача приймає в якості вхідних даних деякий проміжок .

Проміжок однозначно задає скінченну зліченну множину даних .

Таким чином задача може бути представлена у вигляді пари з послідовності дій та проміжку, над яким необхідно виконати ці дії, тобто, уточнюючи (2.9), маємо:

(2.17)

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

2.8.4. Оператор обчислення

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

compute (2.18)

Підзадача, до якої було застосовано оператор compute, не може бути розділена на підзадачі.

Визначення 4. Порядком результату називається невід’ємне число, що дорівнює порядку підзадачі, якій відповідає даний результат.

Тепер використовуючи поняття оператора compute можна формально довести еквівалентність двох форм подання задачі.

Теорема 2.1. Дві введені форми подання задачі (2.9) та (2.17) є еквівалентними. 

Доведення. Нехай вихідна задача була задана у першій формі як скінченна множина послідовностей дій . Щоб показати еквівалентність двох форм задання задачі, побудуємо еквівалентну задачу у другій формі. Для цього визначимо проміжок R = [1, N +1), R N для вхідних даних D. Задамо оператор обчислення наступним чином:

Еквівалентна задача у другій формі має вигляд = (compute, R). ■

2.8.5. Оператор поділу проміжків

Визначимо оператор поділу split для проміжків як частковий випадок узагальненого оператору gsplit:

(2.19)

Для задач у формі подання (2.17) узагальнений оператор поділу gsplit можна застосувати наступним чином:

gsplit (compute, R) → {(compute, Ri)} ,

де проміжки {Ri} в правій частині отримані в результаті застосування оператору split:

split R → {Ri}.

Співставимо з кожним проміжком мітки підзадачі, до якої він відноситься:

,

тоді умови (2.16) приймуть вигляд:

(2.20)

Перша умова задає, що початок першого проміжку (z + 1)-го порядку співпадає з початком відповідного проміжку порядку z. Друга умова задає, що кінець останнього проміжку (z + 1)-го порядку співпадає з кінцем відповідного проміжку порядку z. Третя умова задає, що початок попереднього проміжку є кінцем наступного. Четверта умова (2.20) виключає можливість створення пустих проміжків.

Теорема 2.2. В результаті поділу проміжку не вводяться нові елементи даних.

Доведення. На основі перших трьох умов (2.20):