С точки зрения параллелизма, как пути для повышения эффективности вычислений, существует две крайности.
Первая, когда параллельные вычисления не возможны или очень мало эффективны. Обычно это связано с тем, что каждый шаг в алгоритме зависит от вычислений или статуса выполнения предыдущего шага.
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 процессоров, по сравнению с однопроцессорным решением не будет превышать величины:
Таблица показывает, во сколько раз быстрее выполнится программа с долей последовательных вычислений a при использовании p процессоров.
╔═════════╦════════════════╦═════════════╦══════════╗
║ a/p ║ 10 ║ 100 ║ 1000 ║
╠═════════╬════════════════╬═════════════╬══════════╣
║ 0 ║ 10 ║ 100 ║ 1000 ║
║ 10% ║ 5.263 ║ 9.174 ║ 9.910 ║
║ 25% ║ 3.077 ║ 3.883 ║ 3.988 ║
║ 40% ║ 2.174 ║ 2.463 ║ 2.496 ║
╚═════════╩════════════════╩═════════════╩══════════╝
Из таблицы видно, что только алгоритм, вовсе не содержащий последовательных вычислений (a = 0), позволяет получить линейный прирост производительности с ростом количества вычислителей в системе. Если доля последовательных вычислений в алгоритме равна 25%, то увеличение числа процессоров до 10 дает ускорение в 3,077 раза, а увеличение числа процессоров до 1000 даст ускорение в 3,988 раза.
Отсюда же очевидно, что при доле последовательных вычислений a общий прирост производительности не может превысить 1/a. Так, если половина кода — последовательная, то общий прирост никогда не превысит двух.
Закон Амдала показывает, что прирост эффективности вычислений зависит от алгоритма задачи и ограничен сверху для любой задачи с a<>0. Не для всякой задачи имеет смысл наращивание числа процессоров в вычислительной системе.
Более того, если учесть время, необходимое для передачи данных между узлами вычислительной системы, то зависимость времени вычислений от числа узлов будет иметь максимум. Это накладывает ограничение на масштабируемость вычислительной системы, то есть означает, что с определенного момента добавление новых узлов в систему будет увеличивать время расчёта задачи.
Закон Густавсона-Барсиса
Оценка максимально достижимого ускорения выполнения параллельной программы, в зависимости от количества одновременно выполняемых потоков вычислений («процессоров») и доли последовательных расчётов.
Закон Густафсона — Барсиса выражается формулой:
s — доля последовательных расчётов в программе,
n — количество процессоров
Данную оценку ускорения называют ускорением масштабирования (scaled speedup), так как данная характеристика показывает, насколько эффективно могут быть организованы параллельные вычисления при увеличении сложности решаемых задач.
При оценке ускорения параллельного выполнения закон Амдала предполагает, что объем задачи остается постоянным. Величина ускорения по закону Амдала показывает, во сколько раз меньше времени потребуется параллельной программе для выполнения.
Однако величину ускорения можно рассматривать и как увеличение объема выполненной задачи за постоянный промежуток времени. Закон Густафсона появился именно из этого предположения.
Ускорение масштабирования определяется как отношение объема вычислений, выполненных с использованием многопоточности, к объему вычислений, выполненных последовательно за один и тот же промежуток времени.
Источники
Комментарии в Telegram-группе!