Ступінь паралелізму

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

Рисунок 2 - Схема додавання векторів

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

Розглянемо тепер задачу складання n чисел. Звичайний послідовний алгоритм

(2)

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

Рисунок 3 - Схема алгоритму здвоювання

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

Для чисел алгоритм здвоювання складається з етапів; на першому етапі виконується додавань, на другому — , і так далі, поки на останньому етапі не буде виконано останнє додавання. Загальне число операцій додавання дорівнює : таке ж, як і в послідовному алгоритмі (2).

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

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

Середнім ступенем паралелізму чисельного алгоритму називається відношення загального числа операцій алгоритму до його етапів. Очевидно, для алгоритму здвоювання середня ступінь паралелізму дорівнює:

(3)

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

Дата добавления: 2014-01-07