2013 Nurmambetov_2-kr (1162818), страница 3

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

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

Отправитель посылает сообщение 5 ЭВМ, после чего ломается.(5 сообщений). В качестве уникального идентификатора сообщения используется его начальный приоритет - логическое время отправления. Пусть логическое время занимает 1 байт (ВРЕМЯ СОСТОИТ ИЗ СЧЕТЧИКА СОБЫТИЙ И НОМЕРА ПРОЦЕССА!!!). Процесс-отправитель посылает сообщение группе процессов (список их идентификаторов содержится в сообщении). Пусть этот идентификатор занимает 1 байт. Тогда список будет 9 байт. Если само сообщение(для простоты) занимает 1 байт, тогда отправляется 11 байт. Итого времени прошло 5*(Ts+11*Tb)=555

При получении этого сообщения процессы:

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

2. Информируют отправителя о приписанном сообщению приоритете.

Каждый из пяти получателей отправляют отправителю приоритет - 1 байт(текущее логическое время). Итого 5*(Ts+1*Tb)=505

"Если получатель обнаружит, что он имеет сообщение с пометкой «недоставленное», отправитель которого сломался, то он для завершения выполнения протокола осуществляет следующие два шага в качестве координатора.

1. Опрашивает всех получателей о статусе этого сообщения."
Это и изображено на схеме. (5 запросов)

Пусть сообщение с запросом статуса содержит 2 байта. Тогда 5*(Ts+2*Tb)=510.

Координатор получил ответы(5 ответов). 4 получателя ответили:

1. Сообщение отмечено как «недоставленное» и ему приписан такой-то приоритет. Пусть этот ответ занимает 2 байта.

А один:

1. Он не получал это сообщение. Пусть этот ответ занимает 1 байт.

Тогда имеем 4*(Ts+2*Tb)+Ts+Tb=509

Координатор заново начинает весь протокол с фазы 1.(8 сообщений). Список состоит из 8 процессов(8 байт)+само сообщение(1 байт)+идентификатор сообщения(1 байт). Имеем 8*(Ts+10*Tb)=880

Получает ответы от всех адресатов(8 ответов). Это 8*(Ts+1*Tb)=808. Здесь приписанный каждым получателем приоритет - 1 байт. Далее находим максимальный приоритет и отправляем его всем получателям(8 уведомлений):

Приоритет содержит 1 байт, поэтому 8*(Ts+1*Tb)=808.

Просуммируем все, что мы получили:

555+505+510+509+880+808+808=4575

Должны быть объяснены длины всех сообщений (что в них содержится и сколько места занимает)

Вопрос – если надежность не нужна (все работает надежно), а требуется только неделимость, то алгоритм будет быстрее работать? За счет чего?

Да, за счет того, что не нужно отправлять список идентификаторов процессов, т.к. уже будет гарантирована надежная передача. Да и не нужно будет заново отправлять одно и то же сообщение повторно.

===хорошо

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

Решение:
Централизованный алгоритм.

Все процессы запрашивают у координатора разрешение на вход в критическую секцию и ждут этого разрешения. Координатор обслуживает запросы в порядке поступления. Получив разрешение процесс входит в критическую секцию. При выходе из нее он сообщает об этом координатору. Количество сообщений на одно прохождение критической секции - 3.

Недостатки алгоритма - обычные недостатки централизованного алгоритма (крах координатора или его перегрузка сообщениями).

Отсюда 15*3 (Ts+Tb*L)

А что такое L - Должны быть объяснены длины всех сообщений (что в них содержится и сколько места занимает)

Решение было не совсем правильным. Вышеуказанное решение для шинной организации, а у нас транспьютер. Как примерно будет проходит процесс лучше всего отразят следующие картинки.

Введем следующие обозначения. Зеленый квадрат означает, что «разрешение идет» от координатора к запросившему процессу (от запросившего процесса к координатору), и «разрешение» должно быть передано дальше.

Принцип такой (порядок – слева направо, сверху вниз):

Таким образом, продолжая по данному принципу, получаем 96 посылок сообщений. Пусть размер одного сообщения 1 байт (т.к. содержится только разрешение).

Ответ: Общее время Т = 96*(Ts+1b*Tb) = 96*(203) = 19488

===отлично

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

Решение:

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

2. Из условия (см. конец задачи) ясно, что процессы не знают о причинных зависимостях между переменными. И задача сводится к задаче 5.

Нет, не сводится - не знают о причинных зависимостях, но могут определить потенциально причинные зависимости и реализовать эту модель эффективнее, чем последовательную!

Реализация причинной консистентности может осуществляться следующим образом:

• все модификации переменных на каждом процессоре нумеруются;

• всем процессорам вместе со значением модифицируемой переменной рассылается номер этой модификации на данном процессоре, а также номера модификаций всех процессоров, известных данному процессору к этому моменту;

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

Ответы по плану.

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

2) а) при записи рассылается всем;

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

в) при записи рассылается всем;

г) нет

3) Оценка времени. Например, первый процесс рассылает всем модификации, его модификация станет известна всем. Потом второй процесс в сообщении, помимо модификации, прикрепляет что ему известна модификация первого процесса. Третьему известны модификации первого и второго процессов и т.д. Каждый процесс рассылает по 9 сообщений. Пусть под адрес и значение переменной отведем по 1 байту. Под номер модификации тоже 1 байт. Под номер процессора, которому принадлежит модификация тоже 1 байт. Тогда размер сообщения 1 процесса 2 байта, второго – 4, третьего – 6 и т.д.

Размер десятого – 20 байтов. Соответственно времена:

Т1 = 9*(Ts+2b*Tb)

T2 = 9*(Ts+4b*Tb)

………..

T10 = 9*(Ts+20b*Tb)

Общее время Т = Т1 +….+ Т10 = 9*(10*Ts + 110b*Tb) = 9*(1000+110) = 9*1100 = 9900

===отлично

1. Имеется команда TSL и команда объявления прерывания указанному процессору. Опираясь на него, реализуйте на мультипроцессоре P-операцию и V-операцию для двоичного семафора.

Решение: Tsl(r, s) делает [r = s, s = 1] – это неделимая операция.

Enter_region: //P-operation

Tsl reg, flag

Cmp reg, #0

Je Go

<Ждем прерывание>

Go: Ret

Leave_region:// V-operation

Move flag, #0

<Отправляем сигнал> КОМУ? Это прерывание указанному процессору?

Ret

Да, одному из заблокированных процессоров. Можно дополнительно ввести список ждущих, и отправлять первому из них прерывание. Тогда

Je Go Je Go

<Ждем прерывание> изменится на <Добавляем себя в список ждущих>

Go: Ret <Ждем прерывание>

<Убираем себя из списка>

Go: Ret

На одном процессоре может быть много процессов – активных и заблокированных (например, по ожиданию семафора). Команда TSL нужна для взаимного исключения, чтобы операционные системы одновременно не стали работать с очередями процессов и заначениями семафоров. При освобождении семафора разблокируется первый процесс из очереди ожидающих. Это происходит на том процессоре, на котором выполнена операция освобождения, и надо известить другие процессоры (один конкретный, на котором должен выполняться разблокированный процесс, или все другие) – для этого команда прерывания.

===

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

Решение:

При неблокирующих и блокирующих операциях время передачи одинаковое.

Передавать можно с использованием конвейера или без конвейера.

Без конвейера.

Потребуется 6 посылок по L байт. Время Т = 6*(Ts+L*Tb)

С конвейером.

Идея: разделить исходное сообщение на К частей.

Время передачи первой части 6*(Ts+Tb*L/K).

Время передачи остальных частей (K-1)(Ts+Tb*L/K).

Время Т = (K+5)(Ts+Tb*L/K), К1 = [sqrt(5*Tb*L/Ts)], К2 = К1+1.

K = К1 или К2, в зависимости где достигается минимум времени.

Если исходное сообщение разделить на 2, и каждое полученное сообщение разделив на К частей, пустить по 2 параллельным маршрутам. То получим T = (K+5)(Ts+Tb*(L/2)/K).
К1 = [sqrt(5*Tb*(L/2)*Ts)], К2 = К1+1.

K = К1 или К2, в зависимости где достигается минимум времени.

А без конвейера нельзя использовать несколько маршрутов?

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

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