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

 
8.3. 
Метод геометрического параллелизма
 
Метод геометрического параллелизма подходит для обработки 
изображений, вычислений, связанных с математической физикой и т.д.
Метод обеспечивает выполнение множества однотипных действий над 
однородными взаимосвязанными данными и эффективен для алгоритмов, 
обладающих свойством локальности:
Рис. 27. Схема рассылки данных

---

84 
При распределении данных по процессорам равными частями следует 
обеспечить 
расположение 
вспомогательных 
данных, 
используемых 
конкретным процессором на минимальном количестве других процессоров и 
объем этих данных должен быть минимальным.
Рассмотрим применение метода на примере.
Пример (
«Стена Фокса») [2]. 
Группе каменщиков необходимо согласовать построить стену. 
Каждый каменщик отвечает за построение участка стены. Все участки 
-
одинаковы. Каменщики начинают работу одновременно с укладывания 
нижнего слоя (рис. 28). Переход к укладке следующего слоя на конкретном 
участке осуществляется при условии окончания работы по укладыванию 
этого слоя на соседних участках. В противном случае возникают простои, 
связанные с синхронизацией работ на соседних участках. 
Вычисления реализуются в системе с распределенной памятью. Каждое 
вычисление выполняется отдельным процессором. 
Пусть 
n
‒
число кирпичей в ряду, 
k 
‒
высота стены, τ
с
‒
время, 
необходимое для укладки одного кирпича, 
T
p
‒
время решения задачи с
помощью p параллельно работающих процессов. В случае одного процесса, 
потребуется последовательно уложить 
n*k
кирпичей:
В случае нескольких процессов, каждому из которых выделяется 
вертикальный участок стены, длина которого составляет 
n/p
, объем полезной
Рис. 28. Геометрическое решение
(11)

---

85 
работы составит