Достижению максимального ускорения может препятствовать существование в выполняемых вычислениях последовательных расчетов, которые не могут быть распараллелены. Джин Амдал (Gene Amdahl) показал, что верхняя граница для ускорения определяется долей последовательных вычислений алгоритма:
Например, если доля последовательных вычислений составляет 25%, то максимально достижимое ускорение для параллельного алгоритма равно:
В «законе Амдала» имеется несколько допущений, которые в реальных приложениях могут быть неверными. Одно из допущений заключается в том, что доля последовательных расчетов является постоянной величиной и не зависит от вычислительной сложности решаемой задачи. Однако для большинства задач f является убывающей функцией от n, где n – параметр сложности задачи. В этом случае ускорение может быть увеличено при увеличении вычислительной сложности задачи. Нарушение «закона Амдала» также может быть связано с архитектурными особенностями параллельной вычислительной системы. Например, параллельный алгоритм уменьшает объем данных, используемых каждым процессором, и повышает эффективность использования кэш-памяти каждого процессора. Оптимальная работа с кэш-памятью может сильно увеличить быстродействие алгоритма.
Параллельный алгоритм называется масштабируемым, если при росте числа процессоров он обеспечивает увеличение ускорения при сохранении постоянного уровня эффективности использования процессоров.
--
