Н.Б. Толпинская
4
совпадает с моментом окончания работы
i
-го оператора
τ
i
и одно-
временно начинает работать следующий за ним оператор, т. е.
(
)
τ
j
i
t t i j
− = ≠
, то по формуле (1) в сумме по этим двум операторам
будет получено значение 2. Это означает, что в момент
t
должны од-
новременно, т. е. параллельно, выполняться два оператора — процес-
са, а это не так. Поэтому для функции
f
(
τ
i
,
t
) справедлива формула:
(
)
(
)
τ ,
1 при τ
τ ,
τ ,
0 — в противном случае.
i
i
i
i
i
f
t
t t
f
t
=
− ≤ <
=
(2)
По такой формуле в момент
t
будет учитываться только одна рабо-
та, а именно, та, которая завершает свое выполнение в момент
t
. Для
того же оператора, который еще не начал свое выполнение и не за-
грузил работами по своему исполнению вычислительную систему,
функция
f
(
τ
i
,
t
) будет возвращать 0, а значит, он не будет учиты-
ваться и при вычислении
F
(
τ
1
, …,
τ
m
,
t
) — функции плотности за-
грузки.
Функция минимальной загрузки отрезка времени [
θ
1
,
θ
2
] —
ϕ
(
T
)
(
θ
1
,
θ
2
) является основным средством оценки результатов плани-
рования при решении задач распараллеливания. Она позволяет оце-
нить минимальный объем работ по исполнению всего алгоритма, ко-
торый при всех возможных способах закрепления операторов на оси
времени обязательно необходимо выполнить на отрезке времени [
θ
1
,
θ
2
] для того, чтобы обеспечить выполнение всего алгоритма за время,
не превышающее заданное время
T
. При ее расчете для данного от-
резка времени [
θ
1
,
θ
2
] по всем операторам проводится анализ
наилучшего их расположения относительно данного отрезка.
Наилучшим является такое положение
i
-го оператора относительно
отрезка времени [
θ
1
,
θ
2
], при котором он наименьшим образом загру-
жает отрезок времени [
θ
1
,
θ
2
] работами по своему исполнению. Допу-
стим не единственный вариант закрепления
i
-го оператора на оси
времени. Однако наилучшее его расположение может быть выбрано
из ограниченного числа вариантов, которые определяются двумя
условиями: время окончания выполнения оператора равно раннему
сроку окончания его выполнения
τ
i
=
τ
1
i
, или время окончания вы-
полнения оператора равно позднему сроку окончания его выполне-
ния
τ
i
=
τ
2
i
(
T
). В первом случае объем работ по исполнению этого
оператора, который обязательно должен быть выполнен на отрезке
[
θ
1
,
θ
2
], равен (
τ
1
i
−
θ
1
) (при условии, что
τ
1
i
−
t
i
<
θ
1
). Во втором слу-
чае объем работ по исполнению этого
i
-го оператора, который обяза-
тельно необходимо выполнить на отрезке [
θ
1
,
θ
2
], равен
