Построение оценок производительности и эффективности параллельных компьютеров. Законы Адмала, Густавсона-Барсиса

Июль 24, 2022

Главная
Математика
Построение оценок производительности и эффективности параллельных компьютеров. Законы Адмала, Густавсона-Барсиса

Содержание

2. Содержание Показатели эффективности параллельного алгоритма Ускорение Эффективность Стоимость Оценка максимально достижимого параллелизма Закон Амдала Закон Густафсона
3. Показатели эффективности Ускорение относительно последовательного выполнения вычислений Эффективность использования процессоров Стоимость вычислений
4. Ускорение Ускорение (speedup), получаемое при использовании параллельного алгоритма для p процессоров, по сравнению с последовательным вариантом
5. Абсолютное и относительное ускорение Величину ускорения называют абсолютной, если в качестве T1 берется время выполнения наилучшего
6. Линейное и сверхлинейное ускорение Линейное (linear) или идеальное (ideal) ускорение имеет место при Sp=p. Сверхлинейное (superlinear)
7. Эффективность Эффективность (efficiency) – средняя доля времени выполнения параллельного алгоритма, в течение которого процессоры реально используются
8. Ускорение vs эффективность Ускорение и эффективность – 2 стороны одной медали: попытки повышения качества параллельных вычислений
9. Стоимость вычислений Стоимость (cost) параллельных вычислений Стоимостно-оптимальный (cost-optimal) параллельный алгоритм – алгоритм, стоимость которого является пропорциональной
10. Можно ли достичь max параллелизма? Получение идеальных величин Sp=p для ускорения и Ep=1 для эффективности может
11. Закон Амдала Задает связь между ожидаемым ускорением параллельных реализаций алгоритма и последовательным алгоритмом в предположении, что
12. Закон Амдала Покраска забора (300 досок) Подготовка – 30 мин. НЕ распараллеливается Покраска (одной доски) –
13. Закон Амдала Покраска забора (300 досок) Подготовка – 30 мин. НЕ распараллеливается Покраска (одной доски) –
14. Закон Амдала Ускорение параллельной программы зависит не от количества процессоров, а величины последовательной части программы.
15. Закон Амдала
16. Закон Густафсона Закон Амдала предполагает, что количество процессоров и доля параллельной части программы независимы, что не
17. Закон Густафсона Закон Амдала предполагает, что количество процессоров и доля параллельной части программы независимы, что не
18. Закон Густафсона
19. Законы Амдала и Густафсона Уменьшение времени выполнения vs увеличение объема решаемой задачи Увеличение объема решаемой задачи
20. Масштабируемость алгоритмов Параллельный алгоритм называют масштабируемым (scalable), если при росте числа процессоров он обеспечивает увеличение ускорения
21. Анализ масштабируемости Накладные расходы Время решения задачи Ускорение Эффективность
22. Анализ масштабируемости Если сложность решаемой задачи является фиксированной (T1=const), то при росте числа процессоров эффективность, как
23. Анализ масштабируемости Пусть E=const – это желаемый уровень эффективности выполняемых вычислений. Тогда Данную зависимость n=F(p) между
25. Скачать презентацию

Слайд 2

Содержание
Показатели эффективности параллельного алгоритма
Ускорение
Эффективность
Стоимость
Оценка максимально достижимого параллелизма
Закон Амдала
Закон Густафсона
Анализ масштабируемости

параллельного алгоритма

Слайд 3

Показатели эффективности
Ускорение относительно последовательного выполнения вычислений
Эффективность использования процессоров
Стоимость вычислений

Слайд 4

Ускорение
Ускорение (speedup), получаемое при использовании параллельного алгоритма для p процессоров, по

сравнению с последовательным вариантом выполнения вычислений:
n – параметр вычислительной сложности решаемой задачи (например, количество входных данных задачи)

Слайд 5

Абсолютное и относительное ускорение
Величину ускорения называют абсолютной, если в качестве

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

Слайд 6

Линейное и сверхлинейное ускорение
Линейное (linear) или идеальное (ideal) ускорение имеет

место при Sp=p.
Сверхлинейное (superlinear) ускорение имеет место при Sp>p.
Неравноправность выполнения последовательной и параллельной программ (например, недостаток оперативной памяти).
Нелинейный характер зависимости сложности решения задачи от объема обрабатываемых данных.
Различие вычислительных схем последовательного и параллельного методов.

Слайд 7

Эффективность
Эффективность (efficiency) – средняя доля времени выполнения параллельного алгоритма, в течение

которого процессоры реально используются для решения задачи.
_

Слайд 8

Ускорение vs эффективность
Ускорение и эффективность – 2 стороны одной медали: попытки

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

Слайд 9

Стоимость вычислений
Стоимость (cost) параллельных вычислений
Стоимостно-оптимальный (cost-optimal) параллельный алгоритм – алгоритм, стоимость

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

Слайд 10

Можно ли достичь max параллелизма?
Получение идеальных величин Sp=p для ускорения и

Ep=1 для эффективности может быть обеспечено не для всех вычислительно трудоемких задач.
Достижению максимального ускорения может препятствовать существование в выполняемых вычислениях последовательных расчетов, которые не могут быть распараллелены.

Слайд 11

Закон Амдала
Задает связь между ожидаемым ускорением параллельных реализаций алгоритма и последовательным

алгоритмом в предположении, что размер задачи остается постоянным.
Пусть f – доля последовательных вычислений в алгоритме. Тогда
т.е.

Джин Амдал
(р. 1922)

Слайд 12

Закон Амдала
Покраска забора (300 досок)
Подготовка – 30 мин. НЕ распараллеливается
Покраска (одной доски)

– 1 мин. РАСПАРАЛЛЕЛИВАЕТСЯ
Уборка – 30 мин. НЕ распараллеливается

∞

Слайд 13

Закон Амдала
Покраска забора (300 досок)
Подготовка – 30 мин. НЕ распараллеливается
Покраска (одной доски)

– 1 мин. РАСПАРАЛЛЕЛИВАЕТСЯ
Уборка – 30 мин. НЕ распараллеливается

∞

Слайд 14

Закон Амдала
Ускорение параллельной программы зависит не от количества процессоров, а величины

последовательной части программы.

Слайд 15

Закон Амдала

Слайд 16

Закон Густафсона
Закон Амдала предполагает, что количество процессоров и доля параллельной части

программы независимы, что не совсем верно.
Как правило, задача с фиксированным объемом данных не запускается на различном количестве процессоров (за исключением академических исследований), а объем данных изменяется в соответствии с количеством процессоров.
Вместо вопроса об ускорении на p процессорах рассмотрим вопрос о замедлении вычислений при переходе на один процессор.

Дж. Густафсон
(р. 1955)

Слайд 17

Закон Густафсона
Закон Амдала предполагает, что количество процессоров и доля параллельной части

Дж. Густафсон
(р. 1955)

Слайд 18

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

Слайд 19

Законы Амдала и Густафсона
Уменьшение времени выполнения vs увеличение объема решаемой задачи
Увеличение объема

решаемой задачи приводит к увеличению доли параллельной части, т.к. последовательная часть не изменяется.

Слайд 20

Масштабируемость алгоритмов
Параллельный алгоритм называют масштабируемым (scalable), если при росте числа процессоров

он обеспечивает увеличение ускорения при сохранении постоянного уровня эффективности использования процессоров.
При анализе масштабируемости необходимо учитывать накладные расходы (total overhead), на организацию взаимодействия процессоров, синхронизацию параллельных вычислений и др.

Слайд 21

Анализ масштабируемости
Накладные расходы
Время решения задачи
Ускорение
Эффективность

Слайд 22

Анализ масштабируемости
Если сложность решаемой задачи является фиксированной (T1=const), то при росте

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

Слайд 23

Анализ масштабируемости
Пусть E=const – это желаемый уровень эффективности выполняемых вычислений. Тогда
Данную

зависимость n=F(p) между сложностью решаемой задачи и числом процессоров называют функцией изоэффективности (isoefficiency function).

Построение оценок производительности и эффективности параллельных компьютеров. Законы Адмала, Густавсона-Барсиса

Содержание

Показатели эффективностиУскорение относительно последовательного выполнения вычисленийЭффективность использования процессоровСтоимость вычислений

УскорениеУскорение (speedup), получаемое при использовании параллельного алгоритма для p процессоров, по

Абсолютное и относительное ускорение Величину ускорения называют абсолютной, если в качестве

Линейное и сверхлинейное ускорение Линейное (linear) или идеальное (ideal) ускорение имеет

ЭффективностьЭффективность (efficiency) – средняя доля времени выполнения параллельного алгоритма, в течение

Ускорение vs эффективностьУскорение и эффективность – 2 стороны одной медали: попытки

Стоимость вычисленийСтоимость (cost) параллельных вычислений Стоимостно-оптимальный (cost-optimal) параллельный алгоритм – алгоритм, стоимость

Можно ли достичь max параллелизма?Получение идеальных величин Sp=p для ускорения и

Закон АмдалаЗадает связь между ожидаемым ускорением параллельных реализаций алгоритма и последовательным

Закон АмдалаПокраска забора (300 досок)Подготовка – 30 мин. НЕ распараллеливаетсяПокраска (одной доски)

Закон АмдалаПокраска забора (300 досок)Подготовка – 30 мин. НЕ распараллеливаетсяПокраска (одной доски)

Закон АмдалаУскорение параллельной программы зависит не от количества процессоров, а величины

Закон Амдала

Закон ГустафсонаЗакон Амдала предполагает, что количество процессоров и доля параллельной части

Закон ГустафсонаЗакон Амдала предполагает, что количество процессоров и доля параллельной части

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

Законы Амдала и ГустафсонаУменьшение времени выполнения vs увеличение объема решаемой задачиУвеличение объема

Масштабируемость алгоритмовПараллельный алгоритм называют масштабируемым (scalable), если при росте числа процессоров

Анализ масштабируемостиНакладные расходыВремя решения задачиУскорениеЭффективность

Анализ масштабируемостиЕсли сложность решаемой задачи является фиксированной (T1=const), то при росте

Анализ масштабируемостиПусть E=const – это желаемый уровень эффективности выполняемых вычислений. ТогдаДанную

Похожие презентации

Показатели эффективности
Ускорение относительно последовательного выполнения вычислений
Эффективность использования процессоров
Стоимость вычислений

Ускорение
Ускорение (speedup), получаемое при использовании параллельного алгоритма для p процессоров, по

Абсолютное и относительное ускорение
Величину ускорения называют абсолютной, если в качестве

Линейное и сверхлинейное ускорение
Линейное (linear) или идеальное (ideal) ускорение имеет

Эффективность
Эффективность (efficiency) – средняя доля времени выполнения параллельного алгоритма, в течение

Ускорение vs эффективность
Ускорение и эффективность – 2 стороны одной медали: попытки

Стоимость вычислений
Стоимость (cost) параллельных вычислений
Стоимостно-оптимальный (cost-optimal) параллельный алгоритм – алгоритм, стоимость

Можно ли достичь max параллелизма?
Получение идеальных величин Sp=p для ускорения и

Закон Амдала
Задает связь между ожидаемым ускорением параллельных реализаций алгоритма и последовательным

Закон Амдала
Покраска забора (300 досок)
Подготовка – 30 мин. НЕ распараллеливается
Покраска (одной доски)

Закон Амдала
Покраска забора (300 досок)
Подготовка – 30 мин. НЕ распараллеливается
Покраска (одной доски)

Закон Амдала
Ускорение параллельной программы зависит не от количества процессоров, а величины

Закон Густафсона
Закон Амдала предполагает, что количество процессоров и доля параллельной части

Закон Густафсона
Закон Амдала предполагает, что количество процессоров и доля параллельной части

Законы Амдала и Густафсона
Уменьшение времени выполнения vs увеличение объема решаемой задачи
Увеличение объема

Масштабируемость алгоритмов
Параллельный алгоритм называют масштабируемым (scalable), если при росте числа процессоров

Анализ масштабируемости
Накладные расходы
Время решения задачи
Ускорение
Эффективность

Анализ масштабируемости
Если сложность решаемой задачи является фиксированной (T1=const), то при росте

Анализ масштабируемости
Пусть E=const – это желаемый уровень эффективности выполняемых вычислений. Тогда
Данную