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

UptoLike

ВУЗ: 

СГАУ | Самара

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

Рубрика: 

111
TT нецелесообразно, т.е. найденное значение
T – решение задачи 2. Если
это не так, не меняя значения , вводим очередную, еще не испытанную комби-
нацию nr
связей так, чтобы длина критического пути в полученном графе
G
была меньше
T . Если такая комбинация связей существует, значение
увеличивают на единицу, уточняют для него новые значения ранних сроков
окончания выполнения операторов и ищут наименьшее значение
j
j
tt
1
,
удовлетворяющее неравенству (8.2).
Если значение
t , обеспечивающее выполнение неравенства (8.2), найде-
но, выделяют множество операторов
r,...,,A
j
1 , для которых
jjj
tt
11
. Множество
A является подмножеством некоторого полного
множества ВНО. Далее вводят еще не испытанную комбинацию nr
связей
так, чтобы длина критического пути в полученном при этом графе
G
была
меньше
T . Если такая комбинация связей существует, значение увеличивают
на единицу, уточняют для него новые значения ранних сроков окончания вы-
полнения операторов и вновь ищут наименьшее значение
t , удовлетворяющее
неравенству (8.2).
Если такой комбинации связей не существует или все они уже перебраны и
при этом
1
, уменьшают на единицу, вводят очередную не испытанную
комбинацию и повторяют указанные выше действия. Если уже испытаны все
комбинации связей при
1
, то последнее значение
T определяет искомое
TT .
8.7 Пример задачи определения минимального времени
реализации алгоритма
Для n=2 решим задачу для графа, представленного на рис. 8.2, а. На рис.
8.2, б представлена диаграмма выполнения алгоритма при ранних сроках окон-
чания выполнения операторов.

Страницы