Лекции по параллельным вычислениям. Гергель В.П - 97 стр.

UptoLike

ВУЗ: 

СГАУ | Самара

Составители: 

Рубрика: 

97
Алгоритм построения оценки для минимального времени строится сле-
дующим образом. Первоначально полагают
1
1
1
max ,
m
i
кр
i
T t T
n
,
где
x
означает операцию взятия ближайшего целого числа не меньшего x.
Затем организуется перебор всех отрезков, например, в той же последова-
тельности, как описано в предыдущем разделе. Заметим, что при таком порядке
перебора отрезков значение T
1
можно увеличивать в процессе выполнения ал-
горитма. Для каждого отрезка времени
21
, определяется значение
1221
n,,Td .
Если
d
, новое значение оценки минимального времени определяется по
соотношению
2 1
d
T T
n
.
Для найденного нового значения T
2
определяются поздние сроки выпол-
нения операторов:
2 2 2 2
, 1,
j j
d
T T j m
n
.
После перебора всех отрезков
21
, найденное окончательное значение и бу-
дет нижней оценкой минимального времени выполнения данного алгоритма на
n процессорах.
7.7 Определение временных характеристик
с учетом обмена информацией
Рассмотрим теперь случай, когда нельзя пренебречь временем обмена ин-
формацией при распределении множества информационно взаимосвязанных
задач. Обозначим
R – объем информации, передаваемой в направлении ду-
ги, соединяющей две вершины
и
. Граф, в котором каждая, соединяющая
вершины
и
дуга, снабжена весом
R , будем обозначать
Г,R,P,XG
.

Страницы