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

Критерии декомпозиции
— требования, предъявляемые к виду 
доменов: равномерное распределение по доменам суммарного веса 
узлов/ребер и минимизация максимального веса исходящих из домена ребер. 
Пусть задан граф 
G
0 
= (V, E), V{v
i
}, |V| = n.
Пусть вершины v
i
и ребра 
e
ij
этого графа имеют веса w(v
i
) и 
w(v
i
, v
j
)
соответственно. Найдем такое 
разбиение 
R(V) =(V
1
, ..., V
p
) 
вершин на заданное число доменов p, при 
котором 
J
- взвешенная сумма весов вершин и разрезанных ребер - 
принимает минимальное значение (32):
множитель 
α
обеспечивает согласование единиц измерения весов вершин и 
ребер, что соответствует критерию. Так как выравнивается вычислительная 
нагрузка, приходящаяся на каждый домен (она ассоциируется с весами 
Рис. 37. Двумерная расчетная сетка 
(32) 

---

123 
вершин) и снижаются коммуникационные затраты, ассоциированные с 
числом разрезанных ребер. Задача декомпозиции сводится к минимизации 
J
. 
Выделение обособленных доменов
На рис. 38 представлена декомпозиция сетки на домены: 
-
с нулевого по пятый - домены первого вида, среди которых нет 
ни одной пары доменов, соединенных ребром;
- 
домен 6, на узлы которого замыкаются все выходящие из 
доменов первого вида ребра. 
В случае обработки домена единственным процессором теряется 
эффективность, которая компенсируются снижением числа конфликтов кэш-
памяти