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

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

---

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