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

Відповідно до методу лівих прямокутників, апроксимація визначеного інтегралу знаходиться наступним чином. Проміжок інтегрування [a; b] розбивають точками a = x0, x1,... , b = xn-1 на n рівних частин довжиною Δx = кожна. На кожному відрізку будується прямокутник, верхній лівий кут якого лежить на графіку функції. Наближене значення інтегралу дорівнює сумі площ прямокутників:

. (2.7)

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

, (2.8)

де M – максимальне значення а проміжку [a; b].

Визначимо найменшу кількість відрізків інтегрування n, яка знайти апроксимацію визначеного інтегралу з абсолютною похибкою, що не перевищує ε. З формули (2.8):

.

Отже, кількість кроків інтегрування залежить від значень та властиво максимального значення на проміжку [a; b].

Послідовна реалізація даного алгоритму відповідно до формули (2.7) є тривіальною; послідовна реалізація наведена на рис. 2.4

Вхідні дані:
Вихідні дані:
1 begin
2	;
3	;
4	;
5 end

________________________________________________________________

Рис. 2.4. Послідовна реалізація алгоритму чисельного інтегрування

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

Вхідні дані: Вихідні дані: Спільні змінні:
1 begin
2	;
3	;
4	;
5	Виконати незалежні під задачі Ti;
6	;
7	end
8 Підзадача і begin
9	;
10 end

__________________________________________________________________

Рис. 2.5. Паралельна реалізація алгоритму чисельного інтегрування

Аналіз математичних формул, що лежать в основі даного алгоритму, та використання нерівномірної одномірної сітки, дозволяє побудувати іншу реалізацію. Розіб’ємо проміжок інтегрування на Р рівних частин довжиною кожна. На кожному з отриманих проміжків будемо обчислювати інтеграл за формулою (2.7), але з абсолютною похибкою, що не перевищує ; таким чином сумарна абсолютна похибка не перевищує заданий ε.

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

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

Вхідні дані: Вихідні дані: Спільні змінні:
1 begin
2	;
3	виконати незалежні під задачі Ti;
4	;
5 end
6 Підзадача і begin
7	r ← li;
8	s ← l(i+1);
9	;
10	;
11	;
12 end

______________________________________________________________

Рис. 2.6. Паралельна реалізація алгоритму чисельного інтегрування, що адаптується до швидкості зростання підінтегральної функції

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

2.4. Динамічне балансування навантаження при розв’язанні задачі

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

Тому для виконання оптимізації (2.6) пропонується застосувати динамічне балансування навантаження між ресурсами, що виділені для задачі. Обрано саме динамічне балансування, так як воно не потребує апріорних оцінок часу виконання окремих підзадач.

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

– коли саме та на якому рівні в процесі обробки задачі доцільно виконувати балансування навантаження;

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

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

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

– Динамічне балансування навантаження на рівні планувальника операційної системи недоцільно проводити з двох причин. По-перше, планувальник операційної системи працює в межах одного апаратного вузла. Якщо реалізувати балансування на рівні планувальника ОС, то буде відсутня можливість в результаті балансування перерозподіляти одиниці роботи між різними вузлами, які працюють під окремими операційними системами.

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

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