Диспетчирование параллельных вычислительных систем

Разбить на страницы

Показывать лекцию целиком

Диспетчер последовательного назначения

Частичная упорядоченность работ отсутствует

Пусть на ВК или многопроцессорную ВС поступает поток заданий, которые объединяются в пакет. Каждое задание требует запуска соответствующей программы. Программы не зависят друг от друга, т.е. одни программы не используют результаты выполнения других в качестве исходных данных. Сформированный пакет заданий необходимо выполнить за минимальное время, добившись максимальной эффективности вычислительных средств. Это означает необходимость распределения работ по времени их выполнения "поровну" между процессорами ВС.

Данная задача известна как задача о рюкзаках и отображает необходимость распределения неделимых объектов (нельзя разрезать консервную банку или спальный мешок!) так, чтобы веса рюкзаков были как можно ближе к одинаковым.

Известен "хороший" эвристический алгоритм, для которого не удалось найти пример неточного оптимального распределения.

Формируется очередь заданий (программ), представляющая собой невозрастающую последовательность времен их выполнения. Например, такая очередь может иметь вид, представленный на рис. 10.1, где длина каждого прямоугольника условно соответствует времени выполнения программы, указанного внутри него.

(рис 10.1) Множество работ, упорядоченное по невозрастанию времени выполнения

Сформулируем основное правило назначения: исполнитель, набравший минимальный вес, берет работу из головы очереди.

Пусть заданы три процессора-исполнителя. Первоначально все исполнители свободны. Тогда их приоритет обращения к очереди определяется их номерами. Очевидно, что при трехкратном обращении к очереди (каждым процессором) их загрузка будет выглядеть, как показано на рис. 10.2.

(рис 10.2) Первый шаг распределения

Справа на рисунке показана суммарная текущая загрузка каждого исполнителя.

2. Так как теперь минимально загружен третий процессор, он выбирает работу с весом 12, и вся картина загрузки принимает вид, отраженный на рис. 10.3.

(рис 10.3) Второй шаг распределения

3. Затем последовательно назначаются на процессоры 1 и 2 работы с весами 10 и 8. Загрузка процессоров принимает вид, показанный на рис. 10.4.

(рис 10.4) Третий шаг распределения

4. Продолжая таким же образом, получим окончательный план (рис. 10.5) выполнения работ.

(рис 10.5) Окончательный план выполнения работ

Легко убедиться в том, что более "короткого" плана выполнения данного комплекса работ нет, т.е. распределение совпало с оптимальным.

Диспетчер распределения частично упорядоченного множества работ в однородной ВС

В основе практических диспетчеров ВС лежат эвристические алгоритмы оптимального распараллеливания. Это обусловлено высокой сложностью методов точного решения задач распараллеливания. Реализация таких методов потребовала бы неоправданно больших затрат времени компьютера. Кроме того, подобные методы не позволяют получить гарантированные оценки времени решения: это время колеблется в большом диапазоне в зависимости от случайно складывающейся ситуации. Эвристические методы обеспечивают компромисс между временем работы диспетчера и точностью вырабатываемого расписания работы процессоров ВС.

Частичная упорядоченность заданий, точнее — программ их выполнения, означает, что одни программы используют результаты выполнения некоторых других программ данного пакета. Отражая этот факт графически и введя нумерацию программ, получают графовую структуру, показанную, например, на рис. 10.6.

(рис 10.6) Частично упорядоченное множество работ

Априорное формирование очереди невозможно, и очередность назначения работ выявляется динамически, по мере выполнения или имитации выполнения предыдущих шагов распределения заданий.

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

Выделяются входы графовой структуры, т.е. программы, не использующие выходную информацию других программ. В данном случае это — единственная программа № 1. Она назначается на первый свободный процессор 1. Множество входов исчерпано. Временная диаграмма загрузки процессоров ВС принимает вид, показанный на рис. 10.7.

(рис 10.7) Первый шаг распределени

Имитируется счет времени t, чем отслеживается состояние системы. Видно, что только в момент t = 2, т.е. после окончания выполнения программы № 1, могут появиться возможности для дальнейшего назначения. Работу №1 необходимо исключить из рассмотрения. Граф-схема на момент t = 2 принимает вид, показанный на рис. 10.8.

(рис 10.8) Имитация выполнения первой работы

Вновь выделяются входы графовой структуры текущего вида. В данном примере это программы, составляющие множество {№ 2, № 3, № 4}.

Здесь целесообразно ввести в действие обязательный элемент любого эвристического, т.е. использующего основополагающую догадку, алгоритма решения сложной комбинаторной задачи, к которой относится задача диспетчирования, — решающее правило:

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

Частным случаем этого правила является способ назначения заданий при отсутствии частичной упорядоченности.

В результате упорядочения программ по невозрастанию времен их выполнения формируется очередь на данном шаге распределения:{ № 3, № 2, № 4}. Диаграмма последовательной однократной загрузки свободных с момента t = 2 процессоров принимает вид, показанный на рис. 10.9.

(рис 10.9) Второй шаг распределения

Вновь включается счетчик времени, следя за состоянием системы. Очевидно, что какие-то изменения могут наступить только в результате выполнения заданий. В момент t = 4 заканчивается выполнение программы № 2. Хотя новых входов в граф-схеме не образуется, есть вход (программа № 4), оставшийся после предыдущего шага распределения. Программа № 4 назначается на освободившийся процессор 2.

Затем таким же образом производится назначение программ № 5 и № 6, и формируется окончательный вид (рис. 10.10) временной диаграммы выполнения пакета заданий.

(рис 10.10) Окончательный план выполнения работ

Значит, весь пакет программ выполняется за восемь условных единиц времени. Полученный план выполнения заданий в примере совпадает с оптимальным, т.к. более "короткого" расписания найти невозможно. В общем случае это свидетельствует о том, что данный алгоритм диспетчера "хороший", но не обеспечивает точного решения задачи оптимального распараллеливания. Точное же решение такой задачи, ввиду ее высокой сложности, не может служить основой оперативного диспетчера ВС.

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

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

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

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

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

Пусть в результате распределения составляется таблица-расписание $$\sigma,$$ содержащая n строк — расписаний одному процессору. В строке — последовательность заданий двух видов: выполнить работу (задачу, оператор и т.д.) $$\alpha,$$ простоять t единиц времени ( $$\ubox{t}$$ ). Момент T_i, i = 1 ... n, окончания (отсчет — от нуля) выполнения последней работы или проcтоя, назначенных к данному шагу распределения i -му процессору, назовем текущим временем занятости процессора.

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

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

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

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

Алгоритм.

Полагаем первоначально $$T_{i} = 0, i = 1 \dots n, A = \{ 0, \dots ,0\} , B= \{ 1 \dots n\} ,= \varnothing , R = \varnothing , \nu = 1, S_{\nu }^{*} = S^{*}$$ ; переходим к выполнению шага 6.

Находим T_mu = min{T_i} и множество B номеров процессоров с найденным временем занятости.

Находим множество $$\beta \subseteq A$$ номеров задач, назначенных последними на процессоры из B. После построения $$\beta$$ все позиции в A, соответствующие процессорам из B, полагаем равными нулю. Этим моделируется окончание выполнения задач на данных процессорах к моменту $$T_{\mu }$$.

Если $$\beta = \varnothing$$, переходим к выполнению шага 7 при $$R \ne \varnothing$$ и шага 10 при $$R = \varnothing$$ ; при $$\beta \ne \varnothing$$ выполняем следующий шаг.

Исключаем из $$S_{\nu }^{*}$$ строки и столбцы, соответствующие задачам, составляющим множество $$\beta.$$ Полагаем $$\nu := \nu + 1$$.

Находим множество R входов матрицы следования $$S_{\nu }$$, соответствующих не назначенным ранее задачам. Если $$R = \varnothing$$, переходим к выполнению шага 10.

Располагаем номера задач, составляющих R, в порядке невозрастания времени их выполнения.

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

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

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

Если в результате выполнения шага 8, $$B = \varnothing$$, переходим к выполнению шага 12.

Если $$B \ne \varnothing$$, (при этом $$R =\varnothing$$ ), находим $$T_{\lambda }$$ — значение времени занятости одного из процессоров, минимально превосходящее $$T_{\mu }$$.

В множество строк, соответствующих множеству B процессоров с временем занятости $$T_{\mu }$$, записывается задание — простой $$\ubox{T_\lambda - T_{\mu}}$$ ; для всех процессоров из B время занятости полагается равным $$T_{\lambda }$$.

Проверяем, все ли задачи распределены: $$S_{\nu }^{*} = \varnothing$$? При отрицательном результате проверки выполнение алгоритма продолжаем с шага 2.

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

$$R = \{ 1\} , T_{1} = T_{2} = 0, A = \{ 0, 0\} , B = \{ 1, 2\} , \beta =\varnothing , \sigma =\varnothing$$. Задачу 1 назначаем на первый процессор и исключаем из R. После этого A = {1, 0}, B = {2}, T₁ = 2. Т.к. теперь $$R =\varnothing , B \ne \varnothing$$, записываем во вторую строку $$\sigma$$ "простой в 2 единицы". Таблица $$\sigma$$ примет вид$$\begin{array}{c|ccc|c} 1 1 T_1=2\\ \hline \ubox{2} 2 T_2=2 \end{array}$$

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

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

В результате последовательного назначения задач из R таблица $$\sigma$$ примет вид$$\begin{array}{c|ccc|c} 1 1, 3 T_1=5\\ \hline \ubox{2}, 4 T_2=4 \end{array}$$

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

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

Таблица $$\sigma$$ примет вид$$\begin{array}{c|ccc|c} 1 1, 3 T_1=5\\ \hline \ubox{2}, 4, 2 T_2=5 \end{array}$$

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

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

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

Диспетчирование неоднородной ВС

Информационные графы с векторными весами вершин

Часто в состав ВС включают средства (процессоры) разной специализации и производительности. Например, МВК может комплексироваться разными ЭВМ, но допустимо исследование его как единой ВС. Новые ВС могут дополняться процессорами — эмуляторами ранее распространенных ЭВМ — для использования ранее разработанных программных продуктов. ВС, используемые в системах управления, дополняются процессорами, специализированных для решения конкретных задач, и т.д.

Появляется дополнительный выбор: на процессор какого типа возложить решение задачи? На основе каких типов процессоров с учетом количества процессоров разного типа целесообразно скомпоновать систему? Как спланировать работу неоднородной ВС таким образом, чтобы данный алгоритм выполнялся за минимальное время?

Пусть ВС комплектуется процессорами k типов по производительности и специализации. Пусть n_i , i = 1 ... k, — число процессоров i -го типа. Тогда для каждой работы следует задавать не скалярный вес (такими весами мы пользовались ранее), а вектор — вес. Каждая компонента такого веса равна времени выполнения работы процессорами соответствующего типа. Например, для k = 2 граф G с векторными весами вершин представлен на рис. 10.15а, а расширенная матрица следования — на рис. 10.15б.

(рис 10.15) К распределению работ в неоднородной ВС: а — информационный граф, б — расширенная матрица следования

На таком графе можно сформулировать оптимизационные задачи 1 и 2. Однако их методы решения весьма трудоемки (задачи экспоненциальной сложности), поэтому их заменяют эвристическими методами (полиномиальной сложности). Более того, пусть мы умеем решать задачу нахождения плана выполнения работ, минимизирующего время выполнения всего алгоритма (т.е. задачу 2). Тогда на основе этого решения можно давать заключение о возможности применения ВС в каждой конкретной комплектации, т.е. о решении задачи 1. При этом придется испытывать различные комбинации такой комплектации.

Таким образом, необходимо построить достаточно эффективный алгоритм диспетчирования неоднородной ВС, т.е. эвристический алгоритм планирования выполнения за минимальное время алгоритма, заданного информационным графом с векторными весами вершин.

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

В основе диспетчера лежит следующее решающее правило:

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

Введем сквозную нумерацию процессоров от 1 до $$N = \sum_{i=1}^k n_i$$. Зададим вес {t_j1 ... t_jN} j -й вершины (j = 1 ... m; m — размер матрицы S или объем буфера диспетчера) так, что при новой нумерации процессоров t_jl — время выполнения j -й работы l -м процессором. Например, при k = 2, n₁ = 1, n₂ = 2 расширенная матрица следования на рис. 10.15б примет вид, представленный на рис. 10.16.

В процессе распределения работ будем формировать расписание в виде таблицы $$\tau,$$ состоящей из N строк, каждая из которых соответствует одному процессору. В строке будем записывать последовательность заданий одному процессору. Задания имеют два вида: выполнить работу $$\alpha,$$ простоять t единиц времени (изображается $$\ubox{t}$$ ). Момент T_i , i = 1 ... N, окончания (отсчет ведется от нуля) выполнения последней работы или простоя, назначенных к данному моменту распределения i -му процессору, назовем текущим временем занятости процессора.

В процессе распределения и имитации выполнения работ будем использовать множество A номеров работ, уже назначенных на процессоры, но не выполненных в анализируемый момент времени. A представляет собой таблицу, содержащую пары "назначенная для выполнения задача — время окончания ее выполнения ", т.е. $$A = \{ \alpha _{j} \leftrightarrow t_{j}\}$$.

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

Алгоритм диспетчера

Полагаем первоначально $$T_{l} = 0, l = 1, \dots N, A = B = R =\varnothing , \nu = 1, S_{\nu } = S,(\nu$$ — номер шага распределения). Переходим к выполнению 5.

Находим в множестве A значение

t_mu = min_j
{t_i}

и множество $$B \subseteq A$$ номеров работ, назначенных на процессоры и закончивших выполнение к моменту $$t_{\mu }$$. Полагаем равными нулю все позиции A, составляющие B. Этим имитируется окончание выполнения работ на процессорах к моменту времени $$t_{\mu }$$.

Для всех процессоров, для которых текущее время занятости меньше значения $$t_{\mu } (T_{i} < t_{\mu })$$, записываем простой в течение времени $$t_{\mu } - T_{i}$$ (символом простоя $$\ubox{t_{\mu} - T_i}$$ ). Для этих процессоров полагаем $$T_{i} =t_{\mu }$$.

Исключаем из $$S_{\nu }$$ строки и столбцы, соответствующие всем работам из B, после чего матрицу $$S_{\nu } (S^{*}_{\nu })$$ уплотним. Полагаем $$\nu := \nu + 1$$. Таким образом сформируется матрица $$S_{\nu }$$ (а также $$S^{*}_{\nu }$$ ) на новом шаге распределения.

Находим множество R — входов матрицы следования $$S_{\nu }$$, соответствующих не назначенным ранее работам. Если $$R \ne \varnothing$$, переходим к выполнению 6, в противном случае выполняем пункт 2.

Пусть для определенности $$R = \{ \alpha _{1} \dots \alpha _{r}\}$$, работе $$\alpha _{p}$$ соответствует вес {t_p1 ... t_pN}, p = 1 ... r. Формируем суммы

T_l + t_pl ,  l = 1 ... N,
p = 1 ... r

. Для каждого значения p (т.е. для каждой работы из R ) находим минимальную (по l ) из таких сумм, т.е. для каждой работы находим один или несколько процессоров, на которых время окончания выполнения этой работы минимально при текущих значениях занятости процессоров. Найденные суммы сведем в невозрастающую последовательность R^*, состоящую из r чисел. При этом сохраним информацию о соответствии процессорам.

Ставим в соответствие каждой p -й работе, представленной в последовательности R^*, значение $$\sigma _{p}$$, равное числу процессоров, при выполнении на которых достигается найденное минимальное время окончания выполнения этой работы.

Производим последовательное назначение работ на процессоры следующим образом. Назначаем не более N работ слева направо в соответствии с вхождением времени окончания их выполнения в последовательность R^*. Каждую p -ю работу назначаем на все те процессоры, (их число равно $$\sigma _{p}$$ ), на которых достигается входящее в R^* время окончания выполнения. В результате те работы, для которых $$\sigma > 1$$, окажутся назначенными более чем на один процессор, а на один процессор на данном шаге могут оказаться назначенными более одной работы. Чтобы определить окончательно, на какой процессор должна быть назначена p -я работа, воспользуемся следующей процедурой. Для каждого процессора проводим анализ, сколько работ назначено на него на данном шаге распределения. Если назначения не произошло, переходим к анализу назначения на следующий процессор или заканчиваем анализ процессоров, если все они просмотрены. Если оказалась назначенной на процессор одна, p -я, работа, считаем ее окончательно закрепленной за данным процессором, и, если $$\sigma _{p} > 1$$, исключаем ее из рассмотрения при анализе последующих процессоров — т.е., снимаем ее с назначения на другие процессоры. Если на процессор назначено более одной работы, закрепляем за процессором лишь ту работу $$\alpha _{p}$$, которая имеет минимальное значение $$\sigma _{p}$$. Если несколько работ имеют равное минимальное значение $$\sigma _{p}$$, назначаем любую (первую) из них. Для множества работ $$\{ \gamma \}$$, отклоненных от назначения на данный процессор, полагаем $$\sigma _{\gamma } := \sigma _{\gamma }- 1$$. Значение $$\sigma _{\gamma } = 0$$ означает, что работе $$\gamma$$ отказано в назначении на данном шаге распределения. Назначенную работу исключаем из рассмотрения при анализе следующих процессоров. Номера назначенных работ оказываются записанными в строки таблицы $$\tau,$$ соответствующие процессорам. Эти номера исключаем из R. Номер каждой назначенной работы и время окончания ее выполнения (оно же — время занятости процессора) заносим в A.

Проверяем, все ли работы распределены. При отрицательном результате проверки переходим к выполнению 2.

Конец алгоритма.

Пример.

При k = 2, n₁ = 1, n₂ = 2, (N = 3) распределим работы, отображенные расширенной матрицей следования на рис. 10.16 (соответствующей графу на рис. 10.15), для минимизации времени выполнения.

(рис 10.16) Преобразование расширенной матрицы следования

$$T_{1} = T_{2} = T_{3} = 0, A = B = \varnothing , S_{1} = S, R =\{ 1\}$$. Выполнение работы 1 ранее всех закончит процессор 1. После ее назначения $$T_{1} = 1, T_{2} = T_{3} = 0,A = \{ 1 \leftrightarrow 1\}$$.

Найдем в A работу 1 с минимальным временем окончания выполнения, равным 1. Записываем простои в одну единицу времени процессорам 2 и 3. Таблица $$\tau$$ принимает вид$$\begin{array}{l|l@{\qquad}|l} 1 1 T_1=1\\ \hline 2 \ubox{1} T_2=1\\ \hline 3 \ubox1 T_3=1 \end{array}$$

После исключения первой строки и первого столбца из S₁ (т.е. по матрице S₂ ) найдем R = {2, 3, 4, 6}. Составим таблицу 10.1 времени окончания выполнения каждой работы из R каждым процессором l = 1, 2, 3. Минимальное время окончания выполнения каждой работы выделено.

l	T_l+t_2l	T_l+t_3l	T_l+t_4l	T_l+t_6l
1	4	3	6	4
2	3	6	6	2
3	3	6	6	2

Формируем последовательность $$R^{*} = \{ 6 (4; 1, 2, 3, \sigma _{4} = 3), 3(2; 2,3$$, $$\sigma _{2} = 2), 3( 3; 1, \sigma _{3} = 1), 2 (6; 2,3,\sigma _{6} = 2)\}$$, где в круглых скобках указаны номер работы, список процессоров, на которых достигается минимальное время окончания ее выполнения, и число $$\sigma _{p}$$ этих процессоров.

Назначим первоначально (таблица 10.2) работу 4 на процессоры 1, 2, 3, работу 2 — на процессоры 2 и 3 , работу 3 — на процессор 1.

1	4 ( $$\sigma$$ ₄ = 3), 3( $$\sigma$$ ₃ = 1)
2	4 ( $$\sigma$$ ₄ = 3), 2( $$\sigma$$ ₂ = 2)
3	4 ( $$\sigma$$ ₄ = 3), 2( $$\sigma$$ ₂ = 2)

После анализа значений $$\sigma _{p}$$ оставим на процессоре 1 работу 3 (после чего $$\sigma _{4} = 2$$ ), на процессоре 2 — работу 4 (после чего $$\sigma _{2} = 1$$ ), на процессоре 3 — работу 2, $$A = \setminus \{ 3 \leftrightarrow 3, 4 \leftrightarrow 6, 2\leftrightarrow 3\setminus \}$$. Таблица распределения $$\tau$$ примет вид$$\begin{array}{c|c|c} 1 1, 3 T_1 = 3\\ \hline 2 \ubox 1, 4 T_2 = 6\\ \hline 3 \ubox 1, 2 T_3 = 3 \end{array}$$

B = {2, 3}. После исключения строк и столбцов, соответствующих работам 2 и 3, из матрицы S₂, т.е. по сформированной матрице S₃, найдем R = {5, 6}. Составим таблица 10.3 значений времени окончания выполнения каждой работы из R каждым процессором.

l	T_l+t_5l	T_l+t_6l
1	5	6
2	10	7
3	7	4

Из таблицы найдем $$R^{*} = \{ 5 (5; 1, \sigma _{5} = 1), 4 (6; 3, \sigma _{6} =1)\}$$,

Назначим работу 5 на процессор 1, работу 6 — на процессор 3, $$A =\{ 5 \leftrightarrow 5,4 \leftrightarrow 6, 6 \leftrightarrow 4\}$$. Таблица распределения $$\tau$$ примет вид$$\begin{array}{c|c|c} 1 1, 3, 5 T_1 = 5\\ \hline 2 \ubox1, 4 T_2 = 6\\ \hline 3 \ubox 1, 2, 6 T_3 = 4 \end{array}$$

B = {6}. После исключения строки и столбца, соответствующих работе 6, из матрицы следования S₃, т.е. по сформированной матрице S₄, найдем $$R = \varnothing$$. Назначим процессору 3 простой в течение одной условной единицы времени. Таблица $$\tau$$ примет вид$$\begin{array}{c|c|c} 1 1, 3, 5, T_1> = 5\\ \hline 2 \ubox 1, 4 T_2 = 6\\ \hline 3 \ubox 1, 2, 6, \ubox1 T_3 = 5 \end{array}$$

B = {5}. После преобразования матрицы S₄, т.е. по матрице S₅, найдем R = {7, 8}. Из таблицы 10.4, аналогичной таблице 3, найдем $$R^{*} = \{ 9 (8;1, \sigma _{8} = 1), 7 (7; 3, \sigma _{7} = 1)\} .$$

l	T_l+t_7l	T_l+t_8l
1	9	9
2	8	11
3	7	10

Назначаем работу 8 на процессор 1, работу 7 — на процессор 3. Таблица $$\tau$$ примет вид$$\begin{array}{c|c|c} 1 1, 3, 5, 8 T_1 = 9\\ \hline 2 \ubox 1, 4 T_2 = 6\\ \hline 3 \ubox 1, 2, 6, \ubox 1, 7 T_3 = 7 \end{array}$$

B = {4}. После исключения строки и столбца, соответствующих работе 4, из матрицы следования S₅, т.е. по сформированной при этом матрице S₆, найдем R = {9}. Время окончания выполнения работы 9 на процессорах равно соответственно 10, 8, 9. Назначаем работу 9 на процессор 2. Таблица $$\tau$$ примет окончательный вид$$\begin{array}{c|c|c} 1 1, 3, 5, 8 T_1 = 9\\ \hline 2 \ubox1, 4, 9 T_2 = 8\\ \hline 3 \ubox 1, 2, 6, \ubox 1, 7 T_3 = 7. \end{array}$$

Дополнение.

Данный диспетчер для неоднородной ВС построен на основе обобщения рассмотренного диспетчера последовательного назначения для однородных ВС, который можно рассматривать как частный случай при k = 1.

Он применим и в другом частном случае: когда отсутствует частичная упорядоченность работ, то есть когда надо разделить "поровну" взаимно независимые работы между n исполнителями. Наглядный пример такого распределения составляет задача о рюкзаках, рассмотренная в разделе 10.1.1.

Страницы: