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



              

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


Полагаем ? := ? + 1.
  • Находим множество R входов матрицы следования S?, соответствующих не назначенным ранее задачам. Если R =
    , переходим к выполнению шага 10.
  • Располагаем номера задач, составляющих R, в порядке невозрастания времени их выполнения.
  • Производим поочередное назначение задач, составляющих упорядоченное множество R, на процессоры, составляющие множество B. Назначенные задачи исключаем из R, а процессоры, на которые произведено назначение, — из B. Номер каждой назначенной задачи заносим в позицию A, соответствующую данному процессору. Время занятости этого процессора увеличиваем на время выполнения назначенной задачи. Последовательное назначение прекращается в одном из трех случаев: a) R

    , B =

    ; б) R =
    , B =
    ; в) R =
    , B
    .

    Примечание. Шаги 7 и 8 реализуют решающее правило, лежащее в основе данного (и каждого!) эвристического (практичного, эффективного, но не основанного на точном решении сложной задачи) алгоритма распараллеливания. Повторим его:

    Из тех задач, выполнение которых может быть начато на данном шаге распределения, в первую очередь назначать ту, которая обладает максимальным временем выполнения.

    Возможны и другие решающие правила, например, основанные на допустимом резерве времени до обязательного момента окончания решения и др. Применяемое здесь решающее правило обеспечивает высокое быстродействие диспетчера и достаточно редкое (менее 10 %) отклонение результатов распределения от тех же результатов, получаемых методом точного решения задачи распараллеливания.

  • Если в результате выполнения шага 8,B =
    , переходим к выполнению шага 12.
  • Если B
    , (при этом R =
    ), находим T? — значение времени занятости одного из процессоров, минимально превосходящее T?.
  • В множество строк, соответствующих множеству B процессоров с временем занятости T?, записывается задание — простой

    \ubox{T_\lambda - T_{\mu}}
    ; для всех процессоров из B время занятости полагается равным T?.

  • Проверяем, все ли задачи распределены: S?* =




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