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

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

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

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

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

   ${\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 називається досконалим лінійним прискоренням.[1] Алгоритм, який показує лінійне прискорення вважається так званим масштабованим алгоритмом. [2]
• Ефективність - величина прискорення, що припадає на один процесор: Sp ∕ p.[2]
• Паралельність — відношення 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).}$

[3]

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