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

UptoLike

ВУЗ: 

СГАУ | Самара

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

Рубрика: 

96
С использованием (7.7) можно построить оценку минимального числа n
процессоров, необходимого для выполнения заданного алгоритма за время T.
Для этого перебираются все возможные отрезки
T,, 0
21
, например, в
следующем порядке:
10, ;
20, ;
21, ;
30, ;
31, ;
32, ;
. . . . . . . . . . . . . . . . . . . . .
T,0 ;
T,1 ; . . . ,
T,T 1
.
Всего таких отрезков будет
121
/TT . Для каждого отрезка определя-
ется значение
12
21
,,T
n
'
. (7.8)
После перебора всех отрезков среди полученных по соотношению (7.8) значе-
ний находим максимальное –
'
, которое равно максимальному из значений,
удовлетворяющих условию (7.7).
7.6 Построение оценок минимального времени выполнения алгоритма
на заданном числе процессоров
Методика построения оценки для минимального времени T выполнения
заданного алгоритма на n процессорах опирается на следующее утверждение.
Пусть алгоритм, описываемый информационным графом со скалярными весами
вершин, реализуется на n процессорах, а T
1
– некоторая оценка снизу времени
выполнения алгоритма. Пусть также на отрезке времени
T,, 0
21
выпол-
няется соотношение
0
12211
dn,,T .
Тогда наименьшее время T реализации алгоритма удовлетворяет соотношению
n/dTT
1
.

Страницы