Нижняя оценка минимального времени выполнения данного алгоритма на ВС
Алгоритм 6.
-
Первоначально полагаем
- Организуем перебор всех отрезков [?1, ?2]
[0, T] в той же последовательности, что и в предыдущем алгоритме. (В процессе выполнения данного алгоритма значение T может увеличиваться, что при данном порядке перебора не приведёт к усложнению алгоритма.)
-
Для очередного анализируемого отрезка времени [?1, ?2] находим значение
d =
(T)(?1,?2) - n(?2 - ?1)
- Если d > 0, выполняем операцию T := T + ] d/n [.
- Полагаем ?2j(T) := ?2j(T) + ] d/n [ , j = 1 , ... , m.
После перебора всех отрезков [?1, ?2] окажется найденным окончательное значение T — нижняя оценка минимального времени выполнения данного алгоритма на данной ВС.
Пример.
Произведём оценку T для графа G, рассмотренного в предыдущем примере, и ВС, состоящей из двух процессоров, n = 2 (рис. 7.20).
увеличить изображение
Рис. 7.20. Оценка снизу минимального времени выполнения работ
Рис. 7.20. Окончание
Первоначально находим
После перебора всех отрезков, с учётом уточнения оценки времени в процессе этого перебора, окончательно находим T = 4.
