- 6 -

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Временные ограничения (2) приводят в частности к тому, что план выполнения системы независимых алгоритмов (1) на минимальном числе процессоров предполагает возможность простоев процессоров. Поэтому, для представления плана выполнения системы независимых алгоритмов в виде графа, может потребоваться введение дополнительных операторов, с целью исключения разрывов.

Докажем теорему, что возможно построение искомого графа-решения G', путём ввода дополнительных связей и операторов x_k , удовлетворяющих условию

(3) u_k = j ^.T_i , для некоторых i и j.

Предварительно приведём ряд используемых в дальнейшем определений и формулировок.

Определение 2. (Барский) ( [I], стр.30 ).

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

Определение 3. (Барский) ( [I], стр.31 ).

Операторы a и b будем называть взаимно независимыми операторами (ВНО), если в матрице независимости M(a,b)=(b,a)=0.

Определение 4. (Барский) ( [I], стр.31 ).

Операторы {a_i }, i=1,...,s, образуют полное множество ВНО, если для любого оператора j, не принадлежащего множеству {a_i } существует пара элементов матрицы независимости М(a_i , j) = (j, a_i ) = 1, i принадлежит множеству {1,...,s}.