Параллельные алгоритмы обмена информацией
Судаков А.А.
“Параллельные и распределенные вычисления” Лекция 14
План
Системы с общей и распределенной памятью
Обмен в системах с общей памятью
Обмен сообщениями
Топологии систем
Методы передачи информации
Параллельные алгоритмы обмена сообщениями
Системы с общей и распределенной памятью
Общая память – все процессоры могут обращаться к одним и тем же самым данным
Распределенная память – процессоры не могут обращаться к данным других процессоров непосредственно
для доступа к данным других процессоров используется передача этих данных в виде сообщений
Обмен данными в системах с общей памятью
Обращения к общим данным
Операции
Запись в память
Чтение из памяти
Синхронные и асинхронные операции
Операции чтения и записи в память обычно синхронные
Процессор точно знает, когда операция заканчивается
При эмуляции общей памяти возможны асинхронные операции
Get
Put
Завершение выполнения команды не означает завершения операции
Во время выполнения операции процессор может выполнять другие действия
Обмен сообщениями
Сообщение (пакет) – неделимая порция информации, которая может быть принята, отправлена и обработана только как единое целое
Операции
Отправить сообщение
Принять сообщение
Примеры – отправка и прием данных по сети
Синхронные и асинхронные операции
Синхронная – завершение команды означает завершение операции
Асинхронные - завершение команды не означает завершения операции
Топологии систем
Топология – структура связей между процессорами
Топология
Логическая – реализуется программно
Физическая – реализуется аппаратно
Топологии параллельной системы определяют эффективность обмена информацией
Логическая топология системы обычно соответствует топологии задачи, которая решается (сверху-вниз)
Физическая топология – обычно обычно имеющимся в наличии аппаратным средствам (снизу-вверх)
Топологии иногда можно отображать друг на друга – реализовать один тип топологии на базе другого
Некоторые типы топологий
Линейка (ферма)
решетка |
2D тор |
куб |
|
|
Бинарное дерево |
звезда |
Полный граф |
Кольцо |
|
|
|
|
||
|
|
|
|
|
Гиперкуб размерности n
Каждый процессор непосредственно связан ровно с n соседями
Гипердерево (fat tree)
Особенности гипердерева
В обычном дереве – один корень – узкое место
В гипердереве несколько корней
Каждый лист связан с несколькими корнями – устранение узких мест