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

T = tc + tsys + ti/o + tcomm + tw, (2.5)

де:

- tc – час проведення обчислень,

- tsys – час, витрачений на системні виклики ядра,

- ti/o – час введення/виведення даних (окрім мережевої взаємодії з іншими процесами).

- tcomm – час взаємодії з іншими процесами (пересилка даних),

- tw – час очікування.

Слід відмітити, що коефіцієнт ефективності обмежується відношенням часу виконання обчислень до повного часу виконання, а саме, відповідно до (2.4) та (2.5):

що відповідає закону Амдала. [41] Складові часу очікування:

tw=tw, in + tw, fin,

де:

tw, in – час очікування під задачами вхідних даних, які є вихідними даними інших задач,

tw, fin – час простою ядер наприкінці обчислень, пов'язаний з нерівномірністю навантаження.

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

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

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

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

За рахунок балансування навантаження не вдасться змінити такі характеристики як час обчислень tc, час роботи ядра tsys та час введення та виведення tі/о. Натомість можна змінювати характеристики, пов’язані з пересилками та незбалансованістю розподілу роботи: tcomm, tw, in та tw, fin. Ці характеристики обведені рамкою на рис. 2.1.

Відповідно до проведеного аналізу, необхідно проводити оптимізацію відповідно до наступних умов:

. (2.6) 

Рис. 2.1. Вплив динамічних характеристик виконання програми
на коефіцієнт ефективності

2.3. Аналіз задач, що вирішуються на високопродуктивних обчислювальних системах

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

Нехай ∑ – скінченний алфавіт, а ∑* – множина рядків, що складаються з літер Е. Відповідно до визначення Алана Тьюрінга, алгоритм – це функція f : ∑ → ∑*, обчислення якої можна реалізувати на детермінованій машині Тьюрінга. [42]

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

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

Якщо кількість кроків у всіх підзадачах Ni(D) є функцією розміру вхідних даних | D |, та не залежить від конкретних значень цих даних:

i,D1,D2 : якщо | D1 | = | D2 |, то Ni(D1) = Ni(D2),

то таку реалізацію алгоритму будемо називати паралельною реалізацією алгоритму з регулярним паралелізмом. Якщо кількість кроків у принаймні одній підзадачі не є функцією розміру вхідних даних, то таку реалізацію алгоритму будемо називати паралельною реалізацією алгоритму з нерегулярним паралелізмом. [43, 44, 45]

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

Типові векторно-матричні алгоритми, які часто використовуються при вирішенні більш складних задач, часто припускають паралельні реалізації з регулярним паралелізмом. Так, наприклад, бібліотека базових підпрограм лінійної алгебри ВLAS [5] містить реалізації багатьох таких алгоритмів. Наприклад, алгоритм SAXPY, який обчислює зважену суму двох векторів:

z = ax + у.

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

,

де D=áx,y,añ – вхідні дані, n – розмірність векторів x та у, P – кількість процесорів.

Вхідні дані:
Вихідні дані:
1 begin
2	for i ← 1 to n do
3		;
4	end
5 end

_____________________________________________________________

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

Вхідні дані: Вихідні дані: Спільні змінні:
1 begin
2	;
3	виконати залежні підзадачі Ті;
4 end
5 Підзадача і begin
6	for j ← iN to i(N+1)-1 do
7		;
8	end
9 end

_________________________________________________________________

Рис. 2.3. Паралельна реалізація алгоритму SAXPY з регулярним паралелізмом

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

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