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

UptoLike

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

Рубрика:

нали единица. Матрица следования граф-схемы алгоритма (рис. 6.2) с указани-

ем отдельно связей по управлению и информации и соответствующая ей мат-

рица логической несовместимости операторов L приведены на рис. 6.6.

а) б)

Рис. 6.6. Исходная матрица следования (а) и соответствующая ей

матрица логической несовместимости операторов (б)

Далее на основе заданных связей логической несовместимости определя-

ется несовместимость для всех операторов схемы. Для этого вводятся транзи-

тивные связи логической несовместимости по следующим правилам.

Последовательно просматривают строки треугольной матрицы следования

S, дополненной транзитивными связями (нулевые строки пропускают). В оче-

редной ненулевой i-й строке матрицы S анализируют множество ненулевых

элементов. Из этого множества исключают номера операторов, образующих

входы матрицы S, т.е. обнуляют элементы в столбцах, номера которых совпа-

дают с номерами нулевых строк.

С использованием оставшегося множества номеров операторов (ненулевых

элементов матрицы S) последовательно, начиная с первой строки, формируют

строки i

. Для этого объединяют по операции конъюнкции (И) строки матрицы

L с номерами, соответствующими номерам столбцов матрицы S, в которых ос-

тались ненулевые элементы. Если ненулевой элемент в строке один, то строку

полагают равной строке матрицы L с номером, равным номеру столбца нену-

левого элемента в анализируемой строке.