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

UptoLike

ВУЗ: 

СГАУ | Самара

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

Рубрика: 

103
описанной схемой введено
n
r
связей и n – наименьшее из целых чисел, для
которых это возможно. Тогда в сформированном графе
'
G
каждое полное мно-
жество ВНО содержит не более n операторов. Но это, в соответствии с выво-
дами, содержащимися в разделе 7.3, как раз и означает, что минимальное число
процессоров, способных выполнить данный алгоритм за время
T
, не может
быть больше n. С другой стороны, допущение о том, что число процессоров
меньше n, противоречит результату работы алгоритма, в соответствии с кото-
рым n – наименьшее из целых чисел, для которого возможно введение
n
r
связей.
После нахождения графа-решения
'
G
распределение множества операторов
между n процессорами не представляет трудностей, т.к. известны найденные по
этому графу ранние сроки выполнения операторов. В силу алгоритма при этих
сроках одновременно могут выполняться не более n операторов. Поэтому ос-
тается только закрепить эти операторы за процессорами. Для этого необходимо
просматривать значения ранних сроков начала выполнения операторов в по-
рядке их неубывания и закреплять за процессорами, которые в эти моменты
свободны. Это может быть легко реализовано даже в процессе решения вычис-
лительной задачи.
8.3 Определения минимально необходимого числа процессоров
методом направленного перебора
Описанная выше задача 1 – определения минимально необходимого числа
процессоров, может быть решена методом направленного перебора (ветвей и
границ). В данном случае ветвление определяется различными способами вве-
дения дополнительных связей в каждое полное множество ВНО, число опера-
торов в котором превышает n, или его подмножество. Границы определяются
допустимыми изменениями длины критического пути в графе после введения
дополнительных связей.

Страницы