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

 
Глава 9. Базовые методы построения параллельных алгоритмов 
конвейерный параллелизм; диффузная балансировка 
загрузки 
9.1. Конвейерный параллелизм 
При конвейерном выполнении работ 
n-й
каменщик укладывает 
n-й
слой кирпичей. На рисунке 29 слои одного цвета укладываются одним 
каменщиком. После того, как первый полностью уложит первый слой,
он 
продолжает укладку слоя 
p + 1.
Таким образом, первым начать работу может 
только первый каменщик, а остальные - ожидать укладки нижних слоев. 
Время ожидания будет самым большим у последнего каменщика. В конце 
работы первый каменщик будет ждать, пока работу закончат все остальные.
Рис. 29. Пример укладки слоев каменщиками 

---

88 
При высокой и длинной стене большинство каменщиков будет 
равномерно загружена (при условии неизменности объема работ, одинаковой 
скорости работы каменщиков, одинаковом времени укладки одного кирпича) 
. 
Предложенная стратегия имеет низкую эффективность в связи с тем, 
что при укладке нового кирпича в верхнем слое появляется потребность в 
сообщении о наличии соответствующего кирпича в нижнем слое. На рис. 30 
представлен 
случай 
распределения 
данных 
аналогично 
методу 
геометрического параллелизма. 
До тех пор, пока нулевой процессор не закончит обработку n/p точек с 
номерами 
[0, n/p – 1]
другие процессоры будут находиться в
состоянии 
ожидания. Данная ситуация проиллюстрирована на рис. (рис. 30 а).
Процессор один получит информацию о точке с номером 
(n/p – 1)
только после окончания обработки 
n/p
точек будут. Таким образом, в работе 
будут участвовать два процессора: 
- процессор 0 ‒ вычисление значений третьего слоя в узлах 
[0, n/p – 1]; 
- процессор 1 – вычисление значений второго слоя в узлах