18c0693f

Нижняя оценка минимального времени выполнения данного алгоритма на ВС


Алгоритм 6.

  1. Первоначально полагаем

  2. Организуем перебор всех отрезков [?1, ?2]

    [0, T] в той же последовательности, что и в предыдущем алгоритме. (В процессе выполнения данного алгоритма значение T может увеличиваться, что при данном порядке перебора не приведёт к усложнению алгоритма.)

  3. Для очередного анализируемого отрезка времени [?1, ?2] находим значение

    d =

    (T)(?1,?2) - n(?2 - ?1)

  4. Если d > 0, выполняем операцию T := T + ] d/n [.
  5. Полагаем ?2j(T) := ?2j(T) + ] d/n [ , j = 1 , ... , m.

После перебора всех отрезков [?1, ?2] окажется найденным окончательное значение T — нижняя оценка минимального времени выполнения данного алгоритма на данной ВС.

Пример.

Произведём оценку T для графа G, рассмотренного в предыдущем примере, и ВС, состоящей из двух процессоров, n = 2 (рис. 7.20).


увеличить изображение
Рис. 7.20.  Оценка снизу минимального времени выполнения работ


Рис. 7.20.  Окончание

Первоначально находим

После перебора всех отрезков, с учётом уточнения оценки времени в процессе этого перебора, окончательно находим T = 4.