2.1.3. Навчальний приклад обчислення часткових сум послідовності числових значень

Розглянемо задачу знаходження часткових сум послідовності числових значень

,

(2.1.19)

де - кількість підсумованих значень (назва задачі - prefix sum problem) . Вивчення можливих паралельних методів розв’язку цієї задачі здійснимо на основі більш простого варіанту її постановки - з задачі обчислення загальної суми наявного набору значень (частковий випадок загальної задачі редукції)

.

(2.1.20)

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

,	(2.1.21)
	(2.1.22)

Обчислювальну схему цього алгоритму можна подати наступним чином, рис. 2.3:

Рис. 2.3. Послідовна обчислювальна схема алгоритму знаходження суми

,

(2.1.23)

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

(2.1.24)

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

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

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

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

Рис. 2.4. Каскадна схема алгоритму знаходження суми

Цю обчислювальну схему можна визначити як граф (нехай )

,

(2.1.25)

де є вершини графа ( - операції введення, - операції знаходження суми першої ітерації, і т.д.) а множина дуг графа визначається співвідношеннями:

.

(2.1.26)

Нескладно оцінити, кількість ітерацій каскадної схеми , яка виявляється рівною величині

,

(2.1.27)

а загальна кількість операцій знаходження суми

(2.1.28)

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

.

(2.1.29)

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

,	(2.1.30)
,	(2.1.31)

де - необхідна чисельність процесорів для виконання каскадної схеми.

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

за умови .

Модифікована каскадна схема. Отримання асимптотичної ненульової ефективності можна забезпечити в разі використання модифікованої каскадної схеми. Для спрощення побудови оцінок можна припустити . Тоді в новому варіанті каскадної схеми всі обчислення виконуються в два послідовно виконуваних етапи знаходження суми, рис. 2.5:

Рис. 2.5. Модифікована каскадна схема знаходження суми

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

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

Тоді для виконання першого етапу потрібно паралельних операцій з використанням процесорів. Для виконання другого етапу необхідно

(2.1.32)

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

.

(2.1.33)

З врахуванням отриманих оцінок показники прискорення та ефективності модифікованої каскадної схеми визначаються співвідношеннями:

,	(2.1.34)
.	(2.1.35)

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

за умови .

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

(2.1.36)

пропорційна тривалості виконання послідовного алгоритму.

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

.

(2.1.37)

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

- перед початком обчислень створюється копія вектора значень суми ( ;

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

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

(2.1.38)

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

Рис. 2. 6. Схема паралельного алгоритму обчислення всіх часткових сум (величини означають суми значень від до елементів числової послідовності)

З урахуванням отриманих співвідношень показники прискорення та ефективності паралельного алгоритму визначення всіх часткових сум оцінюється наступним чином:

.	(2.1.39)
.	(2.1.40)

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