2013 Saktaganov_3-kr (1162819), страница 4

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

N-ый шаг – N присваиваний.

Т.е. первые N-1 шага работают не все процессоры. Аналогично последние N-1 шага то же самое. Первые N-1 шага назовем временем разгона. Последние N-1 шага временем торможения. За время разгона обработаем N*(N-1)/2 ячеек. За время торможения столько же. Разгон(торможение) занимает T_A=(N-1) времени.

За разгон+торможение обработаем N*(N-1) ячеек и это займет 2*(N-1) времени.

В оставшееся время работают все процессоры. Назовем это время полного параллелизма. Осталось обработать (L1-2)*(L2-2)-N*(N-1) ячеек.

Время полного параллелизма T_FP = ((L1-2)*(L2-2)-N*(N-1)) / N;

Время параллельной программы:

T_P = T_FP+2*T_A.

Ответ:

Ускорение A = T_L/T_P = (L1-2)*(L2-2)/(((L1-2)*(L2-2)-N*(N-1)) / N + 2*(N-1)) =

= N * (L1-2) * (L2-2) / (N*(N-1)+(L1-2)*(L2-2))

1. В транспьютерной матрице размером 4*4, в каждом узле которой находится один процесс, необходимо выполнить операцию передачи сообщения длиной N байт всем процессам от одного (MPI_BCAST) - процесса с координатами (0,0). Сколько времени потребуется для этого, если все процессы выдали ее одновременно. Время старта равно 100, время передачи байта равно 2 (Ts=100,Tb=2). Процессорные операции, включая чтение из памяти и запись в память, считаются бесконечно быстрыми.

Решение:

А) Без конвейера: Самый дальний от узла (0,0) это узел (3,3). Для того, чтобы сообщение дошло до него нужно 6 передач.

Например: (0,0)=>(1,0)=>(1,1)=>(2,1)=>(2,2)=>(3,2)=>(3,3).
Ответ: T = 6 * ( Ts + N*Tb) = 600 + 12*N.

Б) С конвейером. Пусть у нас k частей. Тогда время передачи:

T(k) = 6*( Ts + (N/k)* Tb) + (k-1)*(Ts + (N/k)* Tb) = (k+5)(Ts + (N/k)*Tb).

Возьмем производную по k и правниваем к нулю.

T’(k) = Ts+ (N/k) * Tb + (k+5) * (-N/k²)*Tb = 0 =>

(k²*Ts + k*N*Tb) / k² = (k+5)*N*Tb/k².

k²*Ts + k*N*Tb = (k+5)*N*Tb => k² = 5*N*Tb/Ts => k = sqrt(5*N*Tb/Ts).

Т.к. k должно быть целым, берем k_1­ = trunc(k) – целая часть от k. k_{2 =} k₁+1;

Ответ: T = (k+5)(100 + 2 * N / k), где k = (T(k_1­) ≤ T(k₂) ? k₁ : k₂).

«? :» есть тернарный оператор.

===Отлично

1. Все 18 процессов, находящихся на разных ЭВМ сети с шинной организацией (без аппаратных возможностей широковещания), одновременно выдали запрос на вход в критическую секцию. Сколько времени потребуется для прохождения всеми критических секций, если используется древовидный маркерный алгоритм. Время старта (время «разгона» после получения доступа к шине) равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Доступ к шине ЭВМ получают последовательно в порядке выдачи операции посылки сообщения (при одновременно выданных операциях - в порядке номеров ЭВМ). Процессорные операции, включая чтение из памяти и запись в память, считаются бесконечно быстрыми.

Решение:

Пусть в начальный момент времени меркер находится у процесса 0. И пусть запрос и маркер могут посылаться в одном сообщении. В начале будет 17 запросов:

После этого пойдет передача маркера.

MR – Marker + Request.

M – Marker.

R – Request.

0—MR—1—MR—2—MR—3—MR—4—M—3—MR—5—M—3—M—2—MR—6—MR—7—M—6—M—2—M—1—MR—8—MR—9—M—8—MR—10—M—8—M—1—M—0—M—11—MR—12—MR—13—M—12—MR—14—M—12—M—11—M—15—MR—16—M—15—M—17.

Получили 17R + 14MR + 17M сообщений. Пусть Маркер и Запрос занимают по 1 байту. Маркер+Запрос занимает 2 байта.

Ответ: T = 17*(Ts+Tb*SIZE_R) + 14*(Ts+Tb*SIZE_MR) + 17*(Ts+Tb*SIZE_M) = 48*Ts + 34*1 + 14*2 = 4800 + 62 = 4862

===Отлично

1. Процессорная консистентность памяти и алгоритм ее реализации в DSM с полным размножением. Сколько времени потребует модификация 18 различных переменных, если все 18 процессов (каждый процесс модифицирует одну переменную), находящихся на разных ЭВМ сети с шинной организацией (без аппаратных возможностей широковещания), одновременно выдали запрос на модификацию своей переменной. Время старта (время «разгона» после получения доступа к шине) равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Доступ к шине ЭВМ получают последовательно в порядке выдачи операции посылки сообщения (при одновременно выданных операциях - в порядке номеров ЭВМ). Процессорные операции, включая чтение из памяти и запись в память, считаются бесконечно быстрыми.

Решение:

1. Процессорная консистентность – каждый процессор видит модификации, производимые одним процессором, в том же порядке, как они были произведены. Кроме того для каждой переменной x есть общее согласие относительно порядка, в котором процессоры модифицируют эту переменную, операции записи в разные переменные – параллельны.

1. а) отправляется кооринатору, который отвечает за данную переменную, запрос на модификацию;

б) читается из локальной памяти;

в) координатор принимает запросы на модификацию и рассылает всем указания о проведении модификации;

г) нет, т.к. можно отправить запрос, и продолжать выполнение.

да, т.к. при записи отправляем координатору запрос и ждем получения указания от координатора о модификации.

Сам алгоритм. За каждую группу переменных отвечает свой координатор, который получает от процессов запросы на модификацию и рассылает всем указания о проведении модификации. Чтобы не нарушить порядок получения процессами указаний о модификациях различных переменных, запрошенных одним процессом у разных координаторов, надо каждому процессу нумеровать свои модификации, и эти номера должны рассылаться всем вместе с указаниями о проведении модификаций. Тогда любой процесс, получающий указание о проведении модификации, может задержать его выполнение до получения недостающих указаний о предшествующих модификациях соответствующего процесса.

1. Оценка времени. Пусть каждый ЭВМ отвечает за одну переменную. Пусть координатором переменной, которую изменяет данный ЭВМ не является тот же самый ЭВМ, т.е. для каждого ЭВМ, координатором изменяемый им переменной является другой ЭВМ. Так как в случае если координатор изменяется свою переменную, задача сводится к простой рассылке модификаций. У нас все переменные разные, поэтому можно в них записывать параллельно. Рассмотрим время выполнения одной модификации. Сначала координатору отправляется запрос на модификацию. Он рассылает указания о проведения модификации (всем, кроме себя и процессора, который запросил эту модификацию поправка: рассылает всем кроме себя). В запросе на модификацию содержится адрес переменной, ее значение, номер модификации. Координатор может прикреплять к указаниям о модификации номера процессов запросивших эти модификации, чтобы можно было различать модификации с одинаковыми номерами различных процессов. Время модификации = время запроса + время рассылки: T_M = T_R + 16*T_MD,

M – Modification;

R – Request;

MD – ModificationDirective.

T_R = Ts + SIZE_R*Tb;

T_MD = Ts + SIZE_MD*Tb;

Для простоты, пусть под адрес переменной, значение переменной, номер модификации отведем по 1 байту. Тогда SIZE_R = 3байта. Под номер процесса отведем тоже 1 байт. SIZE_MD = 4байта. Так как у нас 18 модификации, общее время:
T = 18*T_M = 18*(T_R + 16*T_MD) = 18*(Ts + 3*Tb + 16*(Ts+4*Tb)) =

= 18*(103 + 16*104) = 31806

Ответ: Т = 31806

Если процесс не ждет сообщения о своей модификации от координатора, то он будет считать, что его модификация переменной Х совершилась раньше модификаций этой переменной другими процессами, что неправильно.

Время модификиции будет : T_M = T_R + 17*T_MD,

M – Modification;

R – Request;

MD – ModificationDirective.

T_R = Ts + SIZE_R*Tb;

T_MD = Ts + SIZE_MD*Tb;

Для простоты, пусть под адрес переменной, значение переменной, номер модификации отведем по 1 байту. Тогда SIZE_R = 3байта. Под номер процесса отведем тоже 1 байт. SIZE_MD = 4байта. Так как у нас 18 модификации, общее время:
T = 18*T_M = 18*(T_R + 17*T_MD) = 18*(Ts + 3*Tb + 17*(Ts+4*Tb)) =

= 18*(103 + 17*104) = 33678

Ответ: Т = 33678

===Отлично

ИТОГО – 4 оценки ОТЛ

6 отлично, 3 хорошо, 2 удовл,

Характеристики

Список файлов ответов (шпаргалок)