- 11 -

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

Воспользуемся теоремой 2 для нахождения минимального числа процессоров и плана выполнения системы независимых алгоритмов. Для этого требуется построить граф-решение G', удовлетворяющий условиям теоремы 2. Построение граф-решения системы независимых алгоритмов G' проведем в три этапа.

Алгоритм I.

1. Алгоритм 2.1 (Барский) ( [1], стр.57) построения G' для одного алгоритма модифицируем следующим образом.
а). Поиск значений ранних { u _{1 i j l} } и поздних { u _{2 i j l} } ,

i = 1, ..., n; j = 1, ... , K*/K _i; l = 1, ..., M _i сроков окончания выполнения операторов осуществляется отдельно для всех n, независимых алгоритмов системы на временных отрезках [ 0, T _i ], i = 1, ..., n. Для операторов тех же алгоритмов, но выполняющихся на временных отрезках [ ( j - 1) ^. T _i , j ^. T _i ], i = 1, ..., n; j = 2, ..., K*/K _i значения сроков окончания получаются сдвигами на величины ( j - 1) ^. T _i , соответственно.

б). Вместо проверки ограничения времени окончания выполнения операторов значением T, введём проверку выполнения временных ограничений (2) на систему независимых алгоритмов (1).

2. Выполним полученный алгоритм.

3. Введём дополнительные операторы, удовлетворяющие условию (3). Получим граф-решение G' для системы независимых алгоритмов.