ПОНЯТИЕ О МАТРИЦЕ НЕЗАВИСИМОСТИ В ГРАФ-СХЕМАХ АЛГОРИТМОВ.

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

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

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

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

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

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

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

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

ВЗАИМНО НЕЗАВИСИМЫЕ ОПЕРАТОРЫ. ОПРЕДЕЛЕНИЕ ВЗАИМНОЙ НЕЗАВИСИМОСТИ. ПОЛНЫЕ И МАКСИМАЛЬНО ПОЛНЫЕ МНОЖЕСТВА ВЗАИМНО НЕЗАВИСИМЫХ ОПЕРАТОРОВ.

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

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

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

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

АЛГОРИТМ НАХОЖДЕНИЯ ПОЛНЫХ МНОЖЕСТВ ВЗАИМНО НЕЗАВИСИМЫХ ОПЕРАТОРОВ.

Алгоритм.

1.Пусть W — массив полных множеств ВНО. Максимальное полное множество ВНО обозначим как А, а l — число элементов в нем. Очередное формируемое множество ВНО обозначим как D, d – количество элементов в нем. Номер очередного найденного нулевого элемента в строке обозначим как k. Изначаль­но положим, что стек пуст, W = Ø, А = Ø, l =0, D=Ø, d =0, k=0.

2.Загрузим очередную i-ю строку в стек, где i = 1,..., п; n — размер матрицы М. Положим D = {i} , d= 1, k=i. Если все строки обработаны, то выполнение алгоритма заканчивается: най­дены все полные множества ВНО (W) и определено максимальное (А).

3.В строке-вершине стека найдем очередной нуль, занимающий позицию j > k. Если нуль найден, то перейдем к выполнению шага 6, иначе выполним следующий шаг.

4.Если такого нуля нет или все нули найдены, выполняем про­верку на полноту найденного множества D. Если в строке-вершине стека все нули соответствуют всем операторам из D, то найденное множество полное. Произведем сохранение W_m = D и перейдем к шагу 7. Если в строке-вершине есть хотя бы один нуль, не соответ­ствующий операторам из D, то найденное множество не является полным. Переходим к следующему шагу.

5.Исключим из стека строку-вершину (не будем забывать, что, исключая строку, мы уничтожаем и текущие значения k и D, ивоз­вращаемся к их предыдущим значениям). Если после этого стек ис­черпан, выполним шаг 2. В противном случае выполним шаг 3.

6.В текущей вершине стека присвоим k:= j. Складываем логи­чески (поэлементная дизъюнкция) строку, исключая поля k u D из вершины стека, со строкой с номером j — формируем новую вершину стека. В новой вершине стека формируем множе­ство . Перейдем к шагу 3.

7.Сравним значения d и l. Если d > l, то А := D, l := d. Неза­висимо от результата сравнения перейдем к шагу 5.

Конец алгоритма.