Лекции по параллельным вычислениям. Гергель В.П - 87 стр.

UptoLike

ВУЗ: 

СГАУ | Самара

Составители: 

Рубрика: 

87
Говорят, что
и
взаимно независимые операторы (ВНО), если в матрице
M(
,
)=(
,
)=0. Операторы {
i
}, i=1,…,s образуют полное множество ВНО,
если для любого оператора j{
i
}, существует пара элементов матрицы незави-
симости M(
i
,j)=(j,
i
)=1, i{1,…,s}. При решении задач распараллеливания не-
обходимо перебирать все возможные полные множества ВНО и находить мак-
симально полное множество ВНО, содержащее максимальное число операто-
ров. Для его нахождения используется следующее свойство. Если два операто-
ра
и взаимно независимы, то при сложении по правилам дизъюнкции
-й и
-й строк матрицы независимости M образуется строка, в которой элементы в
-м и
-м столбцах обязательно нулевые.
Процедуру выявления максимально полного множества ВНО рассмотрим
на примере матрицы, представленной на рис. 6.8, б. При сложении десятой
строки матрицы M (по правилу дизъюнкции) с остальными строками получа-
ются строки, содержащие все единичные элементы. Следовательно, оператор
10 образует полное множество ВНО. При сложении строк, соответствующих
операторам 1 и 2, получается строка с нулевыми элементами в 1 и 2 столбцах.
Следовательно, {1,2} - полное множество ВНО с числом элементом, превы-
шающим ранее найденное. Множества с двумя элементами образуют также
операторы {1,6}, {2,3}, {2,4}, {3,6}, {4,6}, {5,6}, {6,7}, {6,8}, {6,9}. Установ-
ленные полные множества ВНО содержат не более двух элементов. При сложе-
нии трех и более строк матрицы M в любых сочетаниях не удается получить
строку, в которой элементы с номерами, совпадающими с номерами склады-
ваемых строк, оказались нулевыми. Следовательно, множество ВНО с двумя
элементами является максимально полным множеством ВНО.
В заключение обратим внимание на тот факт, что начиная с этапа, когда
была построена граф-схема алгоритма, все операции с соответствующими мат-
рицами, включая поиск максимально полного множества ВНО, строго форма-
лизованы и могут быть реализованы в виде алгоритма. Следовательно, нет ни-
каких препятствий для построения полностью автоматических (на указанных

Страницы