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

         

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


Пусть задана (рис. 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?* строки и столбцы, соответствующие задачам, составляющим множество ?.
    Полагаем ? := ? + 1.
  6. Находим множество R входов матрицы следования S?, соответствующих не назначенным ранее задачам. Если R =
    , переходим к выполнению шага 10.
  7. Располагаем номера задач, составляющих R, в порядке невозрастания времени их выполнения.


  8. Производим поочередное назначение задач, составляющих упорядоченное множество R, на процессоры, составляющие множество B. Назначенные задачи исключаем из R, а процессоры, на которые произведено назначение, — из B. Номер каждой назначенной задачи заносим в позицию A, соответствующую данному процессору. Время занятости этого процессора увеличиваем на время выполнения назначенной задачи. Последовательное назначение прекращается в одном из трех случаев: a) R


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

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

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

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

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


  11. В множество строк, соответствующих множеству B процессоров с временем занятости T?, записывается задание — простой
    ; для всех процессоров из B время занятости полагается равным T?.

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




    ? При отрицательном результате проверки выполнение алгоритма продолжаем с шага 2.


Пример. Продолжим рассмотрение G и S* (S), представленных на рис. 10.11.





  1. R = {1}, T1 = T2 = 0, A = {0, 0}, B = {1, 2}, ? =
    , ? =
    . Задачу 1 назначаем на первый процессор и исключаем из R. После этого A = {1, 0}, B = {2}, T1 = 2. Т.к. теперь R =
    , B
    , записываем во вторую строку ? "простой в 2 единицы". Таблица ? примет вид




  2. A = {1, 0} , T? = T1 = T2 = 2 , B = {1, 2} , ? = {1}. После исключения из S* первой строки и первого столбца (рис. 10.12) сформируем множество входов R = {2, 3, 4} которое переупорядочим по невозрастанию времен решения задач, R = {3, 4, 2}.


    Рис. 10.12.  Матрица следования после первого шага распределения


    В результате последовательного назначения задач из R таблица ? примет вид




  3. A = {3, 4}, T? = min {5, 4} = 4, B = {2}, ? = {4}. После исключения из S* (рис. 10.13) информации о задаче 4 сформируем множество неотмеченных в A входов R = {2, 6}.


    Рис. 10.13.  Матрица следования после второго шага распределения

    Таблица ? примет вид




  4. A = {3, 2} , T? = 5 , B = {1, 2}, ? = {3, 2}. После исключения (рис. 10.14) информации о задачах 3 и 2 из S* найдем R = {5, 6}. В результате последовательного назначения получаем окончательный вид таблицы ?.


    Рис. 10.14.  Матрица следования после третьего шага распределения и окончательный план выполнения работ



Tреш = max{T1, T2} = 7 и совпадает с точным минимальным.


Содержание раздела