Понятие о матрице независимости в граф-схемах алгоритмов

Для определения возможности распараллеливания операторов необходимо провести анализ независимости операторов по данным и по управлению. Для этих целей вводится матрица независимости операторов М.

Симметричная матрица , где — операция дизъюнкции булевой алгебры; , если , и , если для i =1,...,RST и j = 1,..., RST (не треугольная, а получается зеркальным отображением относительно главной диагонали из ранее полученной треугольной); L(i,j) —- матрица логиче­ской несовместимости, называется матрицей независимости опера­торов.

Матрица М отражает информационно-логические связи между операторами без учета их ориентации и с учетом транзитивных свя­зей и логической несовместимости операторов.

Следует отметить, что в соответствии с определением для информационного графа матрица М совпадает с матрицей S'.

Операторы и - взаимно независимые (ВНО), если в матрице независимости .

Операторы , , образуют полное множество ВНО, если для любого оператора существует пара элементов матрицы независимости , .

Множество, содержащее наибольшее число элементов для данного графа, называется максимально полным.

Пусть некоторый алгоритм представлен информационно-логической граф-схемой. По нулевым элементам матрицы независимости М в строке каждого оператора можно указать множество тех операторов, каждый из которых при выполнении некоторых условий может быть выполнен одновременно с данным, т.е. он информационно или по управлению не зависит от данного и не является с ним логически несовместимым.