Оценка множества работ при решении задач распараллеливания
3
входящие в непустое пересечение нескольких множеств ВНО? По-
этому выделение операторов, которые могут выполняться параллель-
но, и дальнейшее планирование их реализации необходимо выпол-
нять с учетом закрепления операторов на оси времени.
Этот процесс можно осуществить, определив момент окончания
выполнения
i
-го оператора —
τ
i
. С учетом информационной зависи-
мости между операторами и ограничения на время выполнения всего
алгоритма
T
могут быть определены ранний
τ
1
i
и поздний
τ
2
i
(
T
) сроки
окончания исполнения оператора. Ранний срок окончания выполне-
ния оператора (если началом отсчета является момент начала выпол-
нения операторов) не может быть меньше максимальной из длин всех
путей, заканчивающихся вершиной, соответствующей данному опе-
ратору. Поздний срок не может превышать разности между значени-
ем
Т
и максимальной из длин путей, в первую из вершин которых
входит дуга, выходящая из вершины, соответствующей данному опе-
ратору. При параллельной реализации алгоритма исходной задачи за
ограниченное время
Т
любой оператор должен быть закреплен на оси
времени так, чтобы
τ
1
i
≤
τ
i
≤
τ
2
i
(
T
). Если мощность некоторого мно-
жества операторов ВНО, параллельное выполнение операторов кото-
рого предполагается реализовать, не превышает ресурса вычисли-
тельной системы — множества решающих устройств, то можно по-
ложить
τ
i
=
τ
1
i
для каждого оператора этого множества ВНО. Однако,
если мощность множества операторов ВНО больше множества ре-
шающих устройств, то необходимо построить эффективный план па-
раллельной реализации операторов соответствующего множества
ВНО.
В целях планирования вычислительного процесса в рассмотрение
вводятся [1] функция плотности загрузки
F
(
τ
1
, …,
τ
m
,
t
), функция
Φ
(
τ
1
, …,
τ
m
,
θ
1
,
θ
2
) загрузки отрезка времени [
θ
1
,
θ
2
], принадлежащего
отрезку [0, …,
T
], и функция минимальной загрузки отрезка [
θ
1
,
θ
2
] —
ϕ
(
T
)
(
θ
1
,
θ
2
). Однако следует заметить, что определения функций плот-
ности загрузки и функции минимальной загрузки следует уточнить.
Функция плотности загрузки вычисляется как сумма значений
функции
f
(
τ
i
,
t
) для всех операторов
i
= 1, …,
m
:
(
)
(
)
1 1
τ ,..., τ ,
τ ,
m
m
i
i
F
t
f
t
=
=
∑
,
(1)
где функция
f
(
τ
i
,
t
) отражает факт выполнения
i
-го оператора в мо-
мент времени
t
. Функция
f
(
τ
i
,
t
) должна возвращать значение 1, если
i
-й оператор работает в момент
t
, и 0, если он не работает в этот мо-
мент. Как указано в [1],
f
(
τ
i
,
t
) = 1 при
τ
i
–
t
i
≤
t
≤
τ
i
. Но если момент
t
