Ответы на задачи (1162829), страница 2
Текст из файла (страница 2)
Сколько времени потребуется для этого, если всепроцессы выдали ее одновременно. Время старта равно 100, время передачибайта равно 1 (Ts=100,Tb=1). Процессорные операции, включая чтение изпамяти и запись в память, считаются бесконечно быстрыми.Pr-0 A0 A1 A2 A3SCATTERA0èPr-1A1Pr-2GATHERA2çPr-3A31 сообщение6+0 циклов2 сообщение4+1, 5+1 циклов3 сообщение4+2 циклов4 сообщение3+3 циклов7 сообщение1+6, 2+6 циклов5 сообщение3+4 циклов8 сообщение1+7 циклов6 сообщение2+5 цикловИтого данные будуь получены через 8 циклов, т.е 8*(Ts+N*Tb)74. В транспьютерной матрице размером 4*4, в каждом узле которой находитсяодин процесс, необходимо выполнить операцию нахождения максимумасреди 16 чисел (каждый процесс имеет свое число). Сколько временипотребуется для получения всеми максимального числа, если все процессывыдали эту операцию редукции одновременно. А сколько временипотребуется для нахождения максимума среди 64 чисел в матрице 8*8?Время старта равно 100, время передачи байта равно 1 (Ts=100,Tb=1).Процессорные операции, включая чтение из памяти и запись в память,считаются бесконечно быстрыми.T = 6*(Ts+L*Tb)814*(Ts+L*Tb)5.
В транспьютерной матрице размером 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*Tb6.
В транспьютерной матрице размером 4*4, в каждом узле которой находитсяодин процесс, необходимо переслать сообщение длиной L байт из узла скоординатами (0,0) в узел с координатами (3,3). Сколько времени9потребуется для этого при использовании а) неблокирующих и б)блокирующих операций 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*Tb. Ts*6 время полной загрузки конвейера, 6 – время разгрузки конвейера.10Тема-41. Все 16 процессов, находящихся на разных ЭВМ сети с шинной организацией(без аппаратных возможностей широковещания), одновременно выдализапрос на вход в критическую секцию. Сколько времени потребуется дляпрохождения всеми критических секций, если используется древовидныймаркерный алгоритм (маркером владеет нулевой процесс). Время старта(время «разгона» после получения доступа к шине для передачи сообщения)равно 100, время передачи байта равно 1 (Ts=100,Tb=1).
Доступ к шине ЭВМполучают последовательно в порядке выдачи запроса на передачу (приодновременных запросах - в порядке номеров ЭВМ). Процессорныеоперации, включая чтение из памяти и запись в память, считаютсябесконечно быстрыми.11091263513107811121415401.R912.R265.R37.R513108.R713.R10.R6.R3.R9.R11.R812.R 14.R111215.R14154.R4Ts*15+Tb*Lz*15После этого все процессы знают, куда направлять маркер, когда он придет.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*Lm)*15+(Ts+Tb*Lm)*27.Считая сообщение маркера очень коротким, получим 42*Ts2.
Все 16 процессов, находящихся на разных ЭВМ сети с шинной организацией(без аппаратных возможностей широковещания), одновременно выдализапрос на вход в критическую секцию. Сколько времени потребуется дляпрохождениявсемикритическихсекций,еслииспользуетсядецентрализованный алгоритм с временными метками. Время старта (время12«разгона» после получения доступа к шине для передачи сообщения) равно100, время передачи байта равно 1 (Ts=100,Tb=1).
Доступ к шине ЭВМполучают последовательно в порядке выдачи запроса на передачу (приодновременных запросах - в порядке номеров ЭВМ). Процессорныеоперации, включая чтение из памяти и запись в память, считаютсябесконечно быстрыми.1501412131231141059815670151411421301213123111231141041059876(Ts+Tb*Lm)*155987613Взяв любой другой процесс, мы получим ту же картину: надо разослать 15 запросов и получить 15ответов. При этом мы считаем, что время прохождения КС=0.
Тогда получается, что надо простоумножить время получения разрешения 0-м процессом на 16.16*15*( Ts+Tb*Lm)Если же мы предположим, что внутри КС проводится отличное от 0 время, тогда надо будетучитывать, что некоторые сообщения не зависят от того, находится ли другой процесс в КС или нет.3. Все 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).4. 15 процессов, находящихся в узлах транспьютерной матрицы размером 4*4,одновременно выдали запрос на вход в критическую секцию. Скольковремени потребуется для прохождения всеми критических секций, еслииспользуется централизованный алгоритм (координатор расположен в узле0,0)? Время старта равно 100, время передачи байта равно 1 (Ts=100,Tb=1).Процессорные операции, включая чтение из памяти и запись в память,считаются бесконечно быстрыми.15*3 (Ts+Tb*L)5. Сколько времени потребует выбор координатора среди 16 процессов,находящихся на разных ЭВМ сети с шинной организацией (без аппаратныхвозможностей широковещания), если используется алгоритм «задиры»?«Задира» расположен в узле с координатами (0,0) и имеет уникальный номер0.
Время старта (время «разгона» после получения доступа к шине дляпередачи сообщения) равно 100, время передачи байта равно 1 (Ts=100,Tb=1).Доступ к шине ЭВМ получают последовательно в порядке выдачи запросана передачу (при одновременных запросах - в порядке номеров ЭВМ).Процессорные операции, включая чтение из памяти и запись в память,считаются бесконечно быстрыми.6. Сколько времени потребует выбор координатора среди 16 процессов,находящихся в узлах транспьютерной матрицы размером 4*4, еслииспользуется круговой алгоритм? Время старта равно 100, время передачибайта равно 1 (Ts=100,Tb=1).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
