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

UptoLike

ВУЗ: 

СГАУ | Самара

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

Рубрика: 

109
му увеличению длины критического пути. Пробуем еще одну комбинацию:
213. При введении дуг, соответствующих этим связям, длина критического
пути не превышает допустимого значения. С учетом этих связей находим ран-
ние и поздние сроки окончания выполнения операторов. В данном случае
6523
1
17
1
15
1
16
1
13
1
14
1
12
1
11
,,, . Соответствующая диаграмма реа-
лизации алгоритма приведена на рис. 8.1, в.
Найдем 3
2
t , так как
2336562523
,,,,,,,F . Это значение функции
плотности загрузки определяется выполнением операторов 3, 5, 6. Составляем
матрицу L
2
(рис. 8.1, г) и стараемся ввести в ней единственный единичный
элемент. Перебор всех возможных способов введения такого элемента приво-
дит к недопустимой длине критического пути.
Возвращаемся на шаг назад к анализу матрицы L
1
и пробуем ввести другую
допустимую комбинацию связей. Такой комбинацией является 21, 43. На
рис. 8.1, д представлена диаграмма выполнения операторов при уточненных
ранних сроках окончания их выполнения
23
1
14
1
12
1
11
, ,
564
1
16
1
17
1
15
1
13
,, .
Вновь находим значение 3
2
t , при котором
2336562423
,,,,,,,F .
Это значение так же как и ранее определяется выполнением операторов 3, 5, 6.
Вновь формируем матрицу L
2
и находим первую из допустимых связей – связь
35. На рис. 8.1, ж представлена диаграмма выполнения алгоритма, удовле-
творяющая условиям задачи.
8.6 Определение плана реализации алгоритма
за минимальное время
В основе алгоритма решения задачи 2 лежит та же идея, что и при решении
задачи 1. Для того чтобы T было минимальным временем выполнения алгорит-
ма, представленного информационным графом
, ,
G X P
Г
на n процессорах,
достаточно построить граф
''
Г,P,XG , для которого длина критического пу-

Страницы