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

UptoLike

ВУЗ: 

СГАУ | Самара

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

Рубрика: 

110
ти минимальна среди всех графов, полученных из заданного путем объедине-
ния вершин, соответствующих операторам каждого полного множества ВНО,
содержащего
n
r
операторов,
n
r
ориентированными дугами в n путей, не
содержащих общих вершин.
Действительно, пусть T – минимальное время, для которого удалось по-
строить такой граф
'
G
и
'
кр
TT . Каждое полное множество ВНО в графе
'
G
со-
держит не более n операторов. Следовательно, в соответствии с выводами раз-
дела 7.3 алгоритм, представленный графом
'
G
, может быть выполнен за время
TT
'
кр
. Далее схема решения задачи 2 рассматривается детально.
В соответствии с методикой, изложенной в разделе 7.5, находят оценку
0
TT
минимального времени выполнения заданного алгоритма на n процессо-
рах. Полученная оценка вполне может оказаться искомым минимальным вре-
менем выполнения алгоритма. Чтобы проверить это, целесообразно с помощью
алгоритма, описанного в разделе 8.2, установить, способны ли n процессоров
выполнить данный алгоритм за время
0
T . Если нет, продолжаем решение зада-
чи 2.
Для этого полагаем
T,,m,j,,
jj
111
11
, где – заведомо
большое число, и находим наименьшее значение
j
j
tt
1
,
m,...,j 1
та-
кое, что
nrt,,...,F
m
111
. (8.2)
Если такого значения
t нет на первой же итерации (при
1
), то
кр
T –
решение задачи 2. Если такого значения нет и при
1
, то увеличивают значе-
ние на единицу и полагают
m
,...,maxT
111
, т.е. длине критического пу-
ти в графе
'
G
, полученном из заданного путем объединения вершин каждого
полного множества ВНО, содержащего
n
r
операторов,
n
r
ориентирован-
ными дугами в n путей, не содержащих общих вершин. В случае, когда оказы-
вается, что 1
0
TT , то поскольку
0
T – не решение задачи, искать значение

Страницы