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

UptoLike

ВУЗ: 

СГАУ | Самара

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

Рубрика: 

107
ответственно. Эти элементы находятся под главной диагональю. Если
0
p
, то комбинация единичных элементов – последняя из возможных, т.е.
необходимой комбинации связей не существует.
Если
0
p
, полагают равными нулю эти элементы и смещают единицу,
соответствующую
p
-й связи по строке, в которой она расположена, на од-
ну позицию вправо или в крайнее левое положение на следующую строку,
которая в этом случае обязана быть нулевой. Это смещение производится
так, чтобы по отношению к связям
1
1
p
,
...
,
выполнялось условие 2, т.е. в
результате проверки условия 2 это смещение может быть произведено не-
однократно.
9. Если nrp
, вновь последовательно вводят единичные элементы мат-
рицы
L , соответствующие связям nr,...,p
1 , так, что каждый из вво-
димых единичных элементов должен занимать крайнее левое положение в
очередной строке, следующей за той, в которой введена
p
-я связь. В то же
время вновь вводимая связь должна удовлетворять в совокупности с уже
введенными связями условию 2.
10. Если новую комбинацию единичных элементов матрицы, удовлетворяю-
щую условию 2, удалось ввести, устанавливаем, не содержит ли матрица
L контуров. Если контуры есть, вновь выполняем шаг 8.
11. Если новая комбинация единичных элементов матрицы
L удовлетворяет
условиям 1 и 2, переходим к анализу комбинации связей на шаге 3.
8.5 Пример определения минимального числа процессоров
Найдем минимальное число процессоров, необходимое для выполнения
алгоритма, представленного графом, показанным на рис. 8.1, за время T=7. В
соответствии с алгоритмом, описанным в разделе 7.4, исследуем 28 значений
функции минимальной загрузки отрезков
70
21
,,
и найдем нижнюю
оценку минимального числа процессоров – n=2. При этом

Страницы