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

UptoLike

ВУЗ: 

СГАУ | Самара

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

Рубрика: 

105
Задача выбора допустимой комбинации связей на шаге 6 алгоритма по-
строения графа
'
G
является отдельной важной проблемой, которая в основном
определяет затраты времени на осуществление направленного перебора. Рас-
смотрим ее более детально.
8.4 Выбор допустимой комбинации связей
Отдельного рассмотрения требует выполняемая в ходе построения графа
'
G
процедура выбора допустимой комбинации nr
связей внутри множества
ВНО, содержащего
r операторов. Для этого из соответствующей множеству
ВНО
r,...,,jA 1
r
r матрицы
L , все элементы которой равны
нулю, формируется матрица следования, соответствующая введенным допол-
нительным связям. При этом следуют следующим правилам:
1. Диагональные элементы матрицы
L равны нулю (отсутствие контуров).
2. В каждой строке и каждом столбце содержится не более одной единицы.
3. Если
кр
TT
, первые l строк закрепляются за операторами, принадлежащими
критическому пути, и полагаются нулевыми.
Вводимые связи упорядочиваются так, что единица, соответствующая p-й
связи nr,...,p
1 , оказывается записанной в строке, выше которой есть толь-
ко
1
p
ненулевых строк матрицы
L . Таким образом,
p
-я связь при проверке
всех комбинаций пробегает строки от
p
до
pnpnrr
, а при
кр
TT
от
p
l
до
p
n
.
Алгоритм введения дополнительных связей можно описать в виде сле-
дующей последовательности шагов.
1. Каждому оператору
Aj ставятся в соответствие значения
1
1
и
nr,...,,T
j
1
2
1
.
2. Вводится некоторая комбинация связей, удовлетворяющая приведенным
выше условиям (при этом единичные элементы располагаются в матрице

Страницы