Параллельное программирование



              

Временные оценки на информационных графах - часть 5


Графики функции: а — для ранних сроков окончания работ,,б — для некоторого допустимого расписания

Рис. 7.13.  Графики функции: а — для ранних сроков окончания работ,,б — для некоторого допустимого расписания

Для графического представления функции F удобно пользоваться временной диаграммой, которая для второго случая, например, имеет вид, представленный на рисунке 7.14..

Временная диаграмма функции F

Рис. 7.14.  Временная диаграмма функции F

Пусть данный граф G, в котором учтены транзитивные связи, образует l полных множеств взаимно независимых работ (ПМВНР). (Каждая пара таких множеств может иметь непустое пересечение.) Обозначим ri, i = 1 , ... , l, число работ, образующих i-е полное множество и найдём

R = max {r1 , ... , rl}.

Тогда

 \begin{align*} R = \max\limits_{\tau_1,\tau_2 \dts \tau_m} F(\tau_1,\ldots \tau_m, t), \end{align*}

т.к. возможно и такое распределение выполняемых работ во времени, задаваемое набором ?1 , ... , ?m, (т.е. допустимое расписание), когда на каком-то отрезке времени выполняются все работы, составляющие ПМВНР с числом R работ.

Например, для графа на рис. 7.1 мы нашли ПМВНР {3,5,6,7}, включающее четыре работы. Тогда существует допустимое расписание, например, ?1 = 2, ?2 = 3, ?3 = 5, ?4 = 4, ?5 = 8, ?6 = 8, ?7 = 6, ?8 = 9 такое, при котором максимальное значение плотности загрузки F равно четырём (рис. 7.15).

Максимальное значение плотности загрузки

Рис. 7.15.  Максимальное значение плотности загрузки

Таким образом, справедливо утверждение

Лемма. Минимальное число n процессоров одинаковой специализации и производительности (т.е. в однородной ВС), способных выполнить данный алгоритм за время T

Tкр, не превышает R = max {r1 , ... , rl }, где ri , i = 1 , ... , l, — число работ, входящих в i-е ПМВНР, которое составлено по взвешенному графу G, соответствующему этому алгоритму.

Определение 8. Функцию

 \begin{align*} \text{Ф} (\tau_1 \dts \tau_m, \theta_1, \theta_2)= \int_{\theta_1}^{\theta_2} F(\tau_1 \dts \tau_m,t)dt \end{align*}

назовём загрузкой отрезка [?1, ?2]

[0,T] для заданного допустимого расписания ?1, ... ,?m.

Функция Ф определяет объём работ (суммарное время их выполнения) на фиксированном отрезке их выполнения при заданном допустимом расписании.

Так, для отрезка времени [0, 4]

[0, 10] на рис. 7.13а Ф = 10; для отрезка времени [1, 3] на ррис. 7.13б Ф= 4; для отрезка времени [2, 5] на рис. 7.15




Содержание  Назад  Вперед