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

або іншими словами: всі нові проміжки належать вихідному проміжку. ■

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

Доведення. Знайдемо об’єднання всіх нових проміжків:

Доведемо за індукцією, що це об’єднання дорівнює вихідному проміжку.

База індукції. Якщо , то відповідно до першої та другої умови:

і тому жоден елемент даних не було втрачено, що і треба було довести. Інакше , тоді:

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

Отже, перші два нові проміжки відповідають початку вихідного проміжку.

Крок індукції. Нехай ми довели, що перші p проміжків відповідають початку вихідного проміжку. Доведемо, що p+1 проміжок також відповідає початку вихідного проміжку:

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

■

і тому жоден елемент даних не було втрачено, що і треба було довести.

2.8.6. Поняття шляху поділу підзадачі

Повторюване застосування оператора поділу gsplit до підзадач, які представлені як у вигляді послідовностей дій (2.9), так і у вигляді проміжків (2.17), приводить до формування у кожної підзадачі деякої послідовності індексів Г: де довжина послідовності |Г| визначає порядок підзадачі, а кожен елемент є номером підзадачі даного порядку, з якого шляхом поділу була отримана дана.

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

.

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

На основі формалізації поняття шляху поділу можна виявити додаткові властивості оператору поділу на основі (2.16), а саме:

,

причому z = y + N – n. Іншими словами, підзадачі, які отримані в результаті поділу деякої задачі, мають префікс в шляху поділу, що дорівнює шляху поділу вихідної задачі.

Аналогічно:

.

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

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

2.8.7. Оператор об’єднання результатів

Введемо оператор об’єднання merge. Цей оператор виконує об’єднання результатів обчислень підзадач одного порядку:

,

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

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

.

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

.

2.8.8. Визначення завдання

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

áR0, compute, gsplit, split, mergeñ, (2.21)

де R0 – проміжок вихідних даних, compute – оператор обчислення, gsplit – оператор поділу задачі, split – оператор поділу проміжку, merge – оператор об’єднання результатів. Ці оператори працюють над групами:

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

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

В моделі виcокорівневої передачі повідомлень визначені обмеження, які мають задовольняти оператори обчислення, поділу та об’єднання. Ці оператори визначаються користувачем, так як саме користувач задає спосіб обчислення підзадач, та типи вхідних та вихідних даних. Але точний порядок виконання цих операторів залишається не визначеним. З точки зору моделі ці оператори можуть бути застосовані у будь-якому порядку за умови що відповідні обмеження задовольняються. Але надання програмісту контролю над цим порядком виконання призводить до тих самих проблем, які високорівнева модель мала вирішити, а саме: окрім безпосередньо задачі, програміст буде працювати з особливостями паралельних ЕОМ.

Тому порядок виконання операторів поділу, обчислення та об’єднання має визначатись реалізацією даної моделі програмування. Це має наступні переваги перед наданням програмісту контролю над порядком виконання цих операторів:

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

– Програміст звільняється від роботи з особливостями паралельних ЕОМ, а тільки описує задачу в абстракціях моделі. Це значно спрощує етап програмування.

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

Загальна схема динамічного балансування навантаження є наступною:

– Одразу після запуску задачі на виконання існує тільки одна підзадача нульового порядку Т0. Якщо зразу застосувати оператор обчислення compute до Т0, всі обчислення будуть виконані послідовно. Тому спочатку виконується попередній поділ задачі за допомогою операторів gsplit та split. Нижче описані декілька підходів до вибору кількості та порядку поділу.

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

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

Критерієм зупинки основного циклу обчислень є отримання результату нульового порядку. Цей результат є результатом вихідної задачі нульового порядку Т0.

2.10. Способи організації попереднього поділу задачі

2.10.1. Загальні зауваження

Одразу після запуску задачі на виконання існує тільки одна підзадача нульового порядку Т0, що була створена відповідно до опису з завдання (2.21). З точки зору умов моделі програмування, до цієї задачі дозволяється зразу за-стосувати оператор обчислення compute. Але в цьому випадку всі обчислення будуть виконані послідовно. Тому для виконання обчислень в паралельному режимі необхідно виконати попередній поділ задачі за допомогою операторів поділу gsplit та split.

Для досягнення цієї мети можна використати наступні способи застосування операторів поділу:

– поділ на підзадачі однакового порядку – підзадача нульового порядку розбивається на підзадачі k-гo порядку (рис. 2.8);

– поділ на підзадачі різного порядку – підзадача нульового порядку розбивається на підзадачі першого порядку, частина з яких розбивається на підзадачі другого порядку, частина з яких розбивається на підзадачі третього, і так далі до отримання неподільних підзадач (рис. 2.9).