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

UptoLike

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

Рубрика:

Вначале по матрице S, дополненной транзитивными связями, строят мат-

рицу следования S' путем симметричного отображения элементов матрицы S

относительно главной диагонали (т.е. путем сложения матрицы с ее транспони-

рованной). Далее на сформированную матрицу S' накладывают матрицу L, до-

полненную транзитивными связями. Каждый элемент новой матрицы M фор-

мируется из одноименных элементов матриц S' и L по правилу дизъюнкции.

Нулевые элементы полученной матрицы M указывают множество тех операто-

ров, каждый из которых при выполнении некоторых условий может быть вы-

полнен одновременно с данным, т.е. он информационно или по управлению не

зависит от этого оператора и не является с ним логически несовместимым. На

рис. 6.8 приведены построенные по указанному правилу матрицы S' и M.

Симметричную матрицу M называют матрицей независимости. Она отра-

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

тации, а также связи логической несовместимости операторов с учетом всех

транзитивных связей. Например, из матрицы M следует, что оператор 2 может

выполняться независимо, а следовательно, если необходимо, то и параллельно с

операторами 5 и 8, однако нельзя говорить об их взаимной независимости, так

как существует связь 58. Если не рассматриваются связи по управлению, то

матрица независимости M совпадает с матрицей следования S, дополненной

транзитивными связями.

а) б)

Рис. 6.8 Матрица следования S' (а) и соответствующая

матрица независимости M= S'L (б)