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

Смотреть слайды в полном размере
Презентация Характеристики параллельных алгоритмов


Вашему вниманию предлагается презентация на тему «Характеристики параллельных алгоритмов», с которой можно предварительно ознакомиться, просмотреть текст и слайды к ней, а так же, в случае, если она вам подходит - скачать файл для редактирования или печати.

Презентация содержит 57 слайдов и доступна для скачивания в формате ppt. Размер скачиваемого файла: 546.50 KB

Просмотреть и скачать

Pic.1
Характеристики параллельных алгоритмов Судаков А. А. “Параллельные и распределенные вычисления” Лекц
Характеристики параллельных алгоритмов Судаков А. А. “Параллельные и распределенные вычисления” Лекция 13
Pic.2
План Распараллеливание Характеристики алгоритмов Основные теоремы Факторы снижения эффективности рас
План Распараллеливание Характеристики алгоритмов Основные теоремы Факторы снижения эффективности распареллеливания
Pic.3
Алгоритмы Алгоритм – набор действий, которые необходимо выполнить для решения задачи Последовательны
Алгоритмы Алгоритм – набор действий, которые необходимо выполнить для решения задачи Последовательный алгоритм – решение задачи на одном процессоре Параллельный алгоритм – решение задачи на одновременно работающих процессорах Распараллеливание – какие операции должен выполнить каждый процессор параллельной системы
Pic.4
Декомпозиция, Связь, Синхронизация Декомпозиция – разбиение задачи на составные части Декомпозиция д
Декомпозиция, Связь, Синхронизация Декомпозиция – разбиение задачи на составные части Декомпозиция данных Декомпозиция функций Комбинированная декомпозиция Связь – взаимодействия между составными частями задачи Синхронизация – обеспечение того, что в некоторый момент все процессоры находятся в строго определенном состоянии
Pic.5
Эффективность распараллеливания Единственная цель распараллеливания – уменьшение времени вычислений
Эффективность распараллеливания Единственная цель распараллеливания – уменьшение времени вычислений Не все задачи одинаково эффективно распараллеливаются Задачи теоретического анализа найти оптимальный метод распараллеливания для данного алгоритма Определить насколько та или иная схема эффективна
Pic.6
Модель Система с p процессорами Процессоры могут взаимодействовать между собой В модели с общей памя
Модель Система с p процессорами Процессоры могут взаимодействовать между собой В модели с общей памятью каждый процессор может обращаться независимо к каждой ячейке памяти При обращении к одной и той же ячейке на запись могут возникать конфликты В модели с распределенной памятью Каждые 2 процессора могут взаимодействовать между собой
Pic.7
Характеристики алгоритмов Время вычисления на одном процессоре Время вычисления на p процессорах Кол
Характеристики алгоритмов Время вычисления на одном процессоре Время вычисления на p процессорах Количество операций последовательного алгоритма N1 Количество операций параллельного алгоритма Np Время выполнения одной арифметической операции
Pic.8
Характеристики эффективности распараллеливания Коэффициент ускорения Во сколько раз время параллельн
Характеристики эффективности распараллеливания Коэффициент ускорения Во сколько раз время параллельный алгоритм быстрее Идеальное ускорение Идеальное ускорение = количеству процессоров Коэффициент эффективности Отношение полученного ускорения к идеальному Какой процент процессоров работает Коэффициент избыточности Параллельный алгоритм может потребовать дополнительных операций Качество распараллеливания Произведение всех коэффициентов
Pic.9
Характеристики системы обмена информацией Время передачи единицы информации Время начальной задержки
Характеристики системы обмена информацией Время передачи единицы информации Время начальной задержки Латентность Время установления связи Отношение между временем обработки и временем передачи единицы информации Отношение между временем обработки единицы информации и временем установления связи
Pic.10
Масштабируемость (количество операций алгоритма)‏ Программы (алгоритмы) работают со входными данными
Масштабируемость (количество операций алгоритма)‏ Программы (алгоритмы) работают со входными данными Чем больше данных, тем дольше они будут обрабатываться Масштабируемость – во сколько раз возрастет время выполнения алгоритма при увеличении количества данных
Pic.11
Характеристики масштабируемости Характерная размерность задачи Количество входных данных Количество
Характеристики масштабируемости Характерная размерность задачи Количество входных данных Количество операций алгоритма Нотация большого O Как ведет себя количество N(n) при стремлении объема входных данных к бесконечности
Pic.12
Примеры характерных размерностей Количество элементов массива n Размер квадратной матрицы nxn
Примеры характерных размерностей Количество элементов массива n Размер квадратной матрицы nxn
Pic.13
Примеры масштабируемости
Примеры масштабируемости
Pic.14
Другие характеристики Производительность системы Цена алгоритма Суммарные затраты процессорного врем
Другие характеристики Производительность системы Цена алгоритма Суммарные затраты процессорного времени
Pic.15
Основные свойства параллельных алгоритмов На сколько вообще можно ускорить вычисления за счет паралл
Основные свойства параллельных алгоритмов На сколько вообще можно ускорить вычисления за счет параллельной обработки? Какое оптимальное количество процессоров ? …
Pic.16
Граф операций Граф операции-аргументы Вершины графа – выполняемые операции Дуги – какие результаты п
Граф операций Граф операции-аргументы Вершины графа – выполняемые операции Дуги – какие результаты предыдущих операций используются на следующем этапе Результаты операций соответствуют вершинам
Pic.17
Постановка задачи в терминах графа Последовательности операций соответствует путь на графе Параллель
Постановка задачи в терминах графа Последовательности операций соответствует путь на графе Параллельно могут быть выполнены те операции, между которыми нет пути на графе Каждой схеме распараллеливания на p процессоров соответствует расписание: Для операции i Выбирается процессор Pi В момент времени ti Задача: Найти оптимальное расписание для распараллеливания
Pic.18
Пример расписания (общая память)‏ Момент времени 1 H=(операция 1:загрузить а, процессор 1, момент1 )
Пример расписания (общая память)‏ Момент времени 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 )‏
Pic.19
Ограничения на расписание В один и тот же момент времени один процессор не может выполнять разные оп
Ограничения на расписание В один и тот же момент времени один процессор не может выполнять разные операции Если для выполнения следующей операции должен быть готов результат предыдущей Момент выполнения следующей операции должен быть больше момента выполнения предыдущей операции
Pic.20
Определение времени выполнения параллельного алгоритма Время выполнения соответствует максимально дл
Определение времени выполнения параллельного алгоритма Время выполнения соответствует максимально длинному пути графа Соответствует максимально возможному моменту времени, когда была назначена операция + время выполнения операции Для практики интересно минимальное время при данной схеме вычислений Минимальное время для всех схем вычислений Минимально возможное время при неограниченном количестве процессоров
Pic.21
Некоторые свойства параллельных алгоритмов Минимальное время выполнения параллельного алгоритма соот
Некоторые свойства параллельных алгоритмов Минимальное время выполнения параллельного алгоритма соответствует максимальной длине пути (диаметру) графа Для любого количества процессоров справедлива оценка времени выполнения
Pic.22
Доказательство 2 Пусть есть расписание для получения минимально возможного времени пусть оно соответ
Доказательство 2 Пусть есть расписание для получения минимально возможного времени пусть оно соответствует P процессорам Пусть оно требует времени T∞ Пусть каждый последовательный шаг этого расписания начинается в момент времени ti и всего шагов N∞ Пусть на каждом шаге выполняется ni операций Общее время выполнения равно
Pic.23
Доказательство 2 (продолжение)‏
Доказательство 2 (продолжение)‏
Pic.24
Доказательство 2 (продолжение)‏ Время выполнения алгоритма на p процессорах на i-м шаге Оценим время
Доказательство 2 (продолжение)‏ Время выполнения алгоритма на p процессорах на i-м шаге Оценим время выполнения всего алгоритма на p процессорах сверху Доказано
Pic.25
Другие свойства Можно показать, что максимально возможное ускорение при неизменном количестве операц
Другие свойства Можно показать, что максимально возможное ускорение при неизменном количестве операций равно количеству процессоров Если количество процессоров равно T1/T∞ то время выполнения параллельного алгоритма не будет больше чем в 2 раза превышать оптимальное время выполнения при оптимальном расписании
Pic.26
Использование описания с помощью графов Вычислительную схему необходимо выбирать с графом минимально
Использование описания с помощью графов Вычислительную схему необходимо выбирать с графом минимального диаметра (минимальное время наиболее длинной последовательной операции)‏ Оценочное оптимальное количество процессоров определяется величиной Максимальное время выполнения можно оценить Удобно использовать для формальной оценки эффективности известных вычислительных схем
Pic.27
Факторы ограничения и повышения производительности Гипотеза Минского – принципиальная непараллельнос
Факторы ограничения и повышения производительности Гипотеза Минского – принципиальная непараллельность алгоритма Закон Амдала – наличие принципиально последовательных участков Закон Густафсона – линейное ускорение Гетерогенность – дисбаланс нагрузки Сверхлинейное ускорение – аппаратное и алгоритмическое
Pic.28
Гипотеза Минского Пусть программа имеет p последовательных участков Пусть переход на тот или другой
Гипотеза Минского Пусть программа имеет p последовательных участков Пусть переход на тот или другой участок выполняется путем бинарного ветвления Всего выполнится участков программы Если всю программу выполнять на p процессорах, то ускорение будет не больше, чем Для некоторых эффективных последовательных алгоритмов гипотеза справедлива
Pic.29
Закон Амдала (Amdahl, 1967)‏ Наличие последовательных участков приводит к существенному снижению про
Закон Амдала (Amdahl, 1967)‏ Наличие последовательных участков приводит к существенному снижению производительности Пусть есть система из p процессоров Пусть есть алгоритм, который состоит из участков, которые выполняются параллельно и участков, которые выполняются последовательно Пусть доля последовательных частей равна α Тогда доля параллельных частей равна (1- α)‏
Pic.30
Иллюстрация закона Амдаля
Иллюстрация закона Амдаля
Pic.31
Оценка времени выполнения Время выполнения последовательного алгоритма Время выполнения последовател
Оценка времени выполнения Время выполнения последовательного алгоритма Время выполнения последовательной части параллельного алгоритма Время выполнения параллельной части алгоритма на p процессорах Время выполнения всего параллельного алгоритма
Pic.32
Коэффициент ускорения и эффективность Ускорение Эффективность Время выполнения на паракомпьютере Опт
Коэффициент ускорения и эффективность Ускорение Эффективность Время выполнения на паракомпьютере Оптимальное количество процессоров
Pic.33
Графики зависимостей
Графики зависимостей
Pic.34
Примеры закона Амдала Централизованная схема вычислений Симметричная мультипроцессорная система И др
Примеры закона Амдала Централизованная схема вычислений Симметричная мультипроцессорная система И другие суперкомпьютеры Векторные, конвейерные процессоры Обмен данными
Pic.35
Централизованная схема Главный процессор раздает рабочим задачу Рабочие выполняют задачу и возвращаю
Централизованная схема Главный процессор раздает рабочим задачу Рабочие выполняют задачу и возвращают результат главному процессору Главный процессор – узкое место – существенно последовательная часть алгоритма Главный процессор в один момент времени может обработать только данные с одного рабочего
Pic.36
SMP система Шина не может передавать данные от нескольких процессоров одновременно Шина – существенн
SMP система Шина не может передавать данные от нескольких процессоров одновременно Шина – существенно последовательная часть
Pic.37
Конвейер Пока конвейер не заполнен параллельной обработки нет Заполнение конвейера – существенно пос
Конвейер Пока конвейер не заполнен параллельной обработки нет Заполнение конвейера – существенно последовательная часть алгоритма
Pic.38
Закон Густафсона Другая формулировка закона Амдала Пусть параллельный алгоритм выполняется за время
Закон Густафсона Другая формулировка закона Амдала Пусть параллельный алгоритм выполняется за время Tp Пусть β – доля существенно последовательных операций параллельного алгоритма, тогда (1- β) – доля алгоритма, которая выполняется параллельно на p процессорах
Pic.39
Оценка времени для закона Густафсона Время параллельной обработки Время последовательной обработки (
Оценка времени для закона Густафсона Время параллельной обработки Время последовательной обработки (параллельная часть выполняется в p раз медленнее)‏ Ускорение Получили линейную масштабируемость
Pic.40
Связь или противоречие? Используются разные параметры Амдал – доля последовательных операций последо
Связь или противоречие? Используются разные параметры Амдал – доля последовательных операций последовательного алгоритма Густафсон – доля последовательных операций параллельного алгоритма Связь между параметрами Доля последовательных вычислений зависит от количества процессоров и объема данных с которыми работает алгоритм! При увеличении количества данных, с которыми работает алгоритм часто количество операций распараллеливаемой части растет быстрее, чем количество операций последовательной части и в явном виде закон Густафсона более применим Для быстрых алгоритмов с малым количеством операций в явном виде лучше подходит закон Амдала
Pic.41
Практическое применение законов Амдала и Густафсона При очень малом количестве последовательных опер
Практическое применение законов Амдала и Густафсона При очень малом количестве последовательных операций возможно очень большое ускорение при очень большом количестве процессоров При увеличении объемов данных с которыми работает алгоритм эффекимвность распараллеливания растет
Pic.42
Гетерогенность Гомогенная система – все процессоры одинаковы Гетерогенная система – процессоры разны
Гетерогенность Гомогенная система – все процессоры одинаковы Гетерогенная система – процессоры разные Большинство алгоритмов рассчитаны на гомогенную систему
Pic.43
Дисбаланс нагрузки Если алгоритм, рассчитанный на гомогенную систему запустить на гетерогенной, то Б
Дисбаланс нагрузки Если алгоритм, рассчитанный на гомогенную систему запустить на гетерогенной, то Более быстрые процессоры выполнят свою работу быстрее Более медленные процессоры будут работать дольше Время выполнения такой параллельной программы будет определяться самым медленным процессором!!! Эффективность распараллеливания падает – часть процессоров простаивает
Pic.44
Балансировка нагрузки Для решения проблемы используют балансировку нагрузки Статическая – на этапе з
Балансировка нагрузки Для решения проблемы используют балансировку нагрузки Статическая – на этапе запуска задачи учитывается производительность и загруженность Динамическая – балансировка выполняется в процессе работы
Pic.45
Сверхлинейное ускорение Сверхлинейное ускорение – ускорение большее, чем количество процессоров Согл
Сверхлинейное ускорение Сверхлинейное ускорение – ускорение большее, чем количество процессоров Согласно рассмотренной теории – не возможно Просто учли не все варианты На практике встречается ! Аппаратное сверхлинейное ускорение Алгоритмическое сверхлинейное ускорение
Pic.46
Аппаратное сверхлинейное ускорение Возможно, если процессоры параллельной программы выполняют паралл
Аппаратное сверхлинейное ускорение Возможно, если процессоры параллельной программы выполняют параллельный код с большей производительностью, чем последовательный Каждый процессор параллельной системы может выполнять больше последовательных однотипных операций Работать с меньшими объемами данных (за счет декомпозиции)‏ Данные и код лучше размещаются в оперативной памяти Увеличивается вероятность попадания данных и кода в кэш Очень часто встречается на практике для математических задач!!!
Pic.47
Алгоритмическое сверхлинейное ускорение Возможно, когда для выполнения параллельного алгоритма Необх
Алгоритмическое сверхлинейное ускорение Возможно, когда для выполнения параллельного алгоритма Необходимо выполнить меньше операций Не все операции Часто встречается в задачах поиска, подбора
Pic.48
Пример: подбор пароля Пусть последовательный алгоритм поиска имеет p стадий Стадия1: Перебор географ
Пример: подбор пароля Пусть последовательный алгоритм поиска имеет p стадий Стадия1: Перебор географических названий Стадия2: Перебор нецензурных слов Стадия3: Перебор компьютерных терминов … Последовательный алгоритм выполняет все стадии последовательно и в случае успеха останавливается
Pic.49
Параллельный алгоритм подбора Каждый процессор выполняет свою стадию Процессор1 : Стадия1 Процессор2
Параллельный алгоритм подбора Каждый процессор выполняет свою стадию Процессор1 : Стадия1 Процессор2: Стадия 2 …
Pic.50
Иллюстрация
Иллюстрация
Pic.51
Счастливый случай Как правило пользователи выбирают пароли, чтобы лучше запоминались Если на какой-л
Счастливый случай Как правило пользователи выбирают пароли, чтобы лучше запоминались Если на какой-либо стадии поиска поиск выполняется в нужной категории, то скорее всего пароль будет подобран быстро
Pic.52
Оценка времени последовательного алгоритма Пусть последовательный алгоритм найдет результат в k-й ст
Оценка времени последовательного алгоритма Пусть последовательный алгоритм найдет результат в k-й стадии через время Δt Время выполнения одной стадии t Время выполнения последовательного алгоритма
Pic.53
Оценка времени параллельного алгоритма Процессор параллельной системы, который выполняет k-ю стадию
Оценка времени параллельного алгоритма Процессор параллельной системы, который выполняет k-ю стадию сразу найдет нужный результат за время Δt Все остальные процессоры могут прекратить работу
Pic.54
Ускорение Коэффициент ускорения Сверхлиненейное ускорение возможно, когда ускорение больше p Условие
Ускорение Коэффициент ускорения Сверхлиненейное ускорение возможно, когда ускорение больше p Условие Если успешный подбор будет сразу же после начала стадии На практике очень вероятно, учитывая, как пользователи выбирают пароли
Pic.55
Сравнение факторов ограничения производительности
Сравнение факторов ограничения производительности
Pic.56
Выводы В большинстве случаев ускорение за счет распараллеливания не может быть больше количества про
Выводы В большинстве случаев ускорение за счет распараллеливания не может быть больше количества процессоров Обычно ускорение значительно меньше количества процессоров На практике встречаются ситуации, когда возможно сверхлинейное или близкое к идеальному ускорение При увеличении количества процессоров эффективность распараллеливания падает Для каждой задачи существует свое оптимальное количество процессоров При увеличении количества данных и количества операций алгоритма решения задачи, эффективность распараллеливания увеличивается Если задача эффективно и быстро решается на однопроцессорной системе, то переход к многопроцессорному алгоритму обычно не значительно увеличивает эффективность
Pic.57
Вопросы
Вопросы


Скачать презентацию

Если вам понравился сайт и размещенные на нем материалы, пожалуйста, не забывайте поделиться этой страничкой в социальных сетях и с друзьями! Спасибо!