ВУЗ:
Составители:
95
7.5 Построение оценок минимального числа процессоров,
необходимых для выполнения алгоритма за заданное время
Для построения приближенных оценок минимального времени выполнения
алгоритма при заданном числе процессоров n, либо числа процессоров для вы-
полнения алгоритма за время T может использоваться так называемая функция
загрузки вычислительной системы на отрезке
T,, 0
21
для заданного на-
бора
m
,...,
1
:
2
1
1211
dtt,,...,F,,,...,
mm
. (7.5)
Эта функция определяет суммарный объем работ (необходимое время) на ука-
занном фиксированном отрезке. Например, для отрезка времени
40, по рис.
7.2, а) можно определить:
84098764332
,,,,,,,,, .
На множестве допустимых, принадлежащих многоугольнику (7.3) планов
алгоритма, характеризующихся различными наборами значений
m
,...,
1
,
можно определить минимальную загрузку отрезка
T,, 0
21
:
21121
1
,,,...,min,,T
m
,...,
m
. (7.6)
Для того чтобы T было наименьшим временем выполнения алгоритма на n
процессорах, либо n процессоров было достаточно для выполнения алгоритма
за время T, необходимо, чтобы для данного отрезка времени выполнялось нера-
венство
1221
n,,T . (7.7)
Необходимость этой оценки вытекает из того, что если для некоторого набора
сроков окончания выполнения операторов
m
,...,
1
существует минимальное
значение
m
,...,maxT
1
, для обеспечения которого достаточно n процессо-
ров, то в силу (7.5), (7.6) для любого отрезка времени
12121121
2
1
ndtt,,...,F,,,...,,,T
mm
.
Страницы
- « первая
- ‹ предыдущая
- …
- 93
- 94
- 95
- 96
- 97
- …
- следующая ›
- последняя »
