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

UptoLike

ВУЗ: 

СГАУ | Самара

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

Рубрика: 

101
8.2 Общая схема решения задачи определения минимально
необходимого числа процессоров
Решение задачи 1 заключается в определении минимального числа n, для
которого можно построить преобразованный граф
' '
, ,
G X P
Г
, объединив
вершины, соответствующие операторам каждого полного множества ВНО, со-
держащего
r n
операторов
ориентированными дугами в n путей, не со-
держащих общих вершин. При этом длина критического пути в графе
'
G
не
должна превышать значение T . Суть алгоритма нахождения графа
'
G
состоит в
том, что выбрав начальное расписание, в котором все операторы занимают на
оси времени крайнее левое положение, продвигаются шаг за шагом и находят
точки на оси времени, в которых функция плотности загрузки превышает пер-
воначально заданное значение n. Вводя дополнительные связи, допускаемые
ограничением на T, пытаются уменьшить (сгладить) функции плотности. Если
это не удается, вводят другую комбинацию связей. При переборе всех комби-
наций связей число процессоров увеличивают на единицу и начинают процесс
сначала. Рассмотрим алгоритм построения графа
'
G
более подробно.
Вначале для заданного информационного графа
, ,
G X P
Г
со скалярными
весами вершин и данного времени T находят значения ранних
i1
и поздних
m,i,T
i
1
2
сроков окончания выполнения операторов. При этом для
корректности задачи должно выполняться соотношение
TTmax
крi
i
1
.
Значения
i1
фиксируют исходное расписание выполнения операторов за
время, не превышающее T.
Для сформированного расписания в соответствии с алгоритмом, описан-
ным в разделе 7.4, находят оценку n минимального числа процессоров, которое
необходимо для выполнения заданного алгоритма, соответствующего графу
, ,
G X P
Г
за время, не превышающее T.

Страницы