Оценка множества работ при решении задач распараллеливания
5
(
θ
2
− (
τ
2
i
(
T
) −
t
i
)) (при условии, что
τ
2
i
(
T
) −
t
i
<
θ
2
). Но, кроме указан-
ных двух случаев, возможны еще два:
1) τ
1
i
≥
θ
2
и одновременно
τ
2
i
(
T
) −
t
i
≤
θ
1
, тогда объем работ по ис-
полнению
i
-го оператора, который обязательно необходимо
выполнить на отрезке [
θ
1
,
θ
2
], равен (
θ
2
–
θ
1
);
2) θ
1
≤
τ
1
i
−
t
i
≤
τ
2
i
(
T
) ≤
θ
2
, тогда объем работ по исполнению
i
-го
оператора, который обязательно необходимо выполнить на от-
резке [
θ
1
,
θ
2
], равен
t
i
.
Последний случай, при котором объем работ по исполнению
i
-го
оператора равен
t
i
, в [1] не учтен при вычислении функции
ϕ
(
T
)
(
θ
1
,
θ
2
), но он может иметь место, а значит, должен быть учтен. Тогда
условный минимальный объем работ по исполнению
i
-го оператора
на отрезке [
θ
1
,
θ
2
] может быть вычислен по формуле
( )
(
)
(
)
( )
(
)
{
}
1 2
1 1
2 2
2 1
φ θ , θ min ξ τ θ , ξ θ τ
, θ θ ,
T
i
i
i
i
i
t t
t
=
−
− +
−
, (3)
где
ξ
(
x
) =
x
при
x
≥ 0;
ξ
(
x
) = 0 при
x
< 0.
Таким образом, общий объем работ по исполнению всего алго-
ритма, который необходимо выполнить на отрезке [
θ
1
,
θ
2
], т.е. значе-
ние функции минимальной загрузки отрезка [
θ
1
,
θ
2
] —
ϕ
(
T
)
(
θ
1
,
θ
2
),
можно вычислить по формуле
( )
(
)
(
)
( )
(
)
{
}
(
)
1 2
1 1
2 2
2 1
1
φ θ , θ
min ξ τ θ , ξ θ τ
, θ θ ,
.
m
T
i
i
i
i
i
T t
t
=
=
−
−
+
−
∑
(4)
ЛИТЕРАТУРА
[1] Барский А.Б.
Параллельные процессы в вычислительных системах. Плани-
рование и организация
. Москва, Радио и связь, 1990, 256 с.
[2] Миренков Н.Н.
Параллельное программирование для многомодульных вы-
числительных систем
. Москва, Радио и связь, 1989, 320 с.
Статья поступила в редакцию 10.06.2013
Ссылку на эту статью просим оформлять следующим образом:
Толпинская Н.Б. Оценка множества работ при решении задач распа-
раллеливания.
Инженерный журнал: наука и инновации
, 2013, вып. 6. URL:
Толпинская Наталья Борисовна
родилась в 1953 г. Канд. техн. наук, доцент
кафедры «Программное обеспечение ЭВМ и информационные технологии» МГТУ
им. Н.Э. Баумана. Автор 19 печатных работ. Область научных интересов: парал-
лельное программирование (планирование и алгоритмы), функциональное про-
граммирование и логическое программирование. е-mail:
