3. Алгоритмы распределения работ на параллельно работающие устройства
Распределение независимых работ (Бондаренко а.Т., Сапатый п.С.)
Ш.1 Определяются
элементы множества
и
,
где
и
.
Ш.2 Формируется
последовательность I,
для которой выполняется неравенство
и последовательность J,
для которого справедливо
.
Ш.3 Получаем предварительное распределение работ по устройствам путем постановки в соответствие элементов I и J.
Ш.4 Упорядочиваем
последовательности I
и J
для выполнения
неравенства
.
Ш.5 В последовательности
элементов
,
входящей в J,
ищем первый элемент (k-й
по порядку в J),
для которого
и
.
Если таких элементов нет, переход к Ш.7,
в противном случае переход к следующему
шагу.
Ш.6 Выполняем
транспозицию элементов
и
в
J.
Восстанавливаем упорядоченность
последовательностей I
и J
для выполнения условий Ш.5.
Ш.7 Конец работы алгоритма. Решением считаются все соответствующие пары из I и J.
Рассмотрим более подробно работу алгоритма на примере, решив задачу №1.
Предварительное распределение на Ш.1-Ш.4 предполагает распределение на более быстродействующие процессоры более длительных работ. Быстродействие процессора определяется временем выполнения на нем заданного набора работ, а длительность выполнения конкретной работы оценивается по суммарному времени выполнения ее последовательно на всех устройствах.
Для построения расписания выполним алгоритм.
Ш.1 Определим
множества элементов
и
,
как сумма по строкам и сумма по столбцам.
Упорядочив множества, получим последовательность I и J;
I=(3,1,2); J=(1,2,3). Переставляем элементы I,J так, чтобы выполнялось условие в Ш.4.
,
для того чтобы выполнялось условие Ш.4,
сделаем перестановку попарно i,j
I=(3,2,1); J=(1,3,2).
Тогда
-
условие выполняется .
Выполним Ш.5 к=1..J , при к=2
и
т.е.,
и
;
меняем местами 2
и 1 элементы в J,
J=(3,1,2);
с учетом того, чтобы выполнялось условие
Ш.4
.
Ставя в соответствие
элементы множеств I
и J,
получаем следующее решение
=11.
Алгоритм построения расписания при N=M
Число процессоров равно числу заданий и на каждом процессоре должно выполниться только одно задание. Использование приближенного метода в данном случае представляется наиболее целесообразным для сокращения времени решения. Метод основывается на учете специфического свойства матрицы. Это свойство определяет стратегию распределения согласно следующей теореме.
Теорема 1: Если
в каждой i-й
строке матрицы приращения
,
для всех j
от 1 до N-1
и строки
матрицы расположены так, что
,
то приемлемое (оптимальное) распределение
будет составлено из элементов главной
диагонали. ([3] – доказательство теоремы).
Ш.1 Для каждой
строки матрицы весов определяется
приращение
и строки переставляются по порядку
убывания приращения.
Ш.2 Преобразованная
матрица разбивается на 4 квадратных
подматрицы размером
для четных N
и размером
и
для нечетных N.
Ш.3 С двумя матрицами,
главные диагонали которых совпадают с
главной диагональю исходной матрицы,
выполняют Ш.1. Процесс последовательной
декомпозиции подматриц заканчивается
при размерах
или
.