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

              

Формальное описание алгоритма диспетчера


Пусть задана (рис. 10.11) расширенная матрица следования S*, отражающая информационные связи внутри множества m работ j = 1...m. Веса tj — времена выполнения каждой j-й работы на каждом из n процессоров однородной ВС с общей ОП.


Рис. 10.11.  Граф алгоритма и расширенная матрица следования

Необходимо составить расписание параллельного выполнения работ, при котором время выполнения всей совокупности работ минимально.

Вспомогательные построения

Пусть в результате распределения составляется таблица-расписание?, содержащая n строк — расписаний одному процессору. В строке — последовательность заданий двух видов: выполнить работу (задачу, оператор и т.д.)

, простоять t единиц времени (
). Момент Ti, i = 1 ... n, окончания (отсчет — от нуля) выполнения последней работы или проcтоя, назначенных к данному шагу распределения i-му процессору, назовем текущим временем занятости процессора.

Пусть в процессе распределения формируется таблица (множество) A номеров задач, назначенных к данному шагу распределения последними для выполнения на каждом процессоре. Эти номера заносятся в позиции, закрепленные за каждым процессором. Если последним был записан простой, в соответствующей позиции значится 0.

В множество B будем объединять процессоры (один или более), имеющие на данном шаге распределения минимальное время занятости.

В множество ? выделим те работы из A, которые выполняются на процессорах из B.

Множество R — множество работ, соответствующих входам (нулевым строкам) текущего значения изменяемой в процессе распределения матрицы следования S.

Алгоритм.

  1. Полагаем первоначально Ti = 0, i = 1 ... n, A = {0, ...,0}, B = {1 ... n}, =
    , R =
    , ? = 1, S?* = S*; переходим к выполнению шага 6.
  2. Находим Tmu = min{Ti} и множество B номеров процессоров с найденным временем занятости.
  3. Находим множество ?
    A номеров задач, назначенных последними на процессоры из B. После построения ? все позиции в A, соответствующие процессорам из B, полагаем равными нулю. Этим моделируется окончание выполнения задач на данных процессорах к моменту T?.
  4. Если ? =
    , переходим к выполнению шага 7 при R
    и шага 10 при R =
    ; при ?
    выполняем следующий шаг.
  5. Исключаем из S?* строки и столбцы, соответствующие задачам, составляющим множество ?.

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