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

UptoLike

ВУЗ: 

СГАУ | Самара

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

Рубрика: 

91
jj
k,...,
j
tmax
j
1
1
1
. (7.1)
Если же среди элементов множества
j
j
k,, 1
1
есть хотя бы один нулевой
(т.е. данное значение раннего срока окончания выполнения оператора еще не
определено), переходят к следующей необработанной строке.
Например, по матрице S, представленной на рис. 7.1, можно определить:
2
111
t ; 3
212
t ;
3
31113
t ; 4
41114
t ;
7
5121115
tmax ; 8
61416
t ;
6
7141217
t,max ;
9
81716151318
t,,,max .
Для учета фактора различной производительности процессоров может
быть построена информационная граф-схема алгоритма с векторными весами
вершин. Анализ таких граф-схем существенно сложнее, вследствие значитель-
ного увеличения числа возможных вариантов распределения работ. Для опре-
деления наилучшего плана распределения работ, строго говоря, необходимо
осуществлять перебор всех возможных вариантов, в каждом из которых каж-
дый оператор закреплен за определенным процессором. Подробное изложение
методов анализа различных граф-схем можно найти в монографии [1].
7.3 Определение поздних сроков выполнения операторов
Поздние сроки окончания выполнения операторов при заданном значении
T можно найти по следующему алгоритму.
На первом шаге полагаем
0
221
T...T
m
. Находим первый справа
столбец из необработанных еще столбцов матрицы S. Предположим j – номер
необработанного столбца. Если j -й столбец не содержит единичных элемен-
тов, полагаем
TT
j
2
.

Страницы