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



              

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


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

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

Введем сквозную нумерацию процессоров от 1 до

N = \sum_{i=1}^k n_i
. Зададим вес {tj1 ... tjN} j-й вершины (j = 1 ... m; m — размер матрицы S или объем буфера диспетчера) так, что при новой нумерации процессоров tjl — время выполнения j-й работы l-м процессором. Например, при k = 2, n1 = 1, n2 = 2 расширенная матрица следования на рис. 10.15б примет вид, представленный на рис. 10.16.

В процессе распределения работ будем формировать расписание в виде таблицы ?, состоящей из N строк, каждая из которых соответствует одному процессору. В строке будем записывать последовательность заданий одному процессору. Задания имеют два вида: выполнить работу

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

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

j - tj}.

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

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

  1. Полагаем первоначально Tl = 0, l = 1, ... N, A = B = R =
    , ? = 1, S? = S, (? — номер шага распределения). Переходим к выполнению 5.
  2. Находим в множестве A значение tmu = minj

    {ti} и множество B

    A номеров работ, назначенных на процессоры и закончивших выполнение к моменту t?. Полагаем равными нулю все позиции A, составляющие B.


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