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

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

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

3. Оценка времени:

Для одного выполнения КС надо отправить координатору запрос, получить значения переменных и право владения, после выполнения КС надо вернуть право владения координатору и, т.к. у нас запись (значит монопольный доступ), отправить ему новые значения переменных. Пусть координатор расположен на ЭВМ 0.

И так:

Время запроса T_R=Ts+SIZE_R*Tb

Время ответа координатора: T_CA=Ts+SIZE_CA*Tb

Время возврата права координатору: T_RET = Ts+SIZE_RET*Tb.

Пусть размер запроса 1 байт. Для простоты, размеры адресов и значений по 1 байту. Размер ответа координатора 12*(1+1)=24байт. Т.к. 11 переменных + 1 синхр. переменная. Размер возврата права координатору также 24 байта.

Время одного прохождения = 100+1 + 100+24+100+24 = 349.

Т.к. процессу 0 нет необходимости посылать сообщения через шину, посылать будут только 17 процессов. Общее время = 17*349*3 (трехкратное выполнение) = 17799.

===Удовлетворительно (для лучшей оценки нужен распределенный алгоритм!)

Тогда рассмотрим децентрализованный алгоритм. Он является модификацией предыдущего алгоритма. Для получения права владения синхр. переменной, процесс делает широковещательную рассылку, где указывается тип права на владение (монопольно/ немонопольно), и ждет получения своего же запроса. При получении запроса, процесс добавляет запрос в очередь. Если процесс не выдавал запрос, то он отвечает на все запросы «ОК». Если процесс выдавал запрос на монопольный доступ, то отвечает всем запросам, стоящих перед ним в очереди «ОК»(концептуально, себе тоже – это для удаления себя из очереди). Если процесс выдавал запрос на немонопольный доступ, то отвечает всем запросам, стоящих перед ним в очереди «ОК», а также всем стоящим после него немонопольным запросам до первого запроса в монопольном режиме. Процесс самому себе тоже отправляет «ОК» в обоих случаях. При отправке «ОК» какому-то запросу в очереди, этот запрос удаляется из очереди. Процесс получает право собственности на переменную в соответствующем режиме при получении «ОК» от всех процессов. При выходе из КС, процесс отправляет «ОК» всем остальным процессам в очереди. При выходе из КС, процесс, владеющий монопольным правом собственности на переменную, помимо «ОК», отправляет текущие значения переменных связанных с синхронизационной переменной, всем немонопольным запросам в очереди до первого монопольного запроса включительно.

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

P.S. для разных синхр. переменных следует заводить разные очереди.

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

1. Консистентность по входу - совместно используемые данные, относящиеся к данной критической области, становятся непротиворечивыми при входе в эту область (Таненбаум – «Распределенные системы», поэлементная непротиворечивость).

2. а) пишем в локальную память;

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

в) значения модифицируемых переменных рассылается всем немонопольным запросам в очереди до первого монопольного запроса включительно, процессом владеющим переменным в монопольном режиме при выходе из КС;

г) процесс блокируется пока не получит актуальные значения переменных связанных с синхр. переменной от предыдущего монопольного владельца, и «ОК» от всех процессов.

д) при входе в КС широковещательно рассылается запрос на право владения синхр. переменной в соответствующем режиме (монопольный/ немонопольный). При выходе из КС отправляется «ОК» всем процессам в очереди. Процесс, владеющий синхр. переменной в монопольном режиме, также рассылает текущие значения переменных, связанных с синхр переменной до первого запроса в монопольном режиме включительно.

3. Оценка времени:

В этой задаче все запросы на монопольный доступ. Оценим время одного прохождения КС. Надо сделать одну широковещательную рассылку. Принять 16 «ОК». Одно сообщение «ОК» + актуальные значения связанных переменных. Всего прохождений КС = 3*18=54. Пусть под «ОК» и тип запроса отведем по 1 байту, адрес и значение переменных тоже по 1 байту. В запросе указывается: тип запроса, и синхр. переменная (адрес и значение).

Запрос = тип запроса+адрес и значение синхр. переменной = 3 байта.

ОК = 1байт.

ОК+ актуальные значения = 1байт + 12 * 2байта =25 байтов.

Итого Т = Ts + 3b*Tb + 16*(Ts+1b*Tb) + Ts + 25b*Tb = 1844

Пусть в начале у процесса 0 находится монопольное право на синхр. переменную. Тогда ему не придется делать запрос и ждать ответов.

Тогда общее время 53*1844 = 97732.

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

Решение:

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

каналы пусты и множество строго консистентно. Однако, стоит обратить внимание, что координатор уже посылал всем служебные сообщения,

так что его каналы проверять не нужно. У нас остается 17 ЭВМ, которые хотят проверить по 16 каналов каждая. ЭВМ запоминают, по каким

каналам им приходят эти служебные сообщения. Если придут по всем 16, посылают сообщение координатору с указанием того, что они

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

SM – ServiceMessage;

IM – ImplementMessage.

T1 – фиксация консистентного множества контрольных точек;
17*16*(Ts+Tb*SIZE_SM) – проверка каналов;

17*(Ts+Tb*SIZE_OK) – уведомления о готовности;

17*(Ts*Tb*SIZE_IM) – фиксация пробных точек.

Пусть все служебные сообщения занимают по 1 байту.

Ответ: T = T1 + 306(Ts+Tb) = T1 + 30906

Решение очень неэффективное

===Удовлетворительно

Надо сделать так, чтобы множество контрольных точек создавалось после доставки неслужебных сообщений. Для этого, перед синхронным алгоритмом создания консистентных точек координатор рассылает всем чтобы они не отправляли неслужебные сообщения. Они ему отвечают ОК. Дальше идет синхронная фиксация консистентного множества точек. Т.к. в это время не было не доставленных неслужебных сообщений, множество будет строго консистентным. Пусть служебные сообщения по 1 байту. Получили 17 сообщений от координатора, чтобы не отправляли неслужебные сообщения = 17*(100+1) = 1717. 17 ответов = 1717. В итоге общее время Т1+2*1717=Т1+3434

Ответ: Т = Т1 +3434

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

Я думал что единая очередь…

Тогда лучше оставлю предыдущее решение.

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

Решение: Покажем на картинке. Стрелками показаны передачи максимумов.

Как видно, нахождение максимума выполняется за 6 шагов. 1-4 шаги само нахождение максимума, 5-6 шаги рассылка. Пусть под число отводится байт.

Ответ: T = 6*(Ts+1*Tb) = 6*(200+1*0) = 1200

В случае 8*8, модифицируем приведенное решение. Делим на 4 четверти по 4*4. В каждой четверти выполняем 1-4 шаги. Потребуется еще 2 шага для перессылки максимумов каждой четверти к центральным узлам

(от (2,2) => (3,3) и т.д.). Еще 2 шага для нахождения глобального максимума (аналогично шагам 3-4 в случае 4*4), еще 6 шагов, чтобы разослать остальным узлам результат. Получили 4+2+2+6 = 14 шагов.

Ответ: T = 14*(Ts+1*Tb) = 14*(200+1*0) = 2800

===Отлично

1. Имеется механизм двоичных семафоров. Опираясь на него, реализуйте функции POST(имя переменной-события) и WAIT(имя переменной-события), которые используются в нижеприведенном алгоритме метода последовательной верхней релаксации? Оцените, насколько этот алгоритм можно выполнить быстрее, чем последовательный, если число процессоров мультипроцессора = N, время выполнения одного оператора присваивания (A[i][j]=....) равно 1, временами выполнения остальных операторов можно пренебречь.

float A[L1][L2];

semaphore s[L1][L2]; /* массив двоичных семафоров
с нулевым начальным значением */

for (j = 0; j < L2; j++) { post(s[0][j]) }

parfor (i = 1; i < L1-1; i++)

for (j = 1; j < L2-1; j++)

{ wait( s[i-1][j]);

A[i][j] = (A[i-1][j] + A[i+1][j] + A[i][j-1] + A[i][j+1]) / 4;

post(s[i][j]);

}

Решение:

Время последовательного выполнения программы:

T_L=(L1-2)*(L2-2)

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

N ≤ L1-2; N ≤ L2-2; (L1-2)modN=0;

Картинка непонятна. Как распределяются витки циков между процессорами?

Смысл картинки описывается ниже в тексте.

Следующий кусок кода говорит о том, что строки можно обрабатывать параллельно, а каждую строку надо обрабатывать последовательно.

“parfor (i = 1; i < L1-1; i++)

for (j = 1; j < L2-1; j++) ”

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

Есть L1-2 строк и N процессоров – какие строки будет обрабатывать каждый процессор – напишите яснее. Статически строки приписываются к процессору или динамически?

Можно распределять и статически и динамически.

Динамическое распределение. Первым N процессорам рандомно распределяем первые N строк. Если процессор обработал свою строку, то ему даем на обработку нераспределенную строку с наименьшим номером.

Статическое распределение. Не ограничивая общность рассуждений, например: строки с номерами 1, N+1, 2*N+1,…, L1-1-N первому процессору; строки 2, N+2,…, L1-N второму процессору;…; строки с номерами N, 2* N,…, L1-2 распределяем N-ому процессору ( можно по-другому, но главное чтобы каждая вышеуказанная группа строк попала отдельному процессору).

И в динамическом, и статическом распределении картина будет примерно одинакова. А именно, строки будут распределяться с шагом (номеров) N одному и тому же процессору.

Строки распределяются поровну между всеми процессорами, что исходит из условия что мы наложили (L1-2)modN = 0. В общем случае, максимальная степень параллелизма определяется величиной M = min(L1-2; L2-2; N).

Ячейку можем обработать только если соседняя сверху ячейка уже обработана ( т.е. только если уже объявлено событие s[i-1][j]).

В картинке иллюстрируется массив A, серым цветом закрашены первый и последний столбцы, первая и последняя строки (которые не обрабатываются). Красным цветом закрашена и обозначена числом «1» ячейка, обрабатываемая в шаге/моменте времени 1. Желтым цветом и числом «2» - ячейки, обрабатываемая в шаге 2, и т.д. Аналогично фиолетовым цветом и числом “N” обрабатываемые в шаге N. На картинке я хотел показать как протекают первые N шагов, и проиллюстрировать этап разгона (определение вводится ниже). Этап торможения (определение вводится ниже) происходит аналогичным образом .(это в силу условия

«(L1-2)modN=0»), но в отличии от разгона, с каждым шагом количество обрабатываемых ячеек уменьшается на единицу. В первые N-1 и последние N-1 шаги задействованы не все процессоры. В остальное время – все. Я вычел число ячеек, обрабатываемые за разгон и торможение, из общего числа ячеек, которых надо обработать. Полученный результат поделил на N, получив тем самым время, когда задействованы все процессоры. Добавил к нему время разгона и торможения, и получил итоговое время. Поделив время последовательного выполнения на полученное время, получил ускорение.

Первый шаг – 1 присваивание;

Второй шаг – 2 присваивания;

……………………………..

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

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