Учебное пособие москва мади 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 
известен процесс, выполняющий вычисления медленнее других и время на 
обработку каждого кирпича одинаково. В этом случае, для этого процесса, 
можно уменьшить объем количество кирпичей. Таким образом, удастся 
избежать простоев, и каждый процесс будет затрачивать равное время на 
вычисления. Иначе нагрузка процессоров должна балансироваться 
динамически.