Разделы презентаций
- Разное
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Параллельные алгоритмы обмена информацией
Содержание
- 1. Параллельные алгоритмы обмена информацией
- 2. ПланСистемы с общей и распределенной памятьюОбмен в
- 3. Системы с общей и распределенной памятьюОбщая память
- 4. Обмен данными в системах с общей памятьюОбращения
- 5. Обмен сообщениямиСообщение (пакет) – неделимая порция информации,
- 6. Топологии системТопология – структура связей между процессорамиТопологияЛогическая
- 7. Некоторые типы топологийрешетка2D торкубЛинейка (ферма)Бинарное деревозвездаПолный графКольцо
- 8. Гиперкуб размерности nКаждый процессор непосредственно связан ровно с n соседями
- 9. Гипердерево (fat tree)
- 10. Особенности гипердереваВ обычном дереве – один корень
- 11. Особенности использования топологийРазные аппаратные средства имеют свою
- 12. Характеристики топологийДиаметр – максимально возможная длина пути
- 13. Параметры топологий при количестве узлов p
- 14. Методы передачи сообщенийСообщение атомарная порция данныхМаршрутизация –
- 15. Режимы передачиСинхронный режим – передатчик ожидает подтверждения,
- 16. Время передачи сообщенияВремя передачи сообщения зависит от
- 17. Оценка времениСообщение 1КбайтТехнология Gigabit EthernetСкорость 1Gbit/с (125
- 18. Принцип привилегированной передачиДля повышения скорости вычислений самая
- 19. Параллельные алгоритмы обмена сообщениямиПередача сообщения от одного
- 20. Предача от одного процессора другомуsend(p,m) — передача повідомлення
- 21. Иллюстрация (сообщение 1000 байт)Тор имеет наилучшую масштабируемость при передаче с буферизациейМногие технологии его используют
- 22. Рассылка от одного всем и редукцияОдна машина
- 23. Централизованная схема рассылки и редукцииОдин процессор –
- 24. Эффективный способ широковещательной рассылкиПроцессор 1 имеет данные,
- 25. Широковещательная передача в модели бинарного дерева(1,2)(1,3)(2,4)(2,5)(3,6)(3,7)1234567
- 26. Эффективность широковещательной передачи для разных топологий
- 27. Графическая иллюстрацияСамая эффективная топология – шинаТор и
- 28. Аккумуляция и редукция на одном узлеРедукция на
- 29. Особенность редукцииСуммирование в результате выполняется в нужном порядкеМожно реализовать любую функцию со свойствами ассоциативностиПеремножение матриц
- 30. Обобщенная передача от всех всемКаждый процессор имеет
- 31. Схема(1↔2, d1↔d2), (3↔4, d3↔d4), (5↔6, d5↔d6), (7↔8,
- 32. Время передачи
- 33. ИллюстрацияГиперкуб показывает наилучшие результаты
- 34. Обощенная редукция1↔2, d1+=d2, d2=d2+d1), (3↔4, d3+=d4, d4=d3+d4),
- 35. Обобщенная передача от одного всемПусть один процессор
- 36. Эффективная схема(1→5, d5,d6,d7,d8→5) (1→3, d3,d4→3), (5→7,
- 37. Обобщенная передача от всех одному(2→1, d2→1), (4→3,
- 38. Обобщенный обмен сообщениямиКаждый процессор имеет свое сообщение
- 39. Схема для гиперкуба(1↔5: d15,d16,d17,d18→5; d51,d52,d53,d54→1), (2↔6: d25,d26,d27,d28→6;
- 40. Оценка времени
- 41. ИллюстрацияНаиболее эффективная топология гиперкубФункция allgather(m)
- 42. ВыводыДля сложных задач обмена наиболее эффективная топология – гиперкубДля простых – 2D-3D тор
- 43. Вопросы
- 44. Скачать презентанцию
ПланСистемы с общей и распределенной памятьюОбмен в системах с общей памятьюОбмен сообщениямиТопологии системМетоды передачи информацииПараллельные алгоритмы обмена сообщениями
Слайды и текст этой презентации
Слайд 1Параллельные алгоритмы обмена информацией
Судаков А.А.
“Параллельные и распределенные вычисления” Лекция 14
Слайд 3Системы с общей и распределенной памятью
Общая память – все процессоры
могут обращаться к одним и тем же самым данным
Распределенная память
– процессоры не могут обращаться к данным других процессоров непосредственно для доступа к данным других процессоров используется передача этих данных в виде сообщений
Слайд 4Обмен данными в системах с общей памятью
Обращения к общим данным
Операции
Запись
в память
Чтение из памяти
Синхронные и асинхронные операции
Операции чтения и записи
в память обычно синхронныеПроцессор точно знает, когда операция заканчивается
При эмуляции общей памяти возможны асинхронные операции
Get
Put
Завершение выполнения команды не означает завершения операции
Во время выполнения операции процессор может выполнять другие действия
Слайд 5Обмен сообщениями
Сообщение (пакет) – неделимая порция информации, которая может быть
принята, отправлена и обработана только как единое целое
Операции
Отправить сообщение
Принять сообщение
Примеры
– отправка и прием данных по сетиСинхронные и асинхронные операции
Синхронная – завершение команды означает завершение операции
Асинхронные - завершение команды не означает завершения операции
Слайд 6Топологии систем
Топология – структура связей между процессорами
Топология
Логическая – реализуется программно
Физическая
– реализуется аппаратно
Топологии параллельной системы определяют эффективность обмена информацией
Логическая топология
системы обычно соответствует топологии задачи, которая решается (сверху-вниз)Физическая топология – обычно обычно имеющимся в наличии аппаратным средствам (снизу-вверх)
Топологии иногда можно отображать друг на друга – реализовать один тип топологии на базе другого
Слайд 7Некоторые типы топологий
решетка
2D тор
куб
Линейка (ферма)
Бинарное дерево
звезда
Полный граф
Кольцо
Слайд 10Особенности гипердерева
В обычном дереве – один корень – узкое место
В
гипердереве несколько корней
Каждый лист связан с несколькими корнями – устранение
узких мест
Слайд 11Особенности использования топологий
Разные аппаратные средства имеют свою топологию
Ethernet – звезда
SCI
– тор
Myrinet, QSnet – гипердерево
CrayT3E – решетка
Обычно в любой момент
времени одновременно могут обмениваться данными друг с другом только два адаптера или процессора Не перекрывающиеся пары процессоров могут обмениваться параллельно
Слайд 12Характеристики топологий
Диаметр – максимально возможная длина пути между двумя узлами
Связность
– сколько существует разных путей передачи между двумя процессорами
Сколько процессоров
связаны с однимМинимально сколько путей необходимо удалить, чтобы разделить на две несвязанные области
Ширина бисекции – минимально сколько путей необходимо удалить, чтобы разбить область на две несвязанные
Цена – общее количество путей передачи данных
Слайд 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) [тепер всі процесори містять дані]
1
2
3
4
5
6
7
8
Слайд 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)
1
2
3
4
5
6
7
8
Слайд 29Особенность редукции
Суммирование в результате выполняется в нужном порядке
Можно реализовать любую
функцию со свойствами ассоциативности
Перемножение матриц
Слайд 30Обобщенная передача от всех всем
Каждый процессор имеет свое сообщение, его
необходимо передать остальным
Рассмотрим задачу для гиперкуба
i-й процессор имеет данные
di1
2
3
4
5
6
7
8
Слайд 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 раза
больше данных1
2
3
4
5
6
7
8
Слайд 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)
scatter(p,m,m1)
Все
процессоры вызывают функцию
Каждый процессор получает свое сообщение в массиве m
Первый
процессор передает из массива m1
Слайд 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)
gather(p,m,m1)
Все процессоры вызывают функцию
Слайд 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)
Слайд 42Выводы
Для сложных задач обмена наиболее эффективная топология – гиперкуб
Для простых
– 2D-3D тор
