(2016) Ответы (1162879), страница 2
Текст из файла (страница 2)
Так как все процессоры видят модификации данных ведином порядке (включая и автора изменений)ПричиннаяНет. Причинные связи отслеживаются по чтению,предшествующему записи. Здесь наоборот. Записьпредшествует чтению, что не будет отслежено.PRAMНет, так как каждый процессор сможет изменить значенияразделяемых переменных в локальной памяти и войти в КС.ПроцессорнаяСчитая переменные flag[0] и flag[1] разными, припроцессорной консистентности алгоритм работать не будет,так как оба процессора могут войти в КС.Слабая/По выходу/По входуНет, так как необходимо выделение синхронизационныхпеременных.Тема-31.В транспьютерной матрице размером 4*4, в каждом узле которой находится одинпроцесс, необходимо выполнить операцию передачи сообщения длиной N байтвсем процессам от одного (MPI_BCAST) – процесса с координатами (0,0).Сколько времени потребуется для этого, если все процессы выдали ееодновременно.
Время старта равно 100, время передачи байта равно 1(Ts=100,Tb=1). Процессорные операции, включая чтение из памяти и запись впамять, считаются бесконечно быстрыми.Операция MPI_BCAST выдаётся на каждом процессе. Узнать, кто являетсяисточником сообщения, можно по аргументу root.Без конвейера.Операция MPI_BCAST осуществляет посылку сообщений всем соседям данноготранспьютера. Следовательно, каждая посылка сообщения в транспьютерной матрицеоперацией (MPI_BCAST) заполняет очередную диагональ матрицы: 0 - (0,0); 1 - (1,0),(0,1); 2 - (2,0), (1,1), (0,2) и т.д. (где (i,j) - координата процесса).
Следовательно, дляосуществления операции MPI_BCAST в матрице 4x4 нужно 6*(Ts+N*Tb) единиц времени.Для конвейера.Исходим из определения времени старта:Время старта - это время инициализации канала для передачи любого количестваданных (хоть одного байта)Разобьем сообщение на К кусков. Здесь К не может быть более 2.Для матрицы произвольного размера n*m минимальное время передачи из (0,0)определяется числом шагов для передачи информации по самому длинному маршруту до(n, m), это (n - 1)*(m - 1) шагов.До всех других узлов передача может быть осуществлена за меньшее число шагов.Время передачи первого куска до последней точки (3,3) (загрузка конвейера) равно6*(Ts+(N/K)*Tb) (см. пункт без конвейера)Время прохода остальных кусков (конвейер загружен) (K-1)*(Ts+(N/K)*Tb)ИТОГО: 6*(Ts+(N/K)*Tb)+(K-1)*(Ts+(N/K)*Tb)Для особых эстетов минимум достигается при K = sqrt(5*Tb*N/Ts).2.В транспьютерной матрице размером 4*4, в каждом узле которой находится одинпроцесс, необходимо выполнить операцию сбора данных (длиной один байт) отвсех процессов для одного (MPI_GATHER) – процесса с координатами (0,0).Сколько времени потребуется для этого, если все процессы выдали ееодновременно.
Время старта равно 100, время передачи байта равно 1(Ts=100,Tb=1). Процессорные операции, включая чтение из памяти и запись впамять, считаются бесконечно быстрыми.Вариант 1 (узлы не могут накапливать информацию)2 входящих канала у собирающего узла (0,0) - можем разбить данные от всех узлов надва маршрута.От самого удаленного узла сообщение придёт за 15 / 2 = 8 тактов.На каждом из этих 8 тактов сообщения будут постепенно продвигаться к узлу (0,0).Таким образом за 8 тактов будут получены все сообщения. Итого: 8*(Ts+Tb).Вариант 2 (узлы могут накапливать информацию)Число в скобках - номер такта.
Без скобок - кол-во байт.Максимальная длина маршрута - 6 - от (3,3) к (0,0). Будем передавать по нему одинбайт, не накапливая, за время 6*(Ts+Tb) = 6*(100+1) = 606.Данные от остальных узлов будем передавать с накоплением, максимальное кол-вотактов для этого - 5. Время для трёх маршрутов длины 5:5*Ts+(14+6+4+2+1)*Tb = 527,5*Ts+(14+7+3+2+1)*Tb = 527,5*Ts+(14+7+3+2+1)*Tb = 527, все меньше, чем 606 => Ответ - 606.3.В транспьютерной матрице размером 4*4, в каждом узле которой находится одинпроцесс, необходимо выполнить операцию рассылки данных (длиной один байт)всем процессам от одного (MPI_SCATTER) – процесса с координатами (0,0).Сколько времени потребуется для этого, если все процессы выдали ееодновременно.
Время старта равно 100, время передачи байта равно 1(Ts=100,Tb=1). Процессорные операции, включая чтение из памяти и запись впамять, считаются бесконечно быстрыми.Задача отличается от предыдущей только потоком данных. Ответ тот же.4.В транспьютерной матрице размером 4*4, в каждом узле которой находится одинпроцесс, необходимо выполнить операцию нахождения максимума среди 16чисел (каждый процесс имеет свое число). Сколько времени потребуется дляполучения всеми максимального числа, если все процессы выдали эту операциюредукции одновременно.
А сколько времени потребуется для нахождениямаксимума среди 64 чисел в матрице 8*8? Время старта равно 100, времяпередачи байта равно 1 (Ts=100,Tb=1). Процессорные операции, включая чтениеиз памяти и запись в память, считаются бесконечно быстрыми.Итого: 6*(Ts+Tb).Если процессов 64, то разобьём квадрат на 4 подквадрата. Как было показано ранее, за4 операции можно получить максимум своего квадрата в (3,3), (5,3), (3,5) и (5,5). Ещё двеоперации нужно на пересылку в центральные процессы. Там за 2 операции получаеммаксимум из всех из них (как и в первом случае), и ещё 6 на рассылку (вспомнимbroadcast-рассылку в квадрате 4*4). Итого: 14*(Ts+Tb).5.В транспьютерной матрице размером 4*4, в каждом узле которой находится одинпроцесс, необходимо переслать очень длинное сообщение (длиной L байт) из узлас координатами (0,0) в узел с координатами (3,3).
Сколько времени потребуетсядля этого, если передача сообщений точка-точка выполняется в буферизуемомрежиме MPI? А сколько времени потребуется при использовании синхронногорежима и режима готовности? Время старта равно 100, время передачи байтаравно 1 (Ts=100,Tb=1). Процессорные операции, включая чтение из памяти изапись в память, считаются бесконечно быстрыми.Слова “очень длинное сообщение” означают, что:1. Сообщение можно разбить на большое число частей. Тогда прииспользовании конвейера время его разгона и торможения будетпренебрежимо мало, то есть время не зависит от длины конвейера;2.
Каждая часть сообщения будет иметь большой размер, значит, временем Tsможно пренебречь.Таким образом, остаётся только слагаемое L*Tb.Время можно сэкономить, если задействовать два разных маршрута пересылкисообщения и конвейер.Режимы передачи:1. Буферизуемый. Часть сообщения помещается в буфер одного канала (поусловию это копирование бесконечно быстрое), сразу после этого процесссвободен, он помещает другую часть сообщения в буфер другого канала и т.д.2. Синхронный. Необходимо получить подтверждение готовности отпринимающей стороны, общая схема: запросить готовность - получитьподтверждение - начать передачу.
Потеря времени.3. Режим готовности. Считаем, что принимающая сторона заведомо готова иждёт нашего сообщения. Самый быстрый способ, так как нет переписи вбуфер и нет ожидания подтверждения от приёмника.Без конвейера.1 вариант:6*(L/2)*Tb = 3*L*Tb.2 вариант:Можно также разбивать сообщения на четверти после шага 1, как на рисунке ниже(красным обозначены пересылки L/2, зелёным - L/4).В таком случае, ответ будет (½+¼+¼+¼+¼+½)*L*Tb = 2*L*Tb.С конвейером.Поделим длинное сообщение на K кусков. Кроме того, его можно распилить пополами пустить двумя путями (больше не получится – около углов узкое место), тогда времябудет такое: (K+5)*((L/2)/K)*Tb.6.В транспьютерной матрице размером 4*4, в каждом узле которой находится одинпроцесс, необходимо переслать сообщение длиной L байт из узла с координатами(0,0) в узел с координатами (3,3).
Сколько времени потребуется для этого прииспользовании а) неблокирующих и б) блокирующих операций MPI? Времястарта равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Процессорныеоперации, включая чтение из памяти и запись в память, считаются бесконечнобыстрыми.В случае с неблокирующими операциями время работы будет таким же, как сблокирующими операциями, если использовать режим передачи сообщения сбуферизацией на траспьютерах.Передавать можно с использованием конвейера или без конвейера.Без конвейераПотребуется 6 посылок по L/2 байт (по двум сторонам квадрата).Время Т = 6*(Ts+(L/2)*Tb).С конвейеромИдея: разделить исходное сообщение на К частей.Время передачи первой части - 6*(Ts+(L/K)*Tb).Время передачи остальных частей - (K-1)(Ts+(L/K)*Tb).Время Т = (K+5)(Ts+(L/K)*Tb), К1 = sqrt(5*Tb*L/Ts), К2 = К1+1.K = min(К1, К2).Если исходное сообщение разделить на 2, и каждое полученное сообщение, разделивна К частей, пустить по 2 параллельным маршрутам, то получим T =(K+5)(Ts+((L/2)/K)*Tb).К1 = sqrt(5*Tb*(L/2)/Ts), К2 = К1+1.K = min(К1, К2).Тема-4При решении задач на эту тему необходимо оговаривать нумерацию процессов всети (связанную со структурой дерева) и начальное положение маркера.1.Все 16 (18) процессов, находящихся на разных ЭВМ сети с шинной организацией(без аппаратных возможностей широковещания), одновременно выдали запросна вход в критическую секцию.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
