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

              

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


Для нетреугольной матрицы S на рис. 7.10 при T = 10 находим ?26(10) = ?25(10) = 10. Обработка четвёртого столбца откладывается, т.к. не найдено значение ?22(10). По этой же причине не обрабатывается третий столбец. После обработки второго столбца находим ?22(10) = ?26(10) - t6 = 9.

Обработка первого столбца невозможна, т.к. ещё не найдено значение ?23(10). Продолжаем циклический обзор столбцов. После обработки четвёертого столбца получаем ?24(10) = ?22(10) - t2 = 6. Обработка третьего столбца даёт ?23(10) = min {?22(10) - t2, ?25(10) - t5} = 6. После обработки первого столбца находим ?21(10) = ?23(10) - t3 = 4.

Диаграммы выполнения работ при поздних сроках окончания, по графам на рис. 7.1 и 7.10, при T = 10 представлены на рис. 7.12 — (а) и (б), соответственно. (Стрелки, соответствующие дугам в графах, опущены в связи с их избыточностью.)

Диаграммы выполнения работ при поздних сроках окончания: а — для графа на рис. 7.1,б — для графа на рис. 7.10

Рис. 7.12.  Диаграммы выполнения работ при поздних сроках окончания: а — для графа на рис. 7.1,б — для графа на рис. 7.10

Пусть ?j — произвольное значение момента окончания выполнения j-й работы, j =1 , ... , m,

?1j

?j
?2j(T) (?j
[?1j, ?2j(T)]).

Меняя значения {?j}, j = 1 , ... ,m, но соблюдая при этом порядок следования работ, мы получим множество допустимых расписаний выполнения работ.

Нашей конечной целью является выбор таких расписаний, которые позволяют решить задачи 1 и 2.

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

\begin{align*} F(\tau_1,\tau_2 \dts \tau_m,t) = \sum_{j=1}^m f(\tau_j,t), \end{align*} где \begin{align*} f(\tau_j,t)= \left\{ \begin{array}{rcl} 1 &\text{ при } t \in \lfloor \tau_j - t_j,\tau_j\rfloor \\ 0 &\text{ в противном случае }, \end{array} \right. \end{align*}

назовём плотностью загрузки, найденной для значений ?1 , ... , ?m.

Для заданных ?1 , ... , ?m значение функции F в каждый момент времени t совпадает с числом одновременно (параллельно) выполняющихся в этот момент работ.

Например, по диаграмме на 7.11, т.е. для ?1 = ?11, ?2 = ?12, ... , ?8 = ?18, функция F(2, 3, 3, 4, 7, 8, 6, 9, t) имеет вид, представленный на рис. 7.13а. Для допустимого расписания, определяемого набором значений ?1 = 2, ?2 = 4, ?3 = 3, ?4 = 4, ?5 = 8, ?6 = 9, ?7 = 7, ?8 = 10, функция F(2, 4, 3, 4, 8, 9, 7, 10, t) имеет вид, представленный на рис. 7.13б.




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