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

UptoLike

ВУЗ: 

СГАУ | Самара

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

Рубрика: 

90
Важнейшей характеристикой информационного графа является длина кри-
тического пути. Длиной пути в информационно-логическом графе со скаляр-
ными весами вершин называют сумму весов вершин, составляющих этот путь.
Путь максимальной длины
кр
T называют критическим. Если пути в графе име-
ют одинаковую длину, любой из них может считаться критическим.
Если отсчет времени ведется с момента начала выполнения операторов, то
момент ( m,i,
i
1
1
) окончания выполнения любого (i-го) оператора не мо-
жет быть меньше максимальной из длин всех путей, заканчивающихся верши-
ной, соответствующей этому оператору. Величина
i1
является ранним сроком
выполнения данного оператора. Если выполнение алгоритма ограничено вре-
менем T, то для каждого оператора можно найти также и поздний срок оконча-
ния его выполнения
T
i2
. Он определяется как разность между величиной T
и максимальной из длин путей, в первую из вершин которых входит дуга, исхо-
дящая из вершины, соответствующей данному оператору. При
кр
TT
ранние и
поздние сроки окончания выполнения операторов, находящихся на критиче-
ском пути, совпадают.
7.2 Определение ранних сроков выполнения операторов
Ранние и поздние сроки окончания выполнения операторов удобно опре-
делять с использованием матрицы следования. Общая процедура анализа графа
со скалярными весами вершин
j
t строится в виде следующей последовательно-
сти шагов.
Положив 0
11211
m
... , последовательно обрабатывают строки
матрицы следования S. Если очередная (j-я) строка не содержит единичных
элементов, полагают
jj
t
1
. Если j-я строка содержит единичные элементы,
из множества {
m
,...,
111
} выбирают подмножество элементов
j
j
k,, 1
1
,
соответствующих номерам единичных элементов j-й строки. В случае, когда
все они отличны от нуля, полагают

Страницы