Аналіз паралельних алгоритмів

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

Огляд

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

• Робота — це кількістний показник елементарних операцій, що були виконанні кількістю процесорів p для виконання обчислень. Позначається як Т₁.
• Проліт — довжина найдовшої послідовності операцій, які повинні виконуватися послідовно. Проліт часто також називають критичною довжиною шляху або глибину розрахунку. Дуже важливо звести до мінімуму величину прольоту під час розробки паралельних алгоритмів, оскільки саме від величини прольоту залежить можливий максимально короткий термін виконання обчислень. Проліт також може позначатися як час T_∞, що був затрачений для обчислень, що були виконані за умови використанням ідеалізованої машини з нескінченною кількістю процесорів.
• Вартість обчисення — показник загального часу витраченого процесорними одиницями для виконання обчислень. 

З наведених вище понять та їх визначень випливає наступне:

• Закон Роботи — вартість обчислень завжди буде менша за роботу:

   ${\displaystyle pT_{p}\geq T_{1}}$

  Це пов'язано з тим фактом, що певна кількість процесорів p може виконувати не більше n операцій паралельно.

• Закону Прольоту — кількість процесорів завжди буде скінченним числом, а отже

   ${\displaystyle T_{p}\geq T_{\infty }}$

Опираючись на вищеподані визначення і закони можна виділити наступні атрибути:

• Прискорення — це збільшення швидкості паралельних обчислень в порівнянні з послідовними: S_p = T1 ∕ T_p. Якщо прискорення Ω(n) для вхідного масиву даних з розміром n є лінійним, то випливає, що T1 ∕ Tp ≤ p. Ситуація коли T1 ∕ Tp = p називається досконалим лінійним прискоренням. Алгоритм, який показує лінійне прискорення вважається так званим масштабованим алгоритмом. 
• Ефективність - величина прискорення, що припадає на один процесор: Sp ∕ p.
• Паралельність — відношення T1 ∕ T∞. Являє собою максимально можливе прискорення на будь-якій кількості процесорів. Згідно закону прольоту: p > T1 ∕ T∞, then T1 ∕ Tp ≤ T1 ∕ T∞ < p

Виконання на обмеженій кількості процесорів

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

Закон Брента стверджує:

${\displaystyle T_{p}\leq T_{N}+{\frac {T_{1}-T_{N}}{p}},}$

Формулу також можна звести до наступного вигляду:

${\displaystyle T_{p}=O\left(T_{N}+{\frac {T_{1}}{p}}\right).}$

Див. також

• Оцінка комунікаційної трудомісткості паралельних алгоритмів

Примітки

1. Т. Кормен; Ч. Лейзерсон; Р. Рівест; К. Стайн (2009) [1990]. 27 Багатопотокові алгоритми. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN .
2. Casanova, Henri; Legrand, Arnaud; Robert, Yves (2008). Parallel Algorithms. CRC Press. с. 10.
3. Blelloch, Guy (1996). (PDF). Communications of the ACM. Т. 39, № 3. с. 85—97. doi:10.1145/227234.227246. Архів оригіналу (PDF) за 4 березня 2016. Процитовано 2 червня 2016.