Основные теоретические сведения

Для распараллеливания алгоритма необходимо построить две матрицы: S-матрица информационной независимости операторов с учетом транзитивных связей, L-матрица логической совместимости операторов с учетом транзитивных связей, после чего строится матрица независимости операторов M путем вычисления дизъюнкции элементов матриц S и L, т.е. M(i,j)=S(i,j) V L(i,j). Построение указанных матриц производится по заданному информационно-логическому графу (ИЛГ), по которому определяется исходная информационно-логическая матрица (ИЛМ) Sf, элементы которой вычисляются следующим образом:

{ "Л" - если в ИЛГ есть логическая дуга из j в i,

Sf(i,j)={ "И" - если в ИЛГ есть информационная дуга из j в i,

{ "О" - если в ИЛГ вершины i и j не связаны никакой дугой.

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

S(i,j) = { 1, если Sf(i,j) ¹ "0",

{ 0, если Sf(i,j) = "0".

Наличие транзитивных информационных связей учитывается путем расширения матрицы S согласно правилу: если S(i,j)=1 и S(j,k)=1, то S(i,k)=1. Матрица логической совместимости операторов без учета транзитивных связей определяется по матрице Sf следующим образом: если Sf(m,j)="Ù" и Sf(n,j)="Ù" , то L(m,n)=L(n,m)=1, т.е. операторы m и n не могут исполняться в одном проходе алгоритма. Далее матрица L расширяется с учетом транзитивных связей по следующему правилу:

а.) для каждого оператора i=3..N формируется вектор B=(j1, j2, ..., jl), включающий операторы, выходная информация которых используется при выполнении оператора i;

б.) определяется пересечение множеств операторов, логически несовместимых со всеми операторами множества B (путем вычисления конъюнкции соответствующих строк матрицы L);

в.) полученное множество операторов, логически несовместимых с оператором i в силу транзитивных связей объединяется с исходным множеством логически несовместимых операторов (путем вычисления дизъюнкции i-ой строки матрицы L и вектора C, полученного в п.б.). Матрица независимости операторов M вычисляется путем операции дизъюнкции элементов матриц S и L.

Описание алгоритма.

Таблица имен:

 

Имя	Тип	Содержание
N	INTEGER	Количество операторов в ИЛГ
Sf	ARRAY[1..N, 1..N] OF CHAR	Информационно-логическая матрица
S	ARRAY[1..N, 1..N] OF BOOLEAN	Матрица информационной независимости операторов
L	ARRAY[1..N, 1..N] OF BOOLEAN	Матрица логической совместимости операторов
M	ARRAY[1..N, 1..N] OF BOOLEAN	Матрица независимости операторов
A	ARRAY[1..N] OF INTEGER	Вектор номеров логически несовместимых операторов
B	ARRAY[1..N] OF INTEGER	Вектор номеров информационно связанных операторов
C	ARRAY[1..N] OF BOOLEAN	Вектор транзитивных связей логической несовместимости

{ Ввод информационно-логической матрицы и формирование матрицы информационной независимости без учета транзитивных связей. }

Ввод N

Цикл i=1..N

Цикл j=1..i

IF Sf(i,j) =“О” THEN

S(i,j) := FALSE

ELSE

S(i,j) := TRUE

КЦ(*j*)

КЦ(*i*)

Вывод Sf

 

{ Вычисление матрицы информационной независимости с учетом } { транзитивных связей }

Цикл i=1..N

Цикл j=1..i

IF S(i,j) = TRUE , THEN

Цикл K = 1..i

S(i,K) := S(i,K)ÚS(j,K)

КЦ(*K*)

КЦ(*j*)

КЦ(*i*)

Вывод S

 

{ Вычисление матрицы логической совместимости без учета транзитивных } { связей }

 

Цикл i=1..N

Цикл j=1..i

L(i,j) := FALSE

КЦ(*j*)

КЦ(*i*)

Цикл j=1..N-1

K:= 0

Цикл i=j+1..N

IF Sf(i,j) =“Л” THEN

BEGIN

K:=K+1;

A(K):=i ;

IF K>1 THEN

BEGIN

m := A(K)

Цикл p=1..K-1

n := A(p);

L(m,n) := TRUE;

L(n,m) := TRUE

КЦ(*p*)

END

END

КЦ(*i*)

КЦ(*j*)

Вывод L (* без учета транзитивных связей *)

 

{ Вычисление матрицы логической совместимости с учетом транзитивных } { связей }

Цикл i=3..N

K := 0;

Цикл j=2..i

IF S(i,j) = TRUE THEN

BEGIN

K := K+1;

B(K) := j

END

КЦ(*j*)

IF K>0 THEN

BEGIN

m := B(K);

Цикл n := 1..N

C(n) := C(n) ÙL(m,n)

КЦ(*n*)

Цикл j := (K-1) .. 1 шаг -1

m := B(j)

Цикл n := 1..N

C(n) := C(n) ÙL(m,n)

КЦ(*n*)

КЦ(*j*)

Цикл j := 1..N

B(j) := 0;

КЦ(*j*)

Цикл n := 1..N

L(i,n) := L(i,n) ÚC(n)

КЦ(*n*)

Цикл n := 1..N

C(n) := FALSE

КЦ(*n*)

END;

Цикл n := 1..N

L(n,i) := L(i,n)

КЦ(*n*)

КЦ(*i*)

Вывод L (* с учетом транзитивных связей *)

 

{ Вычисление матрицы независимости операторов }

Цикл i := 1..N

Цикл j := 1..N

IF j<i THEN

M(i,j) := S(i,j)ÚL(i,j)

ELSE IF j=i THEN

M(i,j) := 0

ELSE

M(i,j) := S(j,i)ÚL(i,j)

КЦ(*j*)

КЦ(*i*)

Вывод M