Закон Амдала


Закон Амдала
Ускорение программы с помощью параллельных вычислений на нескольких процессорах ограничено размером последовательной части программы. Например, если можно распараллелить 95% программы, то теоретически максимальное ускорение составит 20×, невзирая на то, сколько процессоров используется.

Зако́н Амдала (англ. Amdahl's law, иногда также Закон Амдаля-Уэра) — иллюстрирует ограничение роста производительности вычислительной системы с увеличением количества вычислителей. Джин Амдал сформулировал закон в 1967 году, обнаружив простое по существу, но непреодолимое по содержанию ограничение на рост производительности при распараллеливании вычислений: «В случае, когда задача разделяется на несколько частей, суммарное время её выполнения на параллельной системе не может быть меньше времени выполнения самого длинного фрагмента». Согласно этому закону, ускорение выполнения программы за счёт распараллеливания её инструкций на множестве вычислителей ограничено временем, необходимым для выполнения её последовательных инструкций.

Содержание

Математическое выражение

Предположим, что необходимо решить некоторую вычислительную задачу. Предположим, что её алгоритм таков, что доля \alpha от общего объёма вычислений может быть получена только последовательными расчётами, а, соответственно, доля 1 - \alpha может быть распараллелена идеально (то есть время вычисления будет обратно пропорционально числу задействованных узлов p). Тогда ускорение, которое может быть получено на вычислительной системе из p процессоров, по сравнению с однопроцессорным решением не будет превышать величины

S_p = \cfrac{1}{\alpha + \cfrac{1 - \alpha}{p}}

Иллюстрация

Таблица показывает, во сколько раз быстрее выполнится программа с долей последовательных вычислений \alpha при использовании p процессоров.

\alpha\ 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

Из таблицы видно, что только алгоритм, вовсе не содержащий последовательных вычислений (\alpha = 0), позволяет получить линейный прирост производительности с ростом количества вычислителей в системе. Если доля последовательных вычислений в алгоритме равна 25 %, то увеличение числа процессоров до 10 дает ускорение в 3,077 раза, а увеличение числа процессоров до 1000 даст ускорение в 3,988 раза.

Отсюда же очевидно, что при доле последовательных вычислений \alpha общий прирост производительности не может превысить 1 / \alpha. Так, если половина кода — последовательная, то общий прирост никогда не превысит двух.

Идейное значение

Закон Амдала показывает, что прирост эффективности вычислений зависит от алгоритма задачи и ограничен сверху для любой задачи с \alpha \ne 0. Не для всякой задачи имеет смысл наращивание числа процессоров в вычислительной системе.

Более того, если учесть время, необходимое для передачи данных между узлами вычислительной системы, то зависимость времени вычислений от числа узлов будет иметь максимум. Это накладывает ограничение на масштабируемость вычислительной системы, то есть означает, что с определенного момента добавление новых узлов в систему будет увеличивать время расчёта задачи.

См. также

Литература


Wikimedia Foundation. 2010.

Смотреть что такое "Закон Амдала" в других словарях:

  • Закон Густавсона — Закон Густавсона  Барсиса (англ. Gustafson – Barsis s law)  оценка максимально достижимого ускорения выполнения параллельной программы, в зависимости от количества одновременно выполняемых потоков вычислений («процессоров») и доли… …   Википедия

  • Закон Мура — Проверить информацию. Необходимо проверить точность фактов и достоверность сведений, изложенных в этой статье. На странице обсуждения должны быть пояснения …   Википедия

  • Закон мура — Увеличение количества транзисторов по времени. Количество удваивается каждые 2 года Закон Мура  эмпирическое наблюдение, сделанное в 1965 году (через шесть лет после изобретения интегральной схемы), в процессе подготовки выступления Гордоном… …   Википедия

  • Параллельные вычислительные системы — Не следует путать с Распределённые вычисления. Параллельные вычислительные системы  это физические компьютерные, а также программные системы, реализующие тем или иным способом параллельную обработку данных на многих вычислительных узлах.[1]… …   Википедия

  • Распределённые вычисления — Не следует путать с Добровольные вычисления. См. также: Параллельные вычисления Распределённые вычисления способ решения трудоёмких вычислительных задач с использованием нескольких компьютеров, чаще всего объединённых в параллельную… …   Википедия

  • Параллельные вычисления — Не следует путать с Распределённые вычисления. Параллельные вычисления  такой способ организации компьютерных вычислений, при котором программы разрабатываются как набор взаимодействующих вычислительных процессов, работающих параллельно… …   Википедия

  • Параллельные компьютеры — Параллельные вычислительные системы это физические компьютерные, а также программные системы, реализующие тем или иным способом параллельную обработку данных на многих вычислительных узлах. Идея распараллеливания вычислений базируется на том, что …   Википедия

  • Message Passing Interface — Сюда перенаправляется запрос «OpenMPI». На эту тему нужна отдельная статья. Message Passing Interface (MPI, интерфейс передачи сообщений) программный интерфейс (API) для передачи информации, который позволяет обмениваться сообщениями между… …   Википедия

  • Nagios — Nagios …   Википедия

  • MPICH — MPICH2 Тип Программное обеспечение для обмена сообщениями между вычислительными процессами Написана на C, C++, Fortran, FreePascal Операционная система Universal Mac OS X, Linux, Unix, Windows Языки интерфейса …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.