Процессоры используют одну часть времени на непосредственно вычисления, а другую - на обмен сообщениями.
Закон Амдаля связывает ускорение с долей операций, выполняемых последовательно.
Обозначим через f ту часть алгоритма, которая не распараллеливается,
тогда та часть алгоритма, которую можно распределить по процессорам, будет равна
(1-f) (затраты на коммутацию не учитываются).
Пусть ts - время выполнения алгоритма на одном процессоре однопроцессорной
системы (последовательная машина), n - число процессоров.
Поясняющий рисунок:
При переносе расчетов на параллельную машину время расчета
распределится следующим образом:
время f ts займет та часть алгоритма, которую невозможно распараллелить,
время (1-f) ts / n будет затрачено на
распараллеливаемую часть алгоритма.
Истинное время tp, затраченное на работу на параллельной машине c n процессорами,
будет рассчитываться по формуле:
tp=f ts+(1-f) ts / n.
Определим фактор ускорения расчета S(n), достигаемый на параллельной машине c
n процессорами, как S(n)=ts / tр.
S(n)=ts / tр=
n / (f n+1-f)
или
S(n)=n / (1+(n-1)f)=n / (fn+1-f) ,
где f- доля операций, выполняемых последовательно.
Эта формула называется законом Амдаля (Gene Amdahl) об ограничении скорости параллельных вычислений.
Она была выведена в 1967 году и говорит о том, что даже если часть последовательных вычислений мала,
максимальный фактор ускорения для бесконечного числа процессоров не превосходит
1 / f.
Для существенного увеличения фактора ускорения S(n) необходимо минимизировать
долю операций f, выполняемых последовательно: f<<1. Однако даже в
этом случае величина fn может быть достаточно заметной при
большом числе используемых процессоров n.
При f<<1 закон Амдаля будет преобразован в виде:
S(n)=n / (1+f n) ,
Из приведенных графиков видно, что при большой доле последовательной части алгоритма f
(близкой к 1) увеличение числа процессоров не
приводит к существенному ускорению выполнения задачи.
При заданном значении f величина S(n) приближается к своему асимптотическому
значанию, приблизительно равному 1 /f , поэтому существует некоторое
критическое значение количества процессоров n, после которого наращивание числа
процессоров не приводит к увеличению фактора ускорения.
[Назад]
[Оглавление]
[Вперед]
Последнее обновление 21.11.2001 WebMaster