Решённые задачи к экзамену (1162834), страница 2
Текст из файла (страница 2)
Гарантирует, что к выполнению следующей заMPI_Barrier инструкции каждая задача приступит одновременно с остальными.Это единственная в MPI функция, вызовами которой гарантированно синхронизируется во времени выполнениеразличных ветвей! Некоторые другие коллективные функции в зависимости от реализации могут обладать, а могути не обладать свойством одновременно возвращать управление всем ветвям; но для них это свойство являетсяпобочным и необязательным - если Вам нужна синхронность, используйте только MPI_Barrier.Пусть координатор находится в точке (0, 0). В один момент времени все 15 оставшихся процессов вызываютMPI_BARRIER. Это выражается в отправке в сторону Координатора 1 байта каждым. Составим таблицу:Расстояние до координатора123456Количество каналов в сторону координатора246642Количество байт для передачи2343218Задержка при передаче этого кол-ва байт по этому кол-ву каналов122211Красным-bold отмечено самое узкое место в топологии каналов в нашем случае.
Задержка получается делениемкол-ва байт для передачи на кол-во каналов в сторону координатора в худшем случае (а это 2). В итоге имеемзадержку байта, посланного от (3, 3): 6 * Ts + (1 + 2 + 2 + 2 + 1 + 1) * Tb = 6 * Ts + 9 * TbПосле этого он начнет рассылать всем процессам сообщение о том, что барьер создан (работа синхронизирована,все дошли до барьера).Расстояние от координатора012345Количество каналов от координатора246642Количество байт для передачи151310631Задержка при передаче этого кол-ва байт по этому кол-ву каналов875321Кроме этого, есть еще 6 затрат на установление соединений (реально соединений было больше, просто многие шлипараллельно). В сумме 6 * Ts + 26 * Tb.Ответ: 12 * Ts + 35 * Tb[ Рассылка всем процессам какого-то сообщения это MPI_BCAST (см. следующую задачу).У нее ответ: 6 * (Ts + 1 * Tb.)] - да, тут вообще все можно по разному обыграть.
Главное обосновать.2. В транспьютерной матрице размером 4*4, в каждом узле которой находится один процесс, необходимовыполнить операцию передачи сообщения длиной N байт всем процессам от одного (MPI_BCAST) - процесса скоординатами (0,0). Сколько времени потребуется для этого, если все процессы выдали ее одновременно. Времястарта равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Процессорные операции, включая чтение из памятии запись в память считаются бесконечно быстрыми.Решение.Если кто понял, что значит фраза "...
если все процессы выдали ее одновременно", скажите. По-моемуэто неправильный копи-паст задач просто.MPI_BCAST - это широковещательная рассылка сообщения всем остальным процессам в группе.Предположим, что нам из точки (0, 0) достаточно послать сообщения только своим соседям, а они сами передадутего копии дальше. Тогда время будет равно времени пути сообщения до самой дальней точки, а это 6 переходов.Ответ: 6 * ( Ts + 1 * Tb).
Только не 1*Tb, а N*Tb. Потому что N байт.3. В транспьютерной матрице размером 4*4, в каждом узле которой находится один процесс, необходимовыполнить операцию сбора данных от всех процессов (длиной один байт) для одного (MPI_GATHER) - процесса скоординатами (0,0). Сколько времени потребуется для этого, если все процессы выдали ее одновременно. Времястарта равно 100, время передачи байта равно 1 (Ts=100,Tb=1).
Процессорные операции, включая чтение из памятии запись в память считаются бесконечно быстрыми. Решение.9Цифрами обозначено количество байт, которое транспьютер хочет отправить в данный момент времени.Итого получаем 6 * ( Ts + Tb)А как работает gather, разве процессоры сначала не должны узнать о том ,что (0,0) хочет от нихинформацию? Т.е не надо считать время, которое потратится сначала на извещение? И не понятно откудав такой картинке 6Ts + ... . Вот последний рисунок, это время 3Ts + ..., при этом левая ветвь состоит из 4посылок, которые не сделанны.Согласен, надо подправить.4.
В транспьютерной матрице размером 4*4, в каждом узле которой находится один процесс, необходимовыполнить операцию рассылки данных (длиной один байт) всем процессам от одного (MPI_SCATTER) - процессас координатами (0,0). Сколько времени потребуется для этого, если все процессы выдали ее одновременно. Времястарта равно 100, время передачи байта равно 1 (Ts=100,Tb=1).
Процессорные операции, включая чтение из памятии запись в память считаются бесконечно быстрыми.Решение.5. В транспьютерной матрице размером 4*4, в каждом узле которой находится один процесс, необходимовыполнить операцию суммирования 16 чисел (каждый процесс имеет свое число). Сколько времени потребуется10для получения всеми суммы, если все процессы выдали эту операцию редукции одновременно? А сколько временипотребуется для суммирования 64 чисел в матрице 8*8? Время старта равно единице, время передачи байта равнонулю (Ts=1,Tb=0).
Процессорные операции, включая чтение из памяти и запись в память считаются бесконечнобыстрыми.Решение.6. В транспьютерной матрице размером 4*4, в каждом узле которой находится один процесс, необходимовыполнить операцию нахождения максимума среди 16 чисел (каждый процесс имеет свое число). Сколько временипотребуется для получения всеми максимального числа, если все процессы выдали эту операцию редукцииодновременно. А сколько времени потребуется для нахождения максимума среди 64 чисел в матрице 8*8? Времястарта равно единице, время передачи байта равно нулю (Ts=1,Tb=0). Процессорные операции, включая чтение изпамяти и запись в память считаются бесконечно быстрыми.Решение.7.
В транспьютерной матрице размером 4*4, в каждом узле которой находится один процесс, необходимопереслать очень длинное сообщение (длиной L байт) из узла с координатами (0,0) в узел с координатами (3,3).Сколько времени потребуется для этого. А сколько времени потребуется для пересылки из узла с координатами(1,1) в узел с координатами (2,2). Время старта равно времени передачи байта (Ts=Tb).
Процессорные операции,включая чтение из памяти и запись в память считаются бесконечно быстрыми.Решение.8. В транспьютерной матрице размером 4*4, в каждом узле которой находится один процесс, необходимопереслать сообщение длиной L байт из узла с координатами (0,0) в узел с координатами (3,3). Сколько временипотребуется для этого, если передача сообщений выполняется в буферизуемом режиме MPI? А сколько временипотребуется при использовании синхронного режима и режима готовности? Время старта равно 100, времяпередачи байта равно 1 (Ts=100,Tb=1).
Процессорные операции, включая чтение из памяти и запись в памятьсчитаются бесконечно быстрыми.Решение.•••MPI_BSEND - передача сообщения с буферизацией. Последовательность вызова и окончания операцийвызова и приема произвольна, операция send завершается тогда, когда сообщение изъято из памяти ипомещено в буфер.
Если места в буфере нет - ошибка программы. Операция локальная.MPI_SSEND - передача сообщения с синхронизацией. Последовательность вызова и завершения операцийвызова и приема произвольна, но операция MPI_SSEND завершается только после начала выполненияоперации receive.
Операция нелокальная.MPI_RSEND - передача сообщения по готовности. Операция MPI_RSEND просто посылает данные наудаленный компьютер и сразу возвращает управление программе. Что с ними дальше происходит, мыможем не знать, если их там не ждали то будет ошибка.
Операция локальная.11Решение.9. В транспьютерной матрице размером 4*4, в каждом узле которой находится один процесс, необходимопереслать сообщение длиной L байт из узла с координатами (0,0) в узел с координатами (3,3). Сколько временипотребуется для этого при использовании а) неблокирующих и б) блокирующих операций MPI? Время стартаравно 100, время передачи байта равно 1 (Ts=100,Tb=1).
Процессорные операции, включая чтение из памяти изапись в память считаются бесконечно быстрыми.Решение.12Тема 4(См. Лекция 4: "Синхронизация в распределенных системах")1. Все 16 процессов, находящихся в узлах транспьютерной матрицы размером 4*4, одновременно выдали запрос навход в критическую секцию. Сколько времени потребуется для прохождения всеми критических секций, еслииспользуется круговой маркерный алгоритм. Время старта равно 100, время передачи байта равно 1 (Ts=100,Tb=1).Процессорные операции, включая чтение из памяти и запись в память считаются бесконечно быстрыми.Решение.Все процессы составляют логическое кольцо, когда каждый знает, кто следует за ним.
По кольцу циркулируетмаркер, дающий право на вход в критическую секцию. Получив маркер (посредством сообщения точка-точка)процесс либо входит в критическую секцию (если он ждал разрешения) либо переправляет маркер дальше. Послевыхода из критической секции маркер переправляется дальше, повторный вход в секцию при том же маркере неразрешается.Ответ: 15 * ( Ts + 1 * Tb)2.
Все 16 процессов, находящихся на разных ЭВМ сети с шинной организацией (без аппаратных возможностейшироковещания), одновременно выдали запрос на вход в критическую секцию. Сколько времени потребуется дляпрохождения всеми критических секций, если используется древовидный маркерный алгоритм.
Время старта(время разгона после получения доступа к шине) равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Доступ кшине ЭВМ получают последовательно в порядке выдачи запроса (при одновременных запросах - в порядкеномеров ЭВМ). Процессорные операции, включая чтение из памяти и запись в память считаются бесконечнобыстрыми.13Решение.Я так понял, что вершины получат маркер в порядке их номеров. Количество ЗАПРОС-ов и МАКЕР-ов будетравно удвоенной длине пути между вершинами (соседними).Если посчитать вручную нужное количество запросов и передач маркеров, то когда 5-ая вершина будет выполнятьсвою КС их будет 18, на 8-ой - 40, а на 6 - 102.Ответ: 102 * (Ts + 1 * Tb).[ В нулевой момент времени к шине поступают запросы от устройств 2-16.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
