Закон Амдала, сверхмасштабируемые и сверхлинейные по скорости исполнения алгоритмы

Для оценивания эффективности разработанной многопроцессорной системы воспользуемся законом Амдала (Gene Amdahl, 1967) [1]. Он связывает потенциальное ускорение вычислений при распараллеливании с долей операций, выполняемых априори последовательно. Пусть f (0 < f < 1) – доля операций алгоритма, которую распараллелить невозможно, тогда распараллельная доля равна (1 – f). При этом на первом этапе исследования эффективности многопроцессорных систем затраты времени на передачу сообщений не учитываются. Предположим, что ts – время выполнения алгоритма на одном процессоре (последовательный вариант), а n – число процессоров параллельной вычислительной системы. Тогда при переносе алгоритма решения необходимой задачи на параллельную вычислительную систему время расчета распределится таким образом:
– f • ts – время выполнения части алгоритма, которую распараллелить невозможно;
– (1-f) • ts / n – время, затраченное на выполнение распараллеленной части алгоритма.
Тогда время tp, необходимое для расчета на параллельной вычислительной системе с использованием количества процессоров n, будет определяться следующим образом:
tp = f • ts + (1 – f) • ts/n .(1.1)
При этом ускорение времени расчета программы можно выяснить на основании выражения:
(1.2)
Учитывая соотношения (1.1), значение величины S можно записать в таком виде:
(1.3)
Соотношение (1.3) и называют законом Амдала об ограничении скорости параллельных вычислений. Он была получен в 1867 году и говорит о том, что даже если часть последовательных вычислений мала, максимальный фактор ускорения для бесконечного числа процессоров не превосходит 1 / f.