ВУЗ:
Составители:
83
а) б) в)
Рис. 6.5 Выявление контуров в графе: а – исходная матрица; б, в – матрицы –
дополненные транзитивными связями (1-й шаг и 2-й шаг соответственно)
Вернемся к исходному примеру. Для того чтобы в явном виде показать, ка-
кие операторы не могут выполняться параллельно, необходимо использовать
только информационные связи. Дело в том, что эти связи прямо указывают на
то, какие операторы не могут выполняться одновременно. Например, в схеме на
рис. 6.2 операторы 3, 4 не могут выполняться не только одновременно, но даже
при одной реализации алгоритма. Такие операторы называются логически не-
совместимыми. Для выявления таких операторов используются матрицы L - ло-
гической несовместимости. Рассмотрим методику их формирования.
6.4. Выявление логически несовместимых операторов
Вначале по исходной треугольной матрице S, в которой связи по управле-
нию отмечены знаком C, а связи по информации – I, формируются задающие
связи логической несовместимости операторов по следующим правилам. По-
следовательно просматривают столбцы j=1,m матрицы S. Если очередной эле-
мент (i
,j)=C и ранее в этом столбце также были зафиксированы элементы
(i
k
,j)= C, k=1,
–1, то все элементы в i
-й строке с номером, совпадающим с
номером строки, в которой ранее встречался знак C, заполняются единицами до
i
-1 -го столбца включительно. Для каждой заполненной описанным способом
единицы затем в матрицу вносится симметричная относительно главной диаго-
Страницы
- « первая
- ‹ предыдущая
- …
- 81
- 82
- 83
- 84
- 85
- …
- следующая ›
- последняя »
