- 9 -

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

Покажем, что во втором случае оператор x i j l включается в объединённый граф путём ввода одной дуги. Действительно, в этом случае нельзя уменьшить время начала выполнения оператора x i j l, из-за увеличения числа процессоров, требуемых для решения системы независимых алгоритмов. Следовательно, существует хотя бы один оператор x s, такой, что выполняется условие

(6) u s = u i j l - t i l.

В этом случае, для включения оператора x i j l в объединённый граф G*, достаточно введения дуги x s -> x i j l.

Если для оператора x i j l выполняется условие (4) и не существует оператора x s, удовлетворяющего условию (б), тогда для включения оператора x i j l в объединённый граф может потребоваться ввод дополнительного оператора x k.

Рассмотрим непустое множество А = { 0, u p} для всех u p}, удовлетворяющих условию

(7) u p =< u i j l - t i l.

Обозначим максимальный элемент этого множества u s. Если для u s выполняется условие (6), введём дугу x s -> x i j l. В противном случае, введём дополнительный оператор x k, начало выполнения которого соответствует моменту времени u s, а окончание u i j l - t i l. Из выполнения условия (4) для оператора x i j l вытекает выполнение условия (3) для оператора x k. Если значение u s отлично от нуля, то введём связи между операторами x s -> x k -> x i j l, в противном случае - только связь x k -> x i j l.

Постоянный адрес статьи в Интернет: http://www.ispl.ru/viniti_9.html

Ключевые слова: число процессоров, объединенный граф, дуга, связь, оператор

Информационные технологии
Главная
(C) Л.Точилов