Закон Амдала — это закон, который определяет связь между предполагаемым ускорением параллельных осуществлений алгоритма и последовательным алгоритмом при неизменном размере решаемой задачи.
Введение
С точки зрения параллелизма, как пути для увеличения эффективности вычислительных процедур, изучаются следующие случаи:
- Случай, когда параллельные вычисления не представляются возможными или обладают малой эффективностью. Как правило, это связано с тем, что любой шаг исполняемого алгоритма зависит от результата или статуса выполнения предыдущего шага.
- Случай Embarrassingly parallel, что означает случай чрезвычайной параллельности. Это абсолютно иной тип задач, для которых нет необходимости в приложении больших усилий для подразделения их на несколько отдельных параллельных подзадач.
Для второго типа, как правило, не существует прямой зависимости между этими параллельными задачами, то есть результаты их решения не могут влиять друг на друга. Распараллеливание может повлечь дополнительные расходы, а именно:
- На синхронизацию.
- На смену контекста и прочее.
Когда задача плохо разбивается на параллельные вычисления, то такие дополнительные расходы способны привести к уменьшению производительности. С другой стороны, когда задача легко может быть поделена на набор параллельных задач, то она может быть подвергнута масштабированию не только по ядрам одной машины, но и в горизонтальном направлении, то есть, на множество разных машин. Как следствие могут появиться проблемы, связанные с сохранением и объединением результатов.
Закон Амдала, сверх масштабируемые и сверх линейные по скорости исполнения алгоритмы
Закон Амдала определяет метод, при помощи которого возможно смоделировать потенциальный выигрыш в производительности при организации параллельных вычислений. Ускорение (speedup), которое получается при использовании параллельного алгоритма для p процессоров, в сравнении с последовательным вариантом реализации вычислений определяется следующей формулой:
Sp(n) = T1(n) / Tp(n)
То есть, это отношение времени решения задач на скалярном процессоре (оценка T1 задаёт время исполнения алгоритма при работе на одном процессоре, то есть определяет время исполнения последовательной версии алгоритма решения задачи) к времени исполнения параллельного алгоритма (значение n используется для параметризации уровня вычислительной сложности решаемой задачи и может представлять, к примеру, количество входных данных задачи).
Эффективность (efficiency) применения параллельным алгоритмом процессоров для решения задачи может быть определена по следующему соотношению:
Ep(n) = T1(n) / (pTp(n)) = Sp(n) / p
Значение эффективности может определить среднюю долю времени исполнения алгоритма, в течение которой процессоры фактически используются для решения задачи. Закон Амдала, по сути, выполняет иллюстрацию ограничения роста производительности вычислительной системы с ростом числа вычислительных модулей.
Джин Амдал вывел формулировку своего закона в 1967-ом году, выявив очень простое по своей сути, но непреодолимое по содержанию ограничение роста производительности при осуществлении распараллеливания вычислительных операций, в следующем виде:
«В случае, когда задача подразделяется на некоторое количество частей, общее время её исполнения на параллельной системе не может быть меньше времени исполнения самого длинного фрагмента».
В соответствии с этим законом, ускорение исполнения программы за счёт распараллеливания её операций на множестве вычислительных модулей ограничено временем, которое требуется для исполнения её последовательных инструкций.
Допустим, что требуется выполнить решение некоторой вычислительной задачи. Можно предположить, что её алгоритм таков, что долю «a» от общего объёма вычислительных операций можно получить только при помощи последовательных расчётов, а, соответственно, долю «1 — a» можно распараллелить идеально. То есть время вычислительных процедур является обратно пропорциональным количеству используемых узлов «p».
В этом случае ускорение, которое можно получить на вычислительной системе из p процессорных модулей, по сравнению с однопроцессорным вариантом решения не будет больше следующего значения:
Рисунок 1. Формула. Автор24 — интернет-биржа студенческих работ
Таблица, приведённая ниже, может показать, во сколько раз быстрее исполнится программа с долей последовательных вычислений «a», если задействовать «p» процессорных модулей:
Рисунок 2. Таблица. Автор24 — интернет-биржа студенческих работ
Из данной таблицы следует, что только алгоритм, который совсем не содержит последовательных вычислений (a = 0), даёт возможность получения линейного прироста производительности при росте количества вычислительных модулей в системе. Если доля последовательных вычислений в алгоритме равняется двадцати пяти процентам, то увеличение количества процессорных модулей до десяти позволяет получить ускорение только в 3,077 раза, а увеличение числа процессорных модулей до тысячи даст ускорение всего лишь в 3,988 раза.
Отсюда же следует, что при доле последовательных вычислений «a» суммарный прирост производительности не может превысить значения «1/a». Так, если половина операций являются последовательными, то общий прирост никогда не превысит двух. Закон Амдала утверждает, что прирост эффективности вычислительных процедур имеет зависимость от алгоритма задачи и ограничен сверху для любой задачи с «a меньше или больше 0». Не для каждой задачи имеет смысл наращивать количество процессорных модулей в вычислительной системе. Более того, если принять во внимание время, которое необходимо для передачи данных между модулями вычислительной системы, то зависимость времени вычислений от количества узлов будет максимальной.
