Учебное пособие москва мади 2020 ббк 32. 81 В 683 Волосова, А. В. В683

τ
с 
* n/p.
Укладку кирпича на левой границе 
0
стены 
предваряет вычисление в процессе с номером rank функции, которая 
обеспечивает получение сообщения, поступающего от процесса с номером 
(rank 
–
1).
Процесс с номером 
(rank 
–
1) 
отвечает за выполнение функции 
передачи 
необходимых 
данных. 
Двусторонний 
обмен 
данными 
осуществляется между процессом rank и процессом 
rank 
–
 1
в общем случае. 
Таким образом каждые два соседних процесса обмениваются сообщениями, 
число которых равно двум. Все процессы, не являющиеся первыми и 
последними в цепочке, обмениваются четырьмя сообщениями с соседями. 
Оптимальное время работы составит:
Алгоритм, обеспечивающий это время
: 
for(шаг = 

; шаг { 
for(кирпич = rank*n/p; кирпич <(rank+1) * n/p; кирпич ++)
Уложить
(
кирпич
) 
if(rank %2 ) 
{if(rank > 

) Send (rank-1, 
кирпич
уложен
) 
if(rank > 

) Recv (rank-1, 
место
готово
? )
if(rank < p-1) Recv (rank+1, 
место
готово
? ) 
if(rank < p-1) Send (rank+1, 
кирпич
уложен
)
} 
else 
{ 
if(rank < p-1) Recv(rank+1, 
место
готово
? ) 
if(rank < p-1) Send(rank+1, 
кирпич
уложен
)
if(rank > 

) Send(rank-1, 
кирпич
уложен
) 
(12)

---

86 
if(rank > 

) Recv(rank-1, 
место
готово
? )
} 
}
Порядок операций обмена данными в алгоритме представлен на рис. 28 а.
Эффективность
и ускорение алгоритма
Приведенные выше оценки имеют смысл при выполнении следующих 
условий:
-
количество кирпичей для процессов –
одинаково;
-
от положения кирпича в стене не зависит количество операций, 
выполняемых при его укладке;
-
производительности процессов;
-
латентности и пропускные способности каналов передачи данных 
равны.
На практике эти условия выполняются только приближенно в связи с 
наличием процессов, которые при укладке ряда кирпичей выполняют шаги 
за разное время. Примером может служить работа каменщиков на крайних 
участках стены. Если известны трудоемкость укладки каждого кирпича и 
производительность каждого процессора, то при статической балансировке 
можно улучшить показатели следующим образом: предположим, что заранее 
Рис. 28 а. 
Распределения данных аналогично методу геометрического
параллелизма
(13)

---

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