Формальное описание алгоритма диспетчера
Пусть задана (рис. 10.11) расширенная матрица следования S*, отражающая информационные связи внутри множества m работ j = 1...m. Веса tj — времена выполнения каждой j-й работы на каждом из n процессоров однородной ВС с общей ОП.
Рис. 10.11. Граф алгоритма и расширенная матрица следования
Необходимо составить расписание параллельного выполнения работ, при котором время выполнения всей совокупности работ минимально.
Вспомогательные построения
Пусть в результате распределения составляется таблица-расписание?, содержащая n строк — расписаний одному процессору. В строке — последовательность заданий двух видов: выполнить работу (задачу, оператор и т.д.)
Пусть в процессе распределения формируется таблица (множество) A номеров задач, назначенных к данному шагу распределения последними для выполнения на каждом процессоре. Эти номера заносятся в позиции, закрепленные за каждым процессором. Если последним был записан простой, в соответствующей позиции значится 0.
В множество B будем объединять процессоры (один или более), имеющие на данном шаге распределения минимальное время занятости.
В множество ? выделим те работы из A, которые выполняются на процессорах из B.
Множество R — множество работ, соответствующих входам (нулевым строкам) текущего значения изменяемой в процессе распределения матрицы следования S.
Алгоритм.
- Полагаем первоначально Ti = 0, i = 1 ... n, A = {0, ...,0}, B = {1 ... n}, = , R =
, ? = 1, S?* = S*; переходим к выполнению шага 6. - Находим Tmu = min{Ti} и множество B номеров процессоров с найденным временем занятости.
- Находим множество ? A номеров задач, назначенных последними на процессоры из B. После построения ? все позиции в A, соответствующие процессорам из B, полагаем равными нулю. Этим моделируется окончание выполнения задач на данных процессорах к моменту T?.
- Если ? = , переходим к выполнению шага 7 при R
и шага 10 при R =; при ?выполняем следующий шаг. - Исключаем из S?* строки и столбцы, соответствующие задачам, составляющим множество ?.
Полагаем ? := ? + 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?, записывается задание — простой; для всех процессоров из B время занятости полагается равным T?.
- Проверяем, все ли задачи распределены: S?* =
? При отрицательном результате проверки выполнение алгоритма продолжаем с шага 2.
Пример. Продолжим рассмотрение G и S* (S), представленных на рис. 10.11.
R = {1}, T1 = T2 = 0, A = {0, 0}, B = {1, 2}, ? =, ? =. Задачу 1 назначаем на первый процессор и исключаем из R. После этого A = {1, 0}, B = {2}, T1 = 2. Т.к. теперь R =, B, записываем во вторую строку ? "простой в 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 таблица ? примет вид
A = {3, 4}, T? = min {5, 4} = 4, B = {2}, ? = {4}. После исключения из S* (рис. 10.13) информации о задаче 4 сформируем множество неотмеченных в A входов R = {2, 6}.
Рис. 10.13. Матрица следования после второго шага распределения
Таблица ? примет вид
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 и совпадает с точным минимальным.
