Эффективность параллельной программы это отношение

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

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

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

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

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

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

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

Лукьяненко Д.В. — Параллельные вычисления — 4.Эффективность и масштабируемость параллельных программ

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

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

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

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

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

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

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

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

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

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

Другая причина повышенного ускорения иллюстрируется примером. Пусть нам нужно выполнить логическую операцию А1 v А2, где как А1, так и А2 имеют зна­чение «Истина» с вероятностью 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с

Параллельное программирование. Лекция 16b. Эффективность параллельных программ

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

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

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

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

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

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

Закон Амдала

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

В реальности достичь такого показателя по ряду причин не удается. Главная из этих причин заключается в невозможности полного распа­раллеливания ни одной из задач. Как правило, в каждой программе имеется фраг­мент кода, который принципиально должен выполняться последовательно и толь­ко одним из процессоров.

Это может быть часть программы, отвечающая за запуск задачи и распределение распараллеленного кода по процессорам, либо фрагмент программы, обеспечивающий операции ввода/вывода. Можно привести и другие примеры, но главное состоит в том, что о полном распараллеливании задачи гово­рить не приходится.

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

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

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

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

Проблема рассматривалась Амдалом в следующей постановке (рис. 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):

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

Источник: infopedia.su

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

Абсолютно параллельных алгоритмов, за исключением тривиальных случаев, не бывает. Как правило, алгоритм параллельной программы представляет собой последовательность параллельных и последовательных участков, т.е. распределение данных (параллельная часть) и их обработку на всех или отдельных процессах (последовательно-параллельная часть). Поэтому естественно, чем меньше время выполнения последовательных участков, тем параллельный алгоритм теоретически должен бать эффективнее. Например, если алгоритм таков, что на первом и последнем этапах – работа последовательна и составляет 10%, центральная часть алгоритма параллельна и составляет 90% всей работы, то это ещё не означает, что мы получим высокую эффективность такого параллельного алгоритма.

Достижению максимального ускорения может препятствовать существование в выполняемых параллельных вычислениях последовательных расчетов, которые не могут быть распараллелены. Обосновывает этот факт закон Амдаля (Amdahl).

Зако́н Амдала(англ.Amdahl’s law, иногда такжеЗакон Амдаля-Уэра) — иллюстрирует ограничение ростапроизводительностивычислительной системыс увеличением количествавычислителей.

«В случае, когда задача разделяется на несколько частей, суммарное время её выполнения на параллельной системе не может быть меньше времени выполнения самого длинного фрагмента». [1] Согласно этому закону, ускорение выполнения программы за счётраспараллеливанияеё инструкций на множестве вычислителей ограничено временем, необходимым для выполнения её последовательных инструкций.

Закон Амдаля

Пусть процессоры однородны по производительности. Т0 – время выполнения последовательной части параллельного алгоритма, например, генерирование начальных данных и обработка полученного при решении задачи результата.

Т1, Т2, . Тp – время последовательной работы, выполняемой каждым процессором без взаимодействия между собой. Тогда время выполнения задачи на p процессорах определяется неравенством:

где i=1, 2, . p. Равенство получается, когда Тi равны между собой. Отсюда, подставляя = Tseq – T0, где Tseq есть время выполнения задачи на одном процессоре, получаем:

Tpar ≥ T0 + . Делим на Tseq и, обозначая через f = T0 / Tseq — долю (fraction) последовательного участка в общем объеме вычислений, получим:

. (1.1)

Ускорение (Speedup) – это отношение времени выполнения задачи в последовательном режиме (на 1 процессоре), ко времени выполнения задачи в параллельном режиме (на p процессорах).

S , используя неравенство (1.1), получим

(1.2)

Отсюда видно, что при f=0 и равенстве Ti получим S=p, при f >0 и p → ∞, получим . Данная функция является монотонно-возрастающей по p и, значит, достигает максимума на бесконечности. Следовательно, ни на каком числе процессоров ускорение счета не может превысить обратной величины доли последовательного участка.

Рассматривая закон Амдаля, мы предполагали, что доля последовательных расчетов f является постоянной величиной и не зависит от параметра n, определяющего вычислительную сложность решаемой задачи. Однако для большого ряда задач доля f=f(n) является убывающей функцией от n, и в этом случае ускорение для фиксированного числа процессоров может быть увеличено за счет уменьшения доли последовательной работы, выполняемой каждым процессором. Иначе говоря, ускорение Sp= Sp(n) является возрастающей функцией от параметра n (данное утверждение часто называют эффектом Амдаля).

Эффективность распараллеливания.

Эффективность распараллеливания – это способность алгоритма использовать все задействованные в выполнении задачи процессоры на 100%. Формула вычисления эффективности:

(1.2)

Т.е. если ускорение S = p (максимально возможное на p процессорной машине), то эффективность распараллеливания задачи равна 100%. Используя закон Амдаля получаем верхнюю оценку эффективности:

E ≤ 100% (1.3)

Например, E ≤ 52.25% для p=100 и f=0.01 и E ≤ 9.1% для p=1000 и f=0.01.

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

Масштабирование (scalable) – это способность параллельного алгоритма эффективно использовать процессоры при повышении сложности вычислений. Задача является масштабируемой, если при росте числа процессоров алгоритм обеспечивает пропорциональное увеличение ускорения при сохранении постоянного уровня эффективности использования процессоров.

Масштабируемость – это пропорциональное увеличение объема задачи с увеличением числа используемых для ее решения процессоров. Наличие масштабируемости задач является важным свойством тестовых систем оценки производительности параллельных вычислительных систем.

Плохая масштабируемость параллельного приложения на MPP-системе может быть вызвана а) ростом затрат на коммуникации при увеличении числа используемых процессоров; б) неравномерностью распределения вычислительной нагрузки между процессорами.

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

Оценим накладные расходы (total overhead), которые имеют место при выполнении параллельного алгоритма T0 = P*Tp − T1 , где T1 — время выполнения последовательного алгоритма задачи, Tp — время выполнения алгоритма задачи на P процессорах.

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

Используя введенное обозначение, можно получить новые выражения для времени параллельного решения задачи и соответствующего ускорения:

Tp = (T1 + T0)/P , Sp = T1/ Tp = (P* T1)/( T1 + T0)

Тогда эффективность использования процессоров можно выразить как

EP = Sp/P = T1/ (T1 + T0) = 1/(1+ T1/T0)

Тогда, если сложность решаемой задачи является фиксированной (T1=const), то при росте числа процессоров эффективность, как правило, будет убывать за счет роста накладных расходов T0. При фиксированном числе процессоров, эффективность можно улучшить путем повышения сложности решаемой задачи T1, поскольку предполагается, что при увеличении сложности накладные расходы T0 растут медленнее, чем объем вычислений T1.

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

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

Источник: studfile.net

Показатели эффективности параллельного алгоритма

Sp(n)=T1(n)/Tp(n), т.е. как отношение времени решения задач на скалярной ЭВМ к времени выполнения параллельного алгоритма (величина n применяется для параметризации вычислительной сложности решаемой задачи и может пониматься, например, как количество входных данных задачи).

Эффективность (efficiency) использования параллельным алгоритмом процессоров при решении задачи определяется соотношением Ep(n)=T1(n)/(pTp(n))=Sp(n)/p (величина эффективности определяет среднюю долю времени выполнения алгоритма, в течение которой процессоры реально задействованы для решения задачи).

Из приведенных соотношений можно показать, что в наилучшем случае Sp(n)=p и Ep(n)=1. При практическом применении данных показателей для оценки эффективности параллельных вычислений следует учитывать два важных момента:

· При определенных обстоятельствах ускорение может оказаться больше числа используемых процессоров Sp(n)>p — в этом случае говорят о существовании сверхлинейного (superlinear) ускорения. Несмотря на парадоксальность таких ситуаций (ускорение превышает число процессоров), на практике сверхлинейное ускорение может иметь место.

Одной из причин такого явления может быть неодинаковость условий выполнения последовательной и параллельной программ. Например, при решении задачи на одном процессоре оказывается недостаточно оперативной памяти для хранения всех обрабатываемых данных и тогда становится необходимым использование более медленной внешней памяти (в случае же использования нескольких процессоров оперативной памяти может оказаться достаточно за счет разделения данных между процессорами). Еще одной причиной сверхлинейного ускорения может быть нелинейный характер зависимости сложности решения задачи от объема обрабатываемых данных. Так, например, известный алгоритм пузырьковой сортировки характеризуется квадратичной зависимостью количества необходимых операций от числа упорядочиваемых данных. Как результат, при распределении сортируемого массива между процессорами может быть получено ускорение, превышающее число процессоров. Источником сверхлинейного ускорения может быть и различие вычислительных схем последовательного и параллельного методов,

· При внимательном рассмотрении можно обратить внимание, что попытки повышения качества параллельных вычислений по одному из показателей (ускорению или эффективности) могут привести к ухудшению ситуации по другому показателю, ибо показатели качества параллельных вычислений являются часто противоречивыми. Так, например, повышение ускорения обычно может быть обеспечено за счет увеличения числа процессоров, что приводит, как правило, к падению эффективности. И наоборот, повышение эффективности достигается во многих случаях при уменьшении числа процессоров (в предельном случае идеальная эффективность Ep(n)=1 легко обеспечивается при использовании одного процессора). Как результат, разработка методов параллельных вычислений часто предполагает выбор некоторого компромиссного варианта с учетом желаемых показателей ускорения и эффективности.

При выборе надлежащего параллельного способа решения задачи может оказаться полезной оценка стоимости (cost) вычислений, определяемой как произведение времени параллельного решения задачи и числа используемых процессоров Cp=pTp.

В связи с этим можно определить понятие стоимостно-оптимального (cost-optimal) параллельного алгоритма как метода, стоимость которого является пропорциональной времени выполнения наилучшего последовательного алгоритма.

Далее для иллюстрации введенных понятий в следующем пункте будет рассмотрен учебный пример решения задачи вычисления частных сумм для последовательности числовых значений. Кроме того, данные показатели будут использоваться для характеристики эффективности всех рассматриваемых в лекциях 6 – 11 параллельных алгоритмов при решении ряда типовых задач вычислительной математики.

Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:

Источник: studopedia.ru