- 8 -

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

Доказательство.

Необходимость.

Пусть N - наименьшее число процессоров, входящих в состав однородной ВС, реализующих систему независимых алгоритмов (1), удовлетворяя при этом временным ограничениям (2). Следовательно, существует план выполнения системы независимых алгоритмов, такой, что в каждый момент времени выполняется не более N операторов. План выполнения представляет собой набор графов, отнесённых к соответствующим временным интервалам. Докажем, что вводом специальным образом дополнительных связей и операторов, можно свести набор графов, отнесённых к соответствующим временным интервалам, в объединённый граф G*, не увеличив при этом число N процессоров, требуемых для выполнения полученного объединённого алгоритма.

Построение объединённого графа G* проводим следующим образом. Перемещаясь по оси времени, находим первый оператор x _{i j l}, начало выполнения которого отлично от нуля и в который не входит ни одной дуги.

Возможны два случая, либо выполняется условие

(4) u _{i j l} - t _{i l} = (j -1) ^. T _i ,

либо условие

(5) u _{i j l} - t _{i l} > (j -1) ^. T _i .

Если выполняется условие (5), то уменьшим время начала выполнения оператора x _{i j l} насколько возможно, при условии, что система независимых алгоритмов удовлетворяет временным орраничениям (2) и реализуется N процессорами однородной ВС.

Возможны также два случая. Либо, для преобразованной таким образом системы, выполняется условие (4), либо по прежнему условие (5).