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

Для оценивания эффективности разработанной многопроцессорной системы воспользуемся законом Амдала (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.