Учебное пособие москва мади 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, на узлы которого замыкаются все выходящие из 
доменов первого вида ребра.
В случае обработки домена единственным процессором теряется 
эффективность, которая компенсируются снижением числа конфликтов кэш
-
памяти