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

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

---

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

---

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