Параллельные алгоритмы обмена информацией - презентация, доклад, проект скачать

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

Параллельные алгоритмы обмена информацией, слайд №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

Содержание ▲

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

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

Слайд 1

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

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

Слайд 2

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

План Системы с общей и распределенной памятью Обмен в системах с общей памятью Обмен сообщениями Топологии систем Методы передачи информации Параллельные алгоритмы обмена сообщениями

Слайд 3

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

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

Слайд 4

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

Обмен данными в системах с общей памятью Обращения к общим данным Операции Запись в память Чтение из памяти Синхронные и асинхронные операции Операции чтения и записи в память обычно синхронные Процессор точно знает, когда операция заканчивается При эмуляции общей памяти возможны асинхронные операции Get Put Завершение выполнения команды не означает завершения операции Во время выполнения операции процессор может выполнять другие действия

Слайд 5

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

Обмен сообщениями Сообщение (пакет) – неделимая порция информации, которая может быть принята, отправлена и обработана только как единое целое Операции Отправить сообщение Принять сообщение Примеры – отправка и прием данных по сети Синхронные и асинхронные операции Синхронная – завершение команды означает завершение операции Асинхронные - завершение команды не означает завершения операции

Слайд 6

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

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

Слайд 7

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

Некоторые типы топологий

Слайд 8

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

Гиперкуб размерности n Каждый процессор непосредственно связан ровно с n соседями

Слайд 9

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

Гипердерево (fat tree)

Слайд 10

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

Особенности гипердерева В обычном дереве – один корень – узкое место В гипердереве несколько корней Каждый лист связан с несколькими корнями – устранение узких мест

Слайд 11

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

Особенности использования топологий Разные аппаратные средства имеют свою топологию Ethernet – звезда SCI – тор Myrinet, QSnet – гипердерево CrayT3E – решетка Обычно в любой момент времени одновременно могут обмениваться данными друг с другом только два адаптера или процессора Не перекрывающиеся пары процессоров могут обмениваться параллельно

Слайд 12

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

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

Слайд 13

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

Параметры топологий при количестве узлов p

Слайд 14

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

Методы передачи сообщений Сообщение атомарная порция данных Маршрутизация – определение пути с минимальной задержкой для данной топологии Обычно аппаратные средства или операционная система обеспечивает прозрачную маршрутизацию Иногда выгоднее выполнять маршрутизацию в параллельных программах Типы передачи при маршрутизации С буферизацией (store-and-forward) Вначале принимается все сообщение в буфер Потом передается дальше Сквозная передача (cut-through, передача пакетов ) Сообщение передается дальше даже, если оно получено не все Обычно сквозная передача более обеспечивает меньшую задержку Сквозная передача иногда обеспечивает такую же задержку, как и передача с буферизацией из-за перегрузки каналов связи

Слайд 15

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

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

Слайд 16

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

Время передачи сообщения Время передачи сообщения зависит от длины сообщения и времени передачи единицы информации Кроме полезной информации каждое сообщение имеет служебную информацию, которая вносит накладные расходы (overhead) Для сообщения размером m единиц (байт, слов), при времени начальной задержки tc и времени передачи одной единицы данных to Время передачи с буферизацией при длине пути l Время сквозной передачи

Слайд 17

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

Оценка времени Сообщение 1Кбайт Технология Gigabit Ethernet Скорость 1Gbit/с (125 Мбайт/с) Время передачи одного байта 7.6 нс Время начальной задержки 33 мкс Время передачи сообщения ~42 мкс Процессор 1 GFlops 1000 операций – 1мкс Время передачи значительно больше времени обработки данных

Слайд 18

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

Принцип привилегированной передачи Для повышения скорости вычислений самая медленна операция должна выполняться по возможности раньше Передача информации – самая медленная операция Принцип Send-ahead – как только появляется возможность передавать данные это необходимо делать

Слайд 19

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

Параллельные алгоритмы обмена сообщениями Передача сообщения от одного процессора другому Передача сообщения от одного процессора всем (широковещательный режим от одного всем) Передача сообщений от всех процессоров одному (аккумуляция, редукция) Передача сообщения от всех процессоров всем Обобщенная передача сообщений от одного процессора всем (scatter) Обобщенная передача от всех процессоров одному (gather) Обобщенная передача от всех всем (allgather)

Слайд 20

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

Предача от одного процессора другому send(p,m) — передача повідомлення m процесору p; recv(p,m) — прийом повідомлення з процесора p у масив m.

Слайд 21

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

Иллюстрация (сообщение 1000 байт) Тор имеет наилучшую масштабируемость при передаче с буферизацией Многие технологии его используют

Слайд 22

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

Рассылка от одного всем и редукция Одна машина передает данные всем – рассылка Все машины передают данные одной и одна выполняет операцию с этими данными - редукция

Слайд 23

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

Централизованная схема рассылки и редукции Один процессор – главный Остальные рабочие Рассылка один процессор по очереди передает данные всем Редукция – все процессоры передают данные одному Время Не эффективно!

Слайд 24

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

Эффективный способ широковещательной рассылки Процессор 1 имеет данные, которые нужно передать всем остальным Топология гиперкуб – принцип сдваивания (12) [тепер процесори 1 і 2 містять дані] (13), (24) [тепер процесори 1, 2, 3, 4 містять дані] (15), (26), (37), (48) [тепер всі процесори містять дані]

Слайд 25

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

Широковещательная передача в модели бинарного дерева (1,2) (1,3)(2,4) (2,5)(3,6) (3,7)

Слайд 26

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

Эффективность широковещательной передачи для разных топологий

Слайд 27

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

Графическая иллюстрация Самая эффективная топология – шина Тор и гиперкуб почти не отличаются bcast(p,m) здійснює широкомовну передачу повідомлення m з вузла p. Все процессоры вызывают эту функцию

Слайд 28

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

Аккумуляция и редукция на одном узле Редукция на узле 1 Для гиперкуба (21, d1+=d2: d1=d1+d2), (43, d3+=d4: d3=d3+d4), (65, d5+=d6: d5=d5+d6), (87, d7+=d8: d7=d7+d8) (31, d1=d1+d3: d1=d1+d2+d3+d4), (75, d5=d5+d7: d5=d5+d6+d7+d8) (51, d1=d1+d5: d1=d1+d2+d3+d4+d5+d6+d7+d8)

Слайд 29

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

Особенность редукции Суммирование в результате выполняется в нужном порядке Можно реализовать любую функцию со свойствами ассоциативности Перемножение матриц

Слайд 30

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

Обобщенная передача от всех всем Каждый процессор имеет свое сообщение, его необходимо передать остальным Рассмотрим задачу для гиперкуба i-й процессор имеет данные di

Слайд 31

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

Схема (12, d1d2), (34, d3d4), (56, d5d6), (78, d7d8) (13, d1,d2d3,d4), (24, d1,d2d3,d4), (57, d5,d6d7,d8), (68, d5,d6d7,d8) (15, d1,d2,d3,d4d5,d6,d7,d8), (26, d1,d2,d3,d4d5,d6,d7,d8), (37, d1,d2,d3,d4d5,d6,d7,d8), (48, d1,d2,d3,d4d5,d6,d7,d8) На каждом этапе передается в 2 раза больше данных

Слайд 32

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

Время передачи

Слайд 33

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

Иллюстрация Гиперкуб показывает наилучшие результаты

Слайд 34

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

Обощенная редукция 12, d1+=d2, d2=d2+d1), (34, d3+=d4, d4=d3+d4), (56, d5+=d6, d6=d5+d6), (78, d7+=d8, d8=d7+d8) (13, d1+=d3, d3=d1+d3), (24, d2+=d4, d4=d2+d4), (57, d5+=d7, d7=d7+d5), (68, d6+=d8, d8=d6+d8) (15, d1+=d5, d5=d5+d1), (26, d2+=d6, d6=d2+d6), (37, d3+=d7, d7=d3+d7), (48, d4+=d8, d8=d4+d8)

Слайд 35

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

Обобщенная передача от одного всем Пусть один процессор имеет p сообщений Каждое из этих сообщений необходимо прислать своему процессору dk –> k-мк процессору

Слайд 36

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

Эффективная схема (15, d5,d6,d7,d85) (13, d3,d43), (57, d7,d87) (12, d22), (34, d44), (56, d66), (78, d88)

Слайд 37

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

Обобщенная передача от всех одному (21, d21), (43, d43), (65, d65), (87, d87) (31, d3,d41), (75, d7,d85) (51, d5,d6,d7,d81)

Слайд 38

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

Обобщенный обмен сообщениями Каждый процессор имеет свое сообщение для отправки на другой процессор Сообщение dij вначале было на процессоре i и должно быть отправлено на процессор j

Слайд 39

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

Схема для гиперкуба (15: d15,d16,d17,d185; d51,d52,d53,d541), (26: d25,d26,d27,d286; d61,d62,d63,d642), (37: d35,d36,d37,d387; d71,d72,d73,d743), (48: d45,d46,d47,d488; d81,d82,d83,d844) (13: d13,d14,d53,d543; d31,d32,d71,d721), (24: d23,d24,d63,d644; d41,d42,d81,d822), (57: d17,d18,d57,d587; d35,d36,d75,d765), (68: d27,d28,d67,d688; d45,d46,d86,d876) (12: d12,d32,d52,d722; d21,d41,d61,d811), (34: d14,d34,d54,d744; d23,d43,d63,d833), (56: d16,d36,d56,d766; d25,d45,d65,d855), (78: d18,d38,d58,d788; d27,d47,d67,d877)