Ускорение, эффективность, загрузка и качество

 

Рассмотрим параллельное выполнение программы со следующими характеристи­ками:

· О(п) — общее число операций (команд), выполненных на п-процессорной сис­теме;

· Т(п) — время выполнения O(п) операций на «-процессорной системе в виде числа квантов времени.

В общем случае Т(п) < O(п), если в единицу времени п процессорами выполня­ется более чем одна команда, где п > 2. Примем, что в однопроцессорной системе T(1) = O(1).

Ускорение (speedup), или точнее, среднее ускорение за счет параллельного вы­полнения программы — это отношение времени, требуемого для выполнения наи­лучшего из последовательных алгоритмов на одном процессоре, и времени парал­лельного вычисления на п процессорах. Без учета коммуникационных издержек ускорение S(n) определяется как

.

Как правило, ускорение удовлетворяет условию S(n) < п.

Эффективность (efficiency) n -процессорной системы — это ускорение на один процессор, определяемое выражением

.

Эффективность обычно отвечает условию 1/п ≤ Е(п) ≤ п. Для более реалис­тичного описания производительности параллельных вычислений необходимо промоделировать ситуацию, когда параллельный алгоритм может потребовать больше операций, чем его последовательный аналог.

Довольно часто организация вычислений на п процессорах связана с существен­ными издержками. Поэтому имеет смысл ввести понятие избыточности (redun­dancy) в виде

.

Это отношение отражает степень соответствия между программным и аппарат­ным параллелизмом. Очевидно, что 1 < R(n) < п.

Определим еще одно понятие, коэффициент полезного использования или ути­лизации (utilization), как

.

Тогда можно утверждать, что

и .

Рассмотрим пример. Пусть наилучший из известных последовательных алго­ритмов занимает 8с, а параллельный алгоритм занимает на пяти процессорах 2с. Тогда:

· S(n) = 8/2 = 4;

· E(n) = 4/5 = 0,8;

· R(n) = 1/0,8 – 1 = 0,25.

Собственное ускорение определяется путем реализации параллельного алгоритма на одном процессоре.

Если ускорение, достигнутое на п процессорах, равно п, то говорят, что алго­ритм показывает линейное ускорение.

В исключительных ситуациях ускорение S(n) может быть больше, чем п. В этих случаях иногда применяют термин суперлинейное ускорение. Данное явление имеет шансы на возникновение в двух следующих случаях:

Последовательная программа может выполняться в очень маленькой памяти, вызывая свопинги (подкачки), или, что менее очевидно, может приводить к большему числу кэш-промахов, чем параллельная версия, где обычно каждая параллельная часть кода выполняется с использованием много меньшего набо­ра данных.

Другая причина повышенного ускорения иллюстрируется примером. Пусть нам нужно выполнить логическую операцию А₁ v А₂, где как А₁, так и А₂ имеют зна­чение «Истина» с вероятностью 50%, причем среднее время вычисления А_i, обозначенное как T(А_i), существенно различается в зависимости от того, является ли результат истинным или ложным.

Пусть T(А_i)= 1c для А_i = 1; T(А_i)= 100c для А_i = 0. Теперь получаем четыре равновероятных случая (Т — «истина», F — «ложь», таблица 9).

 

Таблица 9
А1	А2	Последовательный	Параллельный
Т Т F F	Т F Т F	1с + 0 1с + 0 100 с + 1с 100 с +100 с	1 с 1с 1с 100с
∑	303/4с ≈ 76с	103/4с ≈ 26с

 

Таким образом, параллельные вычисления на двух процессорах ведут к сред­нему ускорению:

.

Отметим, что суперлинейное ускорение вызвано жесткостью последователь­ной обработки, так как после вычисления еще нужно проверить A₂. К факторам, ограничивающим ускорение, следует отнести:

· Программные издержки. Даже если последовательные и параллельные алго­ритмы выполняют одни и те же вычисления, параллельным алгоритмам прису­щи добавочные программные издержки — дополнительные индексные вычис­ления, неизбежно возникающие из-за декомпозиции данных и распределения их по процессорам; различные виды учетных операций, требуемые в параллель­ных алгоритмах, но отсутствующие в алгоритмах последовательных.

· Издержки из-за дисбаланса загрузки процессоров. Между точками синхро­низации каждый из процессоров должен быть загружен одинаковым объемом работы, иначе часть процессоров будет ожидать, пока остальные завершат свои операции. Эта ситуация известна как дисбаланс загрузки. Таким образом, уско­рение ограничивается наиболее медленным из процессоров.

· Коммуникационные издержки. Если принять, что обмен информацией и вы­числения могут перекрываться, то любые коммуникации между процессорами снижают ускорение. В плане коммуникационных затрат важен уровень грану­лярности, определяющий объем вычислительной работы, выполняемой между коммуникационными фазами алгоритма. Для уменьшения коммуникационных издержек выгоднее, чтобы вычислительные гранулы были достаточно крупны­ми и доля коммуникаций была меньше.

Еще одним показателем параллельных вычислений служит качество параллель­ного выполнения программ — характеристика, объединяющая ускорение, эффек­тивность и избыточность. Качество определяется следующим образом:

.

Поскольку как эффективность, так и величина, обратная избыточности, пред­ставляют собой дроби, то Q(n) < S(n). Поскольку Е(п) — это всегда дробь, a R(n) — число между 1 и п, качество Q(n) при любых условиях ограничено сверху величи­ной ускорения S(n).

 

Закон Амдала

 

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

Джин Амдал (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 — это теоретическая верхняя оценка самого лучшего случая, когда никаких других отрицательных фак­торов нет. Следует отметить, что распараллеливание ведет к определенным издерж­кам, которых нет при последовательном выполнении программы. В качестве при­мера таких издержек можно упомянуть дополнительные операции, связанные с распределением программ по процессорам, обмен информацией между процес­сорами и т. д.

 

Закон Густафсона

 

Известную долю оптимизма в оценку, даваемую законом Амдала, вносят исследо­вания, проведенные уже упоминавшимся Джоном Густафсоном из NASA Ames Research. Решая на вычислительной системе из 1024 процессоров три боль­ших задачи, для которых доля последовательного кода лежала в пределах от 0,4 до 0,8%, он получил значения ускорения по сравнению с однопроцессорным вари­антом, равные соответственно 1021,1020 и 1016. Согласно закону Амдала для дан­ного числа процессоров и диапазона f, ускорение не должно было превысить вели чины порядка 201. Пытаясь объяснить это явление, Густафсон пришел к выводу, что причина кроется в исходной предпосылке, лежащей в основе закона Амдала: увеличение числа процессоров не сопровождается увеличением объема решаемой задачи. Реальное же поведение пользователей существенно отличается от такого представления. Обычно, получая в свое распоряжение более мощную систему, пользователь не стремится сократить время вычислений, а, сохраняя его практи­чески неизменным, старается пропорционально мощности ВС увеличить объем решаемой задачи. И тут оказывается, что наращивание общего объема программы касается главным образом распараллеливаемой части программы. Это ведет к со­кращению значения f. Примером может служить решение дифференциального уравнения в частных производных. Если доля последовательного кода составляет 10% для 1000 узловых точек, то для 100 000 точек доля последовательного кода снизится до 0,1%. Сказанное иллюстрирует рис. 88, который отражает тот факт, что, оставаясь практически неизменной, последовательная часть в общем объеме увеличенной программы имеет уже меньший удельный вес.

Рис. 88. К постановке задачи в законе Густафсона.

 

Было отмечено, что в первом приближении объем работы, которая может быть произведена параллельно, возрастает линейно с ростом числа процессоров в сис­теме. Для того чтобы оценить возможность ускорения вычислений, когда объем последних увеличивается с ростом количества процессоров в системе (при посто­янстве общего времени вычислений), Густафсон рекомендует использовать выра­жение, предложенное Е. Барсисом (Е. Barsis):

.

Данное выражение известно как закон масштабируемого ускорения или закон Густафсона (иногда его называют также законом Густафсона-Барсиса). В заклю­чение отметим, что закон Густафсона не противоречит закону Амдала. Различие состоит лишь в форме утилизации дополнительной мощности ВС, возникающей при увеличении числа процессоров.