Презентация Параллельные алгоритмы обмена информацией онлайн

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

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

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

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

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

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

Содержание слайда: Некоторые типы топологий

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

Содержание слайда: Гипердерево (fat tree)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Содержание слайда: Аккумуляция и редукция на одном узле Редукция на узле 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)

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

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

Содержание слайда: Схема (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 раза больше данных

Содержание слайда: Время передачи

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

Содержание слайда: Обощенная редукция 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)

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

Содержание слайда: Эффективная схема (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)

Содержание слайда: Обобщенная передача от всех одному (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)

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

Содержание слайда: Схема для гиперкуба (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)

Содержание слайда: Оценка времени

Содержание слайда: Иллюстрация Наиболее эффективная топология гиперкуб Функция allgather(m)

Содержание слайда: Выводы Для сложных задач обмена наиболее эффективная топология – гиперкуб Для простых – 2D-3D тор

Содержание слайда: Вопросы