(2016) Ответы (1162879), страница 8
Текст из файла (страница 8)
Дайтеоценку накладных расходов на синхронную фиксацию строго консистентногомножества контрольных точек для сети из 10 ЭВМ с шинной организацией (безаппаратных возможностей широковещания), если накладные расходы насинхронную фиксацию консистентного множества равны Т1. Время старта(время «разгона» после получения доступа к шине для передачи сообщения)равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Доступ к шине ЭВМполучают последовательно в порядке выдачи запроса на передачу (приодновременных запросах – в порядке номеров ЭВМ). Процессорные операции,включая чтение из памяти и запись в память, считаются бесконечно быстрыми.1.
Множество контрольных точек называется строго консистентным, если во времяего фиксации никаких обменов между процессами не было.2. Множество контрольных точек называется консистентным, если для любойзафиксированной операции приема сообщения, соответствующая операцияпосылки также зафиксирована (нет сообщений-сирот).Простой метод фиксации консистентного множества контрольных точек - фиксациялокальной контрольной точки после каждой операции посылки сообщения.Синхронная фиксация контрольных точек и восстановление. Требование: надежнаяпередача сообщений (сообщения всегда приходят, схема FIFO).Два вида точек – постоянная (уже точно установлена) и пробная – становится постояннойпосле окончания работы алгоритма.Сохранение:● процесс создает пробную точку, посылает всем уведомление● все создают пробную точку, отвечают процессу-инициатору, при этом нельзяпосылать неслужебные сообщения● процесс шлет всем информацию о создании новой постоянной точки, пробнаястановится постоянной● Оптимизация: если не было сообщений после последней контрольной точки, томожно не создавать новую.Восстановление:● инициатор шлет всем сообщение о подготовке к откату● все отвечают, что готовы, после этого до конца алгоритма не посылаетсянеслужебных сообщений● инициатор шлет сообщение об откате, все откатываются● Оптимизация: если не было сообщений с момента фиксации, то можно неоткатываться.Асинхронный алгоритм.
Фиксация может производиться асинхронно. В этом случаемножество контрольных точек может быть не консистентным. При откате происходитпоиск подходящего консистентного множества путем поочередного отката каждогопроцесса в ту точку, в которой зафиксированы все посланные им и полученные другимисообщения (для ликвидации сообщений-сирот). Алгоритм опирается на наличие встабильной памяти для каждого процесса журнала, отслеживающего номера посланных иполученных им сообщений, а также на некоторые предположения об организациивзаимодействия процессов, необходимые для исключения «эффекта домино» (например,организация приложения по схеме сообщение-реакция-ответ).Решение задачи:1-ая фазаИнициатор сообщает всем о начале создания процесса контрольной точки.
Послеполучения сообщения о начале создании контрольной точки, процессу запрещаетсяпосылать неслужебные сообщения (инициатору тоже запрещается). Каждый процессотвечает инициатору списком номеров процессов и сколько сообщений этим процессамбыло отправлено. Инициатор получает от всех ответы, после этого формирует длякаждого процесса сообщение из списка номеров процессов, и сколько сообщений этимипроцессами было отправлено данному процессу.
После принятия всех сообщений,процесс (в том числе инициатор) создает пробную контрольную точку и сообщает обуспехе (или о неуспехе, если процесс не смог создать пробную контрольную точку)инициатору. Если все процессы создали контрольные точки, то инициатор принимаетрешение о превращении пробных контрольных точек в постоянные. Если какой-либопроцесс не смог сделать пробную точку, то принимается решение об отмене всех пробныхточек.2-ая фазаИнициатор информирует все процессы о своем решении. В результате либо все процессыбудут иметь новые постоянные контрольные точки, либо ни один из процессов не создастновой постоянной контрольной точки.
Только после выполнения принятого процессоминициатором решения все процессы могут посылать сообщения.Данный алгоритм отличается от алгоритма для создания просто консистентного тем, чтонадо дополнительно отправлять списки процессов и количества сообщений.
Пусть подномер процесса и количество сообщений отведем по 1 байту. Тогда сообщения со спискомпроцессов и количеством сообщений от данного процесса занимают 9*(1+1)= 18 байт. 9 –потому что всех процессов – 10, и надо знать сколько сообщений ожидать от всехпроцессов кроме себя. А инициатору тоже отправляется список кому и сколькосообщений было отправлено, тоже кроме себя. Такие обмены списками происходитдважды между каждым процессом и инициатором. Каждый обмен занимает Т2 = Ts +18*Tb. Всего обменов 9*2 = 18.Ответ: Общее время Т = Т1 + 18*Т2 = Т1 + 2124.Тема-8 (на экзамене не будет (совсем не будет))Дополнительные задачи1. Какую модель консистентности можно реализовать в мультипроцессорах (с общейпамятью)?Ответ:Последовательную.
Строгую не можем, так как у процессоров имеется кэш.2. MPI. В синхронизационном режиме отправка сообщения не начинается, пока упроцесса, который должен принять сообщение, не появится RECEIVE. А как мы этоузнаем?Ответ:Процесс, в котором появился SEND, должен отправить запрос, есть ли на другомконце RECEIVE. Это должен сделать именно он, так как:1. он знает получателя (второй процесс может не знать отправителя),2. он знает, что отправка будет производиться в синхронизационном режиме(получатель не может и не должен знать режим).3.
Какую модель консистентности необходимо добавить к причинной, чтобыполученная модель оказалась не слабее процессорной консистентности?Ответ: PRAM консистентность4. Транспьютерная матрица 4x5:Необходимо передать сообщение длиной N=79 байт из A в B. Сколько временипотребуется для этого, если Ts=0, Tb=1. За один такт по одному каналу можно передать 1байт.Решение:Разделяем на 4 маршрута. Из левого соседа можно достичь B за 4 такта, из остальных- за 3.
Влево будем передавать 19 байт сообщения, по остальным направлениям - по 20.Время для передачи сообщения длины L на расстояние K - T=T1+T2, где T1 - времязаполнения конвейера (по сути - передача первого байта), T2 - время передачи всехчастей, кроме первой:T1=K*(Ts+Tb),T2=(L-1)*(Ts+Tb).В нашем случае по левому направлению время T1=5, T2=18; по остальным трём T1=4, T2=19.Ответ: T = 23.См. также esyr.org.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
