Закон Амдала

 

Приобретая для решения своей задачи параллельную вычислительную систему, пользователь рассчитывает на значительное повышение скорости вычислений за счет распределения вычислительной нагрузки по множеству параллельно работа­ющих процессоров. В идеальном случае система из п процессоров могла бы уско­рить вычисления в п раз. В реальности достичь такого показателя по ряду причин не удается. Главная из этих причин заключается в невозможности полного распа­раллеливания ни одной из задач. Как правило, в каждой программе имеется фраг­мент кода, который принципиально должен выполняться последовательно и толь­ко одним из процессоров. Это может быть часть программы, отвечающая за запуск задачи и распределение распараллеленного кода по процессорам, либо фрагмент программы, обеспечивающий операции ввода/вывода. Можно привести и другие примеры, но главное состоит в том, что о полном распараллеливании задачи гово­рить не приходится. Известные проблемы возникают и с той частью задачи, кото­рая поддается распараллеливанию. Здесь идеальным был бы вариант, когда па­раллельные ветви программы постоянно загружали бы все процессоры системы, причем так, чтобы нагрузка на каждый процессор была одинакова. К сожалению, оба этих условия на практике трудно реализуемы. Таким образом, ориентируясь на параллельную ВС, необходимо четко сознавать, что добиться прямо пропорцио­нального числу процессоров увеличения производительности не удастся, и, есте­ственно, встает вопрос о том, на какое реальное ускорение можно рассчитывать. Ответ на этот вопрос в какой-то мере дает закон Амдала.

Джин Амдал (Gene Amdahl) — один из разработчиков всемирно известной си­стемы IBM 360, в своей работе, опубликованной в 1967 году, предложил фор­мулу, отражающую зависимость ускорения вычислений, достигаемого на много­процессорной ВС, от числа процессоров и соотношения между последовательной и параллельной частями программы. Показателем сокращения времени вычисле­ний служит такая метрика, как «ускорение».

Напомним, что ускорение S — это от­ношение времени T_s, затрачиваемого на проведение вычислений на однопроцес­сорной ВС (в варианте наилучшего последовательного алгоритма), ко времени Т_р решения той же задачи на параллельной системе (при использовании наилучшего параллельного алгоритма):

.

Оговорки относительно алгоритмов решения задачи сделаны, чтобы подчерк­нуть тот факт, что для последовательного и параллельного решения лучшими могут оказаться разные реализации, а при оценке ускорения необходимо исходить именно из наилучших алгоритмов.

Проблема рассматривалась Амдалом в следующей постановке (рис. 87). Преж­де всего, объем решаемой задачи с изменением числа процессоров, участвующих в ее решении, остается неизменным. Программный код решаемой задачи состоит из двух частей: последовательной и распараллеливаемой. Обозначим долю опера­ций, которые должны выполняться последовательно одним из процессоров, через f, где 0 ≤ f ≤ 1 (здесь доля понимается не по числу строк кода, а по числу реально выполняемых операций). Отсюда доля, приходящаяся на распараллеливаемую часть программы, составит 1 – f. Крайние случаи в значениях/соответствуют пол­ностью параллельным (f = 0) и полностью последовательным (f = 1) програм­мам. Распараллеливаемая часть программы равномерно распределяется по всем процессорам.

Рис. 87. К постановке задачи в законе Амдала.

 

С учетом приведенной формулировки имеем:

.

В результате получаем формулу Амдала, выражающую ускорение, которое может быть достигнуто на системе из n процессоров:

.

Формула выражает простую и обладающую большой общностью зависимость. Если устремить число процессоров к бесконечности, то в пределе получаем:

.

Это означает, что если в программе 10% последовательных операций (то есть f=0,1), то, сколько бы процессоров ни использовалось, убыстрения работы про­граммы более чем в десять раз никак ни получить, да и то, 10 — это теоретическая верхняя оценка самого лучшего случая, когда никаких других отрицательных фак­торов нет. Следует отметить, что распараллеливание ведет к определенным издерж­кам, которых нет при последовательном выполнении программы. В качестве при­мера таких издержек можно упомянуть дополнительные операции, связанные с распределением программ по процессорам, обмен информацией между процес­сорами и т. д.