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

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

ОглядРедагувати

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

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

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

  • Закон Роботи — вартість обчислень завжди буде менша за роботу:
      
    Це пов'язано з тим фактом, що певна кількість процесорів p може виконувати не більше n операцій паралельно.
  • Закону Прольоту — кількість процесорів завжди буде скінченним числом, а отже
      

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

  • Прискорення — це збільшення швидкості паралельних обчислень в порівнянні з послідовними: Sp = T1 ∕ Tp. Якщо прискорення Ω(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 процесорах, то за умови виконання кожним процесором кількох блоків роботи, виникає так званий закон Брента.

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

 

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

 

[3]

Див. такожРедагувати

ПриміткиРедагувати

  1. а б Томас Кормен; Чарльз Лейзерсон, Рональд Рівест , Кліффорд Штайн (2009) [1990]. Вступ в алгоритми (вид. 3rd). MIT Press і McGraw-Hill. с. 779–784. ISBN 0-262-03384-4. 
  2. а б в Casanova, Henri; Legrand, Arnaud; Robert, Yves (2008). Parallel Algorithms. CRC Press. с. 10. 
  3. Blelloch, Guy (1996). Programming Parallel Algorithms. Communications of the ACM 39 (3). с. 85–97. doi:10.1145/227234.227246.