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

UptoLike

ВУЗ: 

СГАУ | Самара

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

Рубрика: 

82
связи могут быть введены путем формальных преобразований матрицы S по
следующему алгоритму.
Строки матрицы просматриваются последовательно сверху вниз. В каждой
(i-й) строке просмотр элементов производится в порядке увеличения номеров
столбцов. Если в очередном (j-м) столбце имеется знак , указывающий на су-
ществование связи по информации или управле-
нию, одноименные элементы строк с номерами i
и j складываются по правилу дизъюнкции (или):
=, 0=, 0=, 00=0, т.е. в просматривае-
мую строку добавляются все знаки , которые
имеются в j-й строке. На рис. 6.4 приведена тре-
угольная матрица следования, полученная из
матрицы, показанной на рис. 6.3, путем ее до-
полнения транзитивными связями.
При построении алгоритмов распараллели-
вания часто приходится иметь дело с матрицами
следования общего (не треугольного) вида. Если исходная матрица не тре-
угольная, просмотр строк матрицы S производится неоднократно до установле-
ния факта ее неизменности. В результате указанных преобразований вводятся
транзитивные связи, с помощью которых устанавливается факт наличия конту-
ра в информационно-логическом графе. О наличии контуров свидетельствуют
ненулевые диагональные элементы.
Например, если предположить, что в рассматриваемом примере кроме ука-
занных на рис. 6.2 и 6.3 связей существует также связь 104, матрица следо-
вания будет иметь вид, показанный на рис. 6.5, а. В результате двух шагов до-
полнения матрицы транзитивными связями, показанных на рис. 6.5, б и в мат-
рица окончательно принимает неизменный вид, который показан на рис. 6.5, в.
Эта матрица имеет ненулевые диагональные элементы (4,5,8,9,10), что указыва-
ет на существование контура. Нетрудно заметить, что именно операторы с ука-
занными номерами входят в этот контур.
Рис. 6.4. Матрица следова-
ния S, дополненная транзи-
тивными связями

Страницы