6.Зависимость ускорения вычислений от количества процессоров. Закон Амдала

Физический адрес. Адресное пространство памяти. Регистры дескрипторы.

Возможно ли, чтобы система из N процессоров могла бы ускорить вычисления в N раз? В реальности достичь такого показателя по ряду причин не удается. Основная причина - невозможно полного распараллеливания ни одной задачи.

В любой программе имеется фрагмент кода, который принципиально должен выполняться последовательно и только одним ЦП.

Идеальным был бы вариант, тогда параллельные ветви программы постоянно загружали бы все ЦП ВС и притом так, чтобы нагрузка на каждый ЦП бала бы одинаковой. Однако это реализовать трудно.

Таким образом, ориентируясь на параллельную ВС, необходимо четко осознавать, что добиться прямо пропорционального числу ЦП увеличения производительности не удается. Поэтому встает вопрос: на какое ускорение (реально) можно рассчитывать? Ответ на этот вопрос в какой-то мере дает закон Амдалла.

Он в 1967 г. предложил формулу, отражающую зависимость ускорения вычислений, достигаемого на многопроцессорной ВС, от числа ЦП и соотношение между последовательной и параллельной частями программы. Показателем сокращения времени вычислений служит такое понятие как «ускорение», обозначаемое S и определяемое по формуле

S = Ts /Tp,

где Ts – время, затрачиваемое на проведение вычислений на однопроцессорной ВС (с использованием наилучший последовательный алгоритм) и Тр – время решения той же задачи на параллельной ВС (при использовании наилучшего параллельного алгоритма).

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

Время решения задачи на параллельной ВС состоит из двух частей: время затрачиваемое на выполнение последовательной части программы, определяемое по формуле (f Ts) и времени, затрачиваемое на выполнение параллельной части программы одним ЦП, определяемое по формуле ((1 – f ) Ts) / N. Тогда имеем следующую формулу:

Тр = (f Ts) + ((1 – f ) Ts) / N)

В результате получается формула Амдала, выражающее ускорение, которое может быть достигнуто на системе из N процессоров: S = Ts /Tp = N / (1+( N-1) f). Формула выражает простую и обладающую большой общностью зависимость.

Если число ЦП стремится к бесконечности, то в пределе получаем lim S = 1 / f

Считается, что если в программе 10% последовательных операций (f = 0.1), то сколько бы ЦП ни использовались, убыстрения работы программы более чем в 10 раз никак ни получить. Имеется 10 – это теоретическая верхняя оценка самого лучшего случая, когда никаких других отрицательных факторов нет.

Надо отметить, что распараллеливание ведет к определенным издержкам, которых нет при последовательном выполнении программы. Примерами таких издержек являются: дополнительные операции, связанные с распределением программ по ЦП;

обмен информацией между процессорами и т.д.