Возможна оптимизация: первые сообщения посылаются ближайшим транспьютерам:

Они начнут сразу передавать данные. Дальше при больших N сообщения посылаются самым дальним,

И по мере удаления. Цель – сохранить оба входных канала приема максимально заполненными.

Тогда 8*(Ts+N*Tb) +Ts+Lm.

Если N не достаточно велико, то есть будет простой приема при такой схеме (например, N<100), подсчет усложняется. Усложняется также выбор оптимального порядка рассылки сообщений.

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

Pr-0	A0	A1	A2	A3	SCATTER	A0
Pr-1						A1
Pr-2					GATHER	A2
Pr-3						A3

Итого данные будуь получены через 8 циклов, т.е 8*(Ts+N*Tb)

1. В транспьютерной матрице размером 4*4, в каждом узле которой находится один процесс, необходимо выполнить операцию нахождения максимума среди 16 чисел (каждый процесс имеет свое число). Сколько времени потребуется для получения всеми максимального числа, если все процессы выдали эту операцию редукции одновременно. А сколько времени потребуется для нахождения максимума среди 64 чисел в матрице 8*8? Время старта равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Процессорные операции, включая чтение из памяти и запись в память, считаются бесконечно быстрыми.

T = 6*(Ts+L*Tb)

14*(Ts+L*Tb)

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

Замечание. MPI находится на более высоком уровне, чем транспьютерная решётка (в модели OSI).

Собственно буферизуемый или не буферизуемый режим MPI влияет только на процесс-отправитель и процесс-получатель.

Однако транспьютеры могут работать в режиме передачи сообщений с буферизацией или без неё. При режиме с ьуферизацией транспьютер не имеет право инициировать посылку сообщения в выходной канал до того, как он получил последний байт с входного канала.

При отсутствии буферизации транспьютер должен сразу при получения первого байта сообщения инициировать пересылку по выходному каналу (если узел не является получателем). Считаем, что транспьютер имеет возможность инициировать пересылку во исходящему каналу сразу после начала передачи. В общем случае следует учитывать задержку на прием служебной информации с адресом получателя. Существуют системы, в которых такая задержка строго равна 1 байту, т.е. первый байт кадра сообщает коммутатору в какой выходной канал следует направлять все сообщение.

Также учтем, что само сообщение можно распараллелить на 2 выходных канала, что отразим сокращением длины в 2 раза.

Буферизуемый режим транспьютеров – Ts*6+Tb*(L/2)*6

Небуферизуемый режим транспьютеров – Ts*6+(L/2)* Tb+6

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

Разницы между блокирующими и неблокирующими не будет, так как блокировка относится не к подсистеме MPI, а к процессу, вызывающему.

Потребуется времени – Ts*6+Tb*L*6, если не использовать распараллеливание передачи данных.

Если использовать, то можно считать, что данные пойдут по сторонам квадрата, так как узким местом здесь будут выходные каналы узла (0,0). То есть оптимальнее не получится. Тогда получится время Ts*6+Tb*[L/2]*6.

Если при этом предположить, что промежуточные узлы могут передавать сообщение дальше, не дожидаясь полного приема сообщений, и кроме того L достаточно большое, тогда получится:

Ts*6+ Tb*[L/2]+6. Ts*6 время полной загруки конвейера, 6 – время разгрузки конвейера.

Тема-4

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

После этого все процессы знают, куда направлять маркер, когда он придет.

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

Итого сообщений передачи маркера с запросом – 12, маркера без запроса – 15, всего передач маркера – 27.

Считаем, что и маркер и маркер с запросом передаются в одном сообщении длиной в Lm

Тогда общее время = (Ts+Tb*Lz)*15+(Ts+Tb*Lm)*27.

Считая сообщение маркера очень коротким, получим 42*Ts

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

Взяв любой другой процесс, мы получим ту же картину: надо разослать 15 запросов и получить 15 ответов. При этом мы считаем, что время прохождения КС=0. Тогда получается, что надо просто умножить время получения разрешения 0-м процессом на 16.

16*15*( Ts+Tb*Lm)

Если же мы предположим, что внутри КС проводится отличное от 0 время, тогда надо будет учитывать, что некоторые сообщения не зависят от того, находится ли другой процесс в КС или нет.

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

Предположим режим с блокировкой процессов. То есть сообщение не может прийти, если не доставлены ранее отправленные.

Все кроме 0-го пошлют широковещательные запросы. Это займет 15*15*(Ts+Tb*Lz).

После этого будет передаваться только маркер, содержащий очередь запросов. Всего будет 15 передач. Каждая за время Ts+Tb*Lm.

Итого 255*(Ts+Tb*Lz)+15*(Ts+Tb*Lm).

Замечание. Нельзя отбросить Lm, так как он содержит очередь запросов и может быть достаточно большим (как минимум сравним с Ts).

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

15*3 (Ts+Tb*L)

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

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

Тема-5

1. Какие принципиальные решения приходится принимать при обеспечении файлового сервиса?

• Модель файла

• Можно ли модифицировать после создания

• Защита

• загрузка/разгрузка или удалённый доступ

• с состоянием / без состояния

• как обеспечить масштабируемость

• как обеспечить прозрачность

• как обеспечить высокую доступность.

• должно ли быть единое дерево ФС для всех машин

• Есть ли разница между клиентом и сервером

• ФайлСервер и Сервер директ – совпадают?

1. Интерфейс сервера директорий.

• создание /удаление директорий, именование/переименование/перемещение файлов

• создание иерархии

• единое дерево директорий или нет?

• прозрачность расположения/прозрачность миграции

• машина+путь/локальное монтирование/единое унифицированное пространство

1. Семантика разделения файлов.

• UNIX-семантика (FIFO)

• Неизменяемые файлы

• Сессии – изменения становятся видимыми при закрытии

• Транзакции

1. Серверы с состоянием и без состояния. Достоинства и недостатки.

Серверы с состоянием. Достоинства.

Короче сообщения (двоичные имена используют таблицу открытых файлов).