Характеристики параллельных алгоритмов - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Характеристики параллельных алгоритмов, слайд №1

Характеристики параллельных алгоритмов, слайд №2

Характеристики параллельных алгоритмов, слайд №3

Характеристики параллельных алгоритмов, слайд №4

Характеристики параллельных алгоритмов, слайд №5

Характеристики параллельных алгоритмов, слайд №6

Характеристики параллельных алгоритмов, слайд №7

Характеристики параллельных алгоритмов, слайд №8

Характеристики параллельных алгоритмов, слайд №9

Характеристики параллельных алгоритмов, слайд №10

Характеристики параллельных алгоритмов, слайд №11

Характеристики параллельных алгоритмов, слайд №12

Характеристики параллельных алгоритмов, слайд №13

Характеристики параллельных алгоритмов, слайд №14

Характеристики параллельных алгоритмов, слайд №15

Характеристики параллельных алгоритмов, слайд №16

Характеристики параллельных алгоритмов, слайд №17

Характеристики параллельных алгоритмов, слайд №18

Характеристики параллельных алгоритмов, слайд №19

Характеристики параллельных алгоритмов, слайд №20

Характеристики параллельных алгоритмов, слайд №21

Характеристики параллельных алгоритмов, слайд №22

Характеристики параллельных алгоритмов, слайд №23

Характеристики параллельных алгоритмов, слайд №24

Характеристики параллельных алгоритмов, слайд №25

Характеристики параллельных алгоритмов, слайд №26

Характеристики параллельных алгоритмов, слайд №27

Характеристики параллельных алгоритмов, слайд №28

Характеристики параллельных алгоритмов, слайд №29

Характеристики параллельных алгоритмов, слайд №30

Характеристики параллельных алгоритмов, слайд №31

Характеристики параллельных алгоритмов, слайд №32

Характеристики параллельных алгоритмов, слайд №33

Характеристики параллельных алгоритмов, слайд №34

Характеристики параллельных алгоритмов, слайд №35

Характеристики параллельных алгоритмов, слайд №36

Характеристики параллельных алгоритмов, слайд №37

Характеристики параллельных алгоритмов, слайд №38

Характеристики параллельных алгоритмов, слайд №39

Характеристики параллельных алгоритмов, слайд №40

Характеристики параллельных алгоритмов, слайд №41

Характеристики параллельных алгоритмов, слайд №42

Характеристики параллельных алгоритмов, слайд №43

Характеристики параллельных алгоритмов, слайд №44

Характеристики параллельных алгоритмов, слайд №45

Характеристики параллельных алгоритмов, слайд №46

Характеристики параллельных алгоритмов, слайд №47

Характеристики параллельных алгоритмов, слайд №48

Характеристики параллельных алгоритмов, слайд №49

Характеристики параллельных алгоритмов, слайд №50

Характеристики параллельных алгоритмов, слайд №51

Характеристики параллельных алгоритмов, слайд №52

Характеристики параллельных алгоритмов, слайд №53

Характеристики параллельных алгоритмов, слайд №54

Характеристики параллельных алгоритмов, слайд №55

Характеристики параллельных алгоритмов, слайд №56

Характеристики параллельных алгоритмов, слайд №57

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Характеристики параллельных алгоритмов. Доклад-сообщение содержит 57 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Характеристики параллельных алгоритмов Судаков А.А. “Параллельные и распределенные вычисления” Лекция 13

Слайд 2

Описание слайда:

План Распараллеливание Характеристики алгоритмов Основные теоремы Факторы снижения эффективности распареллеливания

Слайд 3

Описание слайда:

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

Слайд 4

Описание слайда:

Декомпозиция, Связь, Синхронизация Декомпозиция – разбиение задачи на составные части Декомпозиция данных Декомпозиция функций Комбинированная декомпозиция Связь – взаимодействия между составными частями задачи Синхронизация – обеспечение того, что в некоторый момент все процессоры находятся в строго определенном состоянии

Слайд 5

Описание слайда:

Эффективность распараллеливания Единственная цель распараллеливания – уменьшение времени вычислений Не все задачи одинаково эффективно распараллеливаются Задачи теоретического анализа найти оптимальный метод распараллеливания для данного алгоритма Определить насколько та или иная схема эффективна

Слайд 6

Описание слайда:

Модель Система с p процессорами Процессоры могут взаимодействовать между собой В модели с общей памятью каждый процессор может обращаться независимо к каждой ячейке памяти При обращении к одной и той же ячейке на запись могут возникать конфликты В модели с распределенной памятью Каждые 2 процессора могут взаимодействовать между собой

Слайд 7

Описание слайда:

Характеристики алгоритмов Время вычисления на одном процессоре Время вычисления на p процессорах Количество операций последовательного алгоритма N1 Количество операций параллельного алгоритма Np Время выполнения одной арифметической операции

Слайд 8

Описание слайда:

Характеристики эффективности распараллеливания Коэффициент ускорения Во сколько раз время параллельный алгоритм быстрее Идеальное ускорение Идеальное ускорение = количеству процессоров Коэффициент эффективности Отношение полученного ускорения к идеальному Какой процент процессоров работает Коэффициент избыточности Параллельный алгоритм может потребовать дополнительных операций Качество распараллеливания Произведение всех коэффициентов

Слайд 9

Описание слайда:

Характеристики системы обмена информацией Время передачи единицы информации Время начальной задержки Латентность Время установления связи Отношение между временем обработки и временем передачи единицы информации Отношение между временем обработки единицы информации и временем установления связи

Слайд 10

Описание слайда:

Масштабируемость (количество операций алгоритма)‏ Программы (алгоритмы) работают со входными данными Чем больше данных, тем дольше они будут обрабатываться Масштабируемость – во сколько раз возрастет время выполнения алгоритма при увеличении количества данных

Слайд 11

Описание слайда:

Характеристики масштабируемости Характерная размерность задачи Количество входных данных Количество операций алгоритма Нотация большого O Как ведет себя количество N(n) при стремлении объема входных данных к бесконечности

Слайд 12

Описание слайда:

Примеры характерных размерностей Количество элементов массива n Размер квадратной матрицы nxn

Слайд 13

Описание слайда:

Примеры масштабируемости

Слайд 14

Описание слайда:

Другие характеристики Производительность системы Цена алгоритма Суммарные затраты процессорного времени

Слайд 15

Описание слайда:

Основные свойства параллельных алгоритмов На сколько вообще можно ускорить вычисления за счет параллельной обработки? Какое оптимальное количество процессоров ? …

Слайд 16

Описание слайда:

Граф операций Граф операции-аргументы Вершины графа – выполняемые операции Дуги – какие результаты предыдущих операций используются на следующем этапе Результаты операций соответствуют вершинам

Слайд 17

Описание слайда:

Постановка задачи в терминах графа Последовательности операций соответствует путь на графе Параллельно могут быть выполнены те операции, между которыми нет пути на графе Каждой схеме распараллеливания на p процессоров соответствует расписание: Для операции i Выбирается процессор Pi В момент времени ti Задача: Найти оптимальное расписание для распараллеливания

Слайд 18

Описание слайда:

Пример расписания (общая память)‏ Момент времени 1 H=(операция 1:загрузить а, процессор 1, момент1 )‏ H=(операция 2:загрузить b, процессор 2, момент1 )‏ H=(операция 3:загрузить c, процессор 3, момент1 )‏ H=(операция 4:загрузить d, процессор 4, момент1 )‏ Момент времени 2 H=(операция 5: а*с, процессор 1, момент2 )‏ H=(операция 6: а*b, процессор 2, момент2 )‏ H=(операция 7: c*d, процессор 3, момент2 )‏ H=(операция 8: b*d, процессор 4, момент2 )‏ Момент времени 3 H=(операция 9: а*с+b*d, процессор 2, момент3 )‏ H=(операция 10: a*d+b*c, процессор 3, момент3 )‏ Момент времени 4 H=(операция 11: а*с+b*d+ a*d+b*c, процессор 3, момент4 )‏

Слайд 19

Описание слайда:

Ограничения на расписание В один и тот же момент времени один процессор не может выполнять разные операции Если для выполнения следующей операции должен быть готов результат предыдущей Момент выполнения следующей операции должен быть больше момента выполнения предыдущей операции

Слайд 20

Описание слайда:

Определение времени выполнения параллельного алгоритма Время выполнения соответствует максимально длинному пути графа Соответствует максимально возможному моменту времени, когда была назначена операция + время выполнения операции Для практики интересно минимальное время при данной схеме вычислений Минимальное время для всех схем вычислений Минимально возможное время при неограниченном количестве процессоров

Слайд 21

Описание слайда:

Некоторые свойства параллельных алгоритмов Минимальное время выполнения параллельного алгоритма соответствует максимальной длине пути (диаметру) графа Для любого количества процессоров справедлива оценка времени выполнения

Слайд 22

Описание слайда:

Доказательство 2 Пусть есть расписание для получения минимально возможного времени пусть оно соответствует P процессорам Пусть оно требует времени T∞ Пусть каждый последовательный шаг этого расписания начинается в момент времени ti и всего шагов N∞ Пусть на каждом шаге выполняется ni операций Общее время выполнения равно

Слайд 23

Описание слайда:

Доказательство 2 (продолжение)‏

Слайд 24

Описание слайда:

Доказательство 2 (продолжение)‏ Время выполнения алгоритма на p процессорах на i-м шаге Оценим время выполнения всего алгоритма на p процессорах сверху Доказано

Слайд 25

Описание слайда:

Другие свойства Можно показать, что максимально возможное ускорение при неизменном количестве операций равно количеству процессоров Если количество процессоров равно T1/T∞ то время выполнения параллельного алгоритма не будет больше чем в 2 раза превышать оптимальное время выполнения при оптимальном расписании

Слайд 26

Описание слайда:

Использование описания с помощью графов Вычислительную схему необходимо выбирать с графом минимального диаметра (минимальное время наиболее длинной последовательной операции)‏ Оценочное оптимальное количество процессоров определяется величиной Максимальное время выполнения можно оценить Удобно использовать для формальной оценки эффективности известных вычислительных схем

Слайд 27

Описание слайда:

Факторы ограничения и повышения производительности Гипотеза Минского – принципиальная непараллельность алгоритма Закон Амдала – наличие принципиально последовательных участков Закон Густафсона – линейное ускорение Гетерогенность – дисбаланс нагрузки Сверхлинейное ускорение – аппаратное и алгоритмическое

Слайд 28

Описание слайда:

Гипотеза Минского Пусть программа имеет p последовательных участков Пусть переход на тот или другой участок выполняется путем бинарного ветвления Всего выполнится участков программы Если всю программу выполнять на p процессорах, то ускорение будет не больше, чем Для некоторых эффективных последовательных алгоритмов гипотеза справедлива

Слайд 29

Описание слайда:

Закон Амдала (Amdahl, 1967)‏ Наличие последовательных участков приводит к существенному снижению производительности Пусть есть система из p процессоров Пусть есть алгоритм, который состоит из участков, которые выполняются параллельно и участков, которые выполняются последовательно Пусть доля последовательных частей равна α Тогда доля параллельных частей равна (1- α)‏

Слайд 30

Описание слайда:

Иллюстрация закона Амдаля

Слайд 31

Описание слайда:

Оценка времени выполнения Время выполнения последовательного алгоритма Время выполнения последовательной части параллельного алгоритма Время выполнения параллельной части алгоритма на p процессорах Время выполнения всего параллельного алгоритма

Слайд 32

Описание слайда:

Коэффициент ускорения и эффективность Ускорение Эффективность Время выполнения на паракомпьютере Оптимальное количество процессоров

Слайд 33

Описание слайда:

Графики зависимостей

Слайд 34

Описание слайда:

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

Слайд 35

Описание слайда:

Централизованная схема Главный процессор раздает рабочим задачу Рабочие выполняют задачу и возвращают результат главному процессору Главный процессор – узкое место – существенно последовательная часть алгоритма Главный процессор в один момент времени может обработать только данные с одного рабочего

Слайд 36

Описание слайда:

SMP система Шина не может передавать данные от нескольких процессоров одновременно Шина – существенно последовательная часть

Слайд 37

Описание слайда:

Конвейер Пока конвейер не заполнен параллельной обработки нет Заполнение конвейера – существенно последовательная часть алгоритма

Слайд 38

Описание слайда:

Закон Густафсона Другая формулировка закона Амдала Пусть параллельный алгоритм выполняется за время Tp Пусть β – доля существенно последовательных операций параллельного алгоритма, тогда (1- β) – доля алгоритма, которая выполняется параллельно на p процессорах

Слайд 39

Описание слайда:

Оценка времени для закона Густафсона Время параллельной обработки Время последовательной обработки (параллельная часть выполняется в p раз медленнее)‏ Ускорение Получили линейную масштабируемость

Слайд 40

Описание слайда:

Связь или противоречие? Используются разные параметры Амдал – доля последовательных операций последовательного алгоритма Густафсон – доля последовательных операций параллельного алгоритма Связь между параметрами Доля последовательных вычислений зависит от количества процессоров и объема данных с которыми работает алгоритм! При увеличении количества данных, с которыми работает алгоритм часто количество операций распараллеливаемой части растет быстрее, чем количество операций последовательной части и в явном виде закон Густафсона более применим Для быстрых алгоритмов с малым количеством операций в явном виде лучше подходит закон Амдала

Слайд 41

Описание слайда:

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

Слайд 42

Описание слайда:

Гетерогенность Гомогенная система – все процессоры одинаковы Гетерогенная система – процессоры разные Большинство алгоритмов рассчитаны на гомогенную систему

Слайд 43

Описание слайда:

Дисбаланс нагрузки Если алгоритм, рассчитанный на гомогенную систему запустить на гетерогенной, то Более быстрые процессоры выполнят свою работу быстрее Более медленные процессоры будут работать дольше Время выполнения такой параллельной программы будет определяться самым медленным процессором!!! Эффективность распараллеливания падает – часть процессоров простаивает

Слайд 44

Описание слайда:

Балансировка нагрузки Для решения проблемы используют балансировку нагрузки Статическая – на этапе запуска задачи учитывается производительность и загруженность Динамическая – балансировка выполняется в процессе работы

Слайд 45

Описание слайда:

Сверхлинейное ускорение Сверхлинейное ускорение – ускорение большее, чем количество процессоров Согласно рассмотренной теории – не возможно Просто учли не все варианты На практике встречается ! Аппаратное сверхлинейное ускорение Алгоритмическое сверхлинейное ускорение

Слайд 46

Описание слайда:

Аппаратное сверхлинейное ускорение Возможно, если процессоры параллельной программы выполняют параллельный код с большей производительностью, чем последовательный Каждый процессор параллельной системы может выполнять больше последовательных однотипных операций Работать с меньшими объемами данных (за счет декомпозиции)‏ Данные и код лучше размещаются в оперативной памяти Увеличивается вероятность попадания данных и кода в кэш Очень часто встречается на практике для математических задач!!!

Слайд 47

Описание слайда:

Алгоритмическое сверхлинейное ускорение Возможно, когда для выполнения параллельного алгоритма Необходимо выполнить меньше операций Не все операции Часто встречается в задачах поиска, подбора

Слайд 48

Описание слайда:

Пример: подбор пароля Пусть последовательный алгоритм поиска имеет p стадий Стадия1: Перебор географических названий Стадия2: Перебор нецензурных слов Стадия3: Перебор компьютерных терминов … Последовательный алгоритм выполняет все стадии последовательно и в случае успеха останавливается

Слайд 49

Описание слайда:

Параллельный алгоритм подбора Каждый процессор выполняет свою стадию Процессор1 : Стадия1 Процессор2: Стадия 2 …

Слайд 50

Описание слайда:

Иллюстрация

Слайд 51

Описание слайда:

Счастливый случай Как правило пользователи выбирают пароли, чтобы лучше запоминались Если на какой-либо стадии поиска поиск выполняется в нужной категории, то скорее всего пароль будет подобран быстро

Слайд 52

Описание слайда:

Оценка времени последовательного алгоритма Пусть последовательный алгоритм найдет результат в k-й стадии через время Δt Время выполнения одной стадии t Время выполнения последовательного алгоритма

Слайд 53

Описание слайда:

Оценка времени параллельного алгоритма Процессор параллельной системы, который выполняет k-ю стадию сразу найдет нужный результат за время Δt Все остальные процессоры могут прекратить работу

Слайд 54

Описание слайда:

Ускорение Коэффициент ускорения Сверхлиненейное ускорение возможно, когда ускорение больше p Условие Если успешный подбор будет сразу же после начала стадии На практике очень вероятно, учитывая, как пользователи выбирают пароли

Слайд 55

Описание слайда:

Сравнение факторов ограничения производительности

Слайд 56

Описание слайда:

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