Параллельное программирование



              

Диспетчер последовательного назначения для неоднородной ВС - часть 2


Этим имитируется окончание выполнения работ на процессорах к моменту времени t?.
  • Для всех процессоров, для которых текущее время занятости меньше значения t? (Ti < t?), записываем простой в течение времени t? - Ti (символом простоя
    \ubox{t_{\mu} - T_i}
    ). Для этих процессоров полагаем Ti = t?.
  • Исключаем из S? строки и столбцы, соответствующие всем работам из B, после чего матрицу S? (S*?) уплотним. Полагаем ? := ? + 1. Таким образом сформируется матрица S? (а также S*?) на новом шаге распределения.
  • Находим множество R — входов матрицы следования S?, соответствующих не назначенным ранее работам. Если R
    , переходим к выполнению 6, в противном случае выполняем пункт 2.
  • Пусть для определенности R = {
    1 ...
    r}, работе
    p соответствует вес {tp1 ... tpN}, p = 1 ... r. Формируем суммы Tl + tpl , l = 1 ... N, p = 1 ... r. Для каждого значения p (т.е. для каждой работы из R) находим минимальную (по l) из таких сумм, т.е. для каждой работы находим один или несколько процессоров, на которых время окончания выполнения этой работы минимально при текущих значениях занятости процессоров. Найденные суммы сведем в невозрастающую последовательность R*, состоящую из r чисел. При этом сохраним информацию о соответствии процессорам.
  • Ставим в соответствие каждой p-й работе, представленной в последовательности R*, значение ?p, равное числу процессоров, при выполнении на которых достигается найденное минимальное время окончания выполнения этой работы.
  • Производим последовательное назначение работ на процессоры следующим образом. Назначаем не более N работ слева направо в соответствии с вхождением времени окончания их выполнения в последовательность R*. Каждую p-ю работу назначаем на все те процессоры, (их число равно ?p), на которых достигается входящее в R* время окончания выполнения. В результате те работы, для которых ? > 1, окажутся назначенными более чем на один процессор, а на один процессор на данном шаге могут оказаться назначенными более одной работы. Чтобы определить окончательно, на какой процессор должна быть назначена p-я работа, воспользуемся следующей процедурой.


    Содержание  Назад  Вперед