Основы распараллеливания алгоритмов

Эффективность использования параллельным алгоритмом процессоров при решении задачи определяется соотношением:

(величина эффективности определяет среднюю долю времени выполнения алгоритма, в течение которой процессоры реально используются для решения задачи).
Как следует из приведенных соотношений, в наилучшем случае Sp(n) = p и Ep(n) = 1.

Для примера пред ставленого на рис.8.2 ускорение и эффективность рас читаны в таблице.

Характеристики параллельности

для выражения E:	для выражения Ep:
T1(n)=n-1=6	T1(n)=n-1=6
Tp(n)=t=5	Tp(n)=tp=5
Sp(n)=1,2	Sp(n)=2
Qp(n)=0.6	Qp(n)=0.66

Таким образом, выражение Ep имеет лучшие характеристики параллельности, чем выражение E.

8.4 Закон Амдаля –формальная модель ускорения кластера

Выполнение любого параллельного алгоритма включает в себя как последовательную часть так и параллельную.


Рис. 8.4. Иллюстрация закона Амдаля

Обозначим через f ту часть алгоритма, которая не распараллеливается, тогда та часть алгоритма, которую можно распределить по процессорам, будет равна (1-f) (затраты на коммутацию не учитываются).

Пусть T₁ - время выполнения алгоритма на одном процессоре однопроцессорной системы (последовательная машина), p - число процессоров.

При переносе расчетов на параллельную машину время расчета распределится следующим образом:

• 
  время f T₁займет та часть алгоритма, которую невозможно распараллелить,
  
• 
  время (1-f) T₁ / p будет затрачено на распараллеливаемую часть алгоритма.
  

Истинное время T_p, затраченное на работу на параллельной машине c p процессорами, будет рассчитываться по формуле:
T_p=f T₁+(1-f) T₁ / p.

Определим фактор ускорения расчета S_p(n), достигаемый на параллельной машине c p процессорами, как Sp= T1 / Tp.

Sp= T1 / Tp = p/(fp+1-f) или Sp = p/(1+(p-1)f)=p/(fp+1-f)
где f- доля операций, выполняемых последовательно.

Эта формула называется законом Амдаля (Gene Amdahl) об ограничении скорости параллельных вычислений. Она была выведена в 1867 году и говорит о том, что даже если часть последовательных вычислений мала, максимальный фактор ускорения для бесконечного числа процессоров не превосходит 1 / f.

Для существенного увеличения фактора ускорения S_p необходимо минимизировать долю операций f, выполняемых последовательно: f<<1. Однако даже в этом случае величина fp может быть достаточно заметной при большом числе используемых процессоров p.
При f<<1 закон Амдаля будет преобразован в виде: S_p=p / (1+f p) ,


Рис. 8.5. Зависимости ускорения

Из приведенных графиков видно, что при большой доле последовательной части алгоритма f (близкой к 1) увеличение числа процессоров не приводит к существенному ускорению выполнения задачи.

При заданном значении f величина S_p приближается к своему асимптотическому значению, приблизительно равному 1 /f , поэтому существует некоторое критическое значение количества процессоров p, после которого наращивание числа процессоров не приводит к увеличению фактора ускорения.