Презентация на тему: Оценка эффективности параллельных вычислений

Оценка эффективности параллельных вычислений
Содержание
Показатели эффективности
Ускорение
Абсолютное и относительное ускорение
Линейное и сверхлинейное ускорение
Эффективность
Ускорение vs эффективность
Стоимость вычислений
Можно ли достичь max параллелизма?
Закон Амдала
Закон Амдала
Закон Амдала
Закон Амдала
Закон Амдала
Закон Густафсона
Закон Густафсона
Закон Густафсона
Законы Амдала и Густафсона
Масштабируемость алгоритмов
Анализ масштабируемости
Анализ масштабируемости
Анализ масштабируемости
Заключение
1/24
Средняя оценка: 4.9/5 (всего оценок: 33)
Код скопирован в буфер обмена
Скачать (540 Кб)
1

Первый слайд презентации: Оценка эффективности параллельных вычислений

В наш век передовой техники неэффективность и непроизводительность есть грех перед Святым Духом. О. Хаксли

Изображение слайда
2

Слайд 2: Содержание

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

Изображение слайда
3

Слайд 3: Показатели эффективности

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

Изображение слайда
4

Слайд 4: Ускорение

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

Изображение слайда
5

Слайд 5: Абсолютное и относительное ускорение

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

Изображение слайда
6

Слайд 6: Линейное и сверхлинейное ускорение

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

Изображение слайда
7

Слайд 7: Эффективность

7 Эффективность ( efficiency ) – средняя доля времени выполнения параллельного алгоритма, в течение которого процессоры реально используются для решения задачи. _

Изображение слайда
8

Слайд 8: Ускорение vs эффективность

8 Ускорение и эффективность – 2 стороны одной медали: попытки повышения качества параллельных вычислений по одному из показателей может привести к ухудшению качества по другому показателю.

Изображение слайда
9

Слайд 9: Стоимость вычислений

9 Стоимость (cost) параллельных вычислений Стоимостно-оптимальный ( cost - optimal ) параллельный алгоритм – алгоритм, стоимость которого является пропорциональной времени выполнения наилучшего последовательного алгоритма.

Изображение слайда
10

Слайд 10: Можно ли достичь max параллелизма?

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

Изображение слайда
11

Слайд 11: Закон Амдала

11 Задает связь между ожидаемым ускорением параллельных реализаций алгоритма и последовательным алгоритмом в предположении, что размер задачи остается постоянным. Пусть f – доля последовательных вычислений в алгоритме. Тогда т.е. Джин Амдал (р. 1922)

Изображение слайда
12

Слайд 12: Закон Амдала

12 Покраска забора (300 досок) Подготовка – 30 мин. НЕ распараллеливается Покраска (одной доски) – 1 мин. РАСПАРАЛЛЕЛИВАЕТСЯ Уборка – 30 мин. НЕ распараллеливается Количество маляров Время покраски 1 30 + 300/1 + 30 = 360 2 30 + 300/2 + 30 = 210 10 30 + 300/10 + 30 = 90 100 30 + 300/100 + 30 = 63 1000 30 + 300/1000 + 30  60 1000000 30 + 300/1000000 + 30  60 

Изображение слайда
13

Слайд 13: Закон Амдала

13 Покраска забора (300 досок) Подготовка – 30 мин. НЕ распараллеливается Покраска (одной доски) – 1 мин. РАСПАРАЛЛЕЛИВАЕТСЯ Уборка – 30 мин. НЕ распараллеливается Количество маляров Время покраски 1 30 + 300/1 + 30 = 360 2 30 + 300/2 + 30 = 210 10 30 + 300/10 + 30 = 90 100 30 + 300/100 + 30 = 63 1000 30 + 300/1000 + 30  60 1000000 30 + 300/1000000 + 30  60 

Изображение слайда
14

Слайд 14: Закон Амдала

14 Ускорение параллельной программы зависит не от количества процессоров, а величины последовательной части программы. Количество процессоров Ускорение Параллельная часть

Изображение слайда
15

Слайд 15: Закон Амдала

15

Изображение слайда
16

Слайд 16: Закон Густафсона

16 Закон Амдала предполагает, что количество процессоров и доля параллельной части программы независимы, что не совсем верно. Как правило, задача с фиксированным объемом данных не запускается на различном количестве процессоров (за исключением академических исследований), а объем данных изменяется в соответствии с количеством процессоров. Вместо вопроса об ускорении на p процессорах рассмотрим вопрос о замедлении вычислений при переходе на один процессор. Дж. Густафсон (р. 1955) Запуск на параллельном процессоре f 1- f f (1- f )/ p 1 p Запуск на последовательном процессоре f' 1- f' f' ( 1- f' )* p 1 p Гипотетический запуск на последовательном процессоре Запуск на параллельном процессоре

Изображение слайда
17

Слайд 17: Закон Густафсона

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

Изображение слайда
18

Слайд 18: Закон Густафсона

18

Изображение слайда
19

Слайд 19: Законы Амдала и Густафсона

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

Изображение слайда
20

Слайд 20: Масштабируемость алгоритмов

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

Изображение слайда
21

Слайд 21: Анализ масштабируемости

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

Изображение слайда
22

Слайд 22: Анализ масштабируемости

22 Если сложность решаемой задачи является фиксированной ( T 1 =const ), то при росте числа процессоров эффективность, как правило, будет убывать за счет роста накладных расходов T 0. При фиксации числа процессоров эффективность использования процессоров можно улучшить путем повышения сложности решаемой задачи T 1. При увеличении числа процессоров в большинстве случаев можно обеспечить определенный уровень эффективности при помощи соответствующего повышения сложности решаемых задач.

Изображение слайда
23

Слайд 23: Анализ масштабируемости

23 Пусть E = const – это желаемый уровень эффективности выполняемых вычислений. Тогда Данную зависимость n=F(p) между сложностью решаемой задачи и числом процессоров называют функцией изоэффективности ( isoefficiency function ).

Изображение слайда
24

Последний слайд презентации: Оценка эффективности параллельных вычислений: Заключение

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

Изображение слайда