Показатели производительности алгоритмов распараллеливания. Технология гиперпоточности. Многозадачные и многопоточные системы. Суперскалярные вычисления. Группа : tt-13-20p

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

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


Рис. 1. Иллюстрация закона Амдаля
Обозначим через 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) ,

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

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