Неформальная постановка задач параллельного программирования ВС (стр. 4 )

R = max {r1 , ... , rl}.

Тогда

т. к. возможно и такое распределение выполняемых работ во времени, задаваемое набором ф1 , ... , фm, (т. е. допустимое расписание), когда на каком-то отрезке времени выполняются все работы, составляющие ПМВНР с числом R работ.

Например, для графа на рис. 7.1 мы нашли ПМВНР {3,5,6,7}, включающее четыре работы. Тогда существует допустимое расписание, например, ф1 = 2, ф2 = 3, ф3 = 5, ф4 = 4, ф5 = 8, ф6 = 8, ф7 = 6, ф8 = 9 такое, при котором максимальное значение плотности загрузки F равно четырём (рис. 7.15).

Рис. 7.15. Максимальное значение плотности загрузки

Таким образом, справедливо утверждение

Лемма. Минимальное число n процессоров одинаковой специализации и производительности (т. е. в однородной ВС), способных выполнить данный алгоритм за время T Tкр, не превышает R = max {r1 , ... , rl }, где ri, i = 1 , ... , l, — число работ, входящих в i-е ПМВНР, которое составлено по взвешенному графу G, соответствующему этому алгоритму.

Определение 8. Функцию

назовём загрузкой отрезка [и1, и2] [0,T] для заданного допустимого расписания ф1, ... ,фm.

Функция Ф определяет объём работ (суммарное время их выполнения) на фиксированном отрезке их выполнения при заданном допустимом расписании.

Так, для отрезка времени [0, 4] [0, 10] на рис. 7.13а Ф = 10; для отрезка времени [1, 3] на ррис. 7.13б Ф= 4; для отрезка времени [2, 5] на рис. 7.15 Ф = 10 и т. д.

Определение 9. Функцию

назовём минимальной загрузкой отрезка [и1, и2] [0, T].

Функция определяет минимально возможный объём работ, который при данном T и при различных допустимых значениях (расписаниях) ф1 , ... , фm должен быть выполнен на отрезке времени [и1, и2] [0, T]. Это означает, что как бы мы не планировали вычислительный процесс, который должен быть закончен к моменту времени T, т. е. какой бы набор значений ф1 , ... , фm мы не выбрали, объём работ, выполняемых на отрезке времени [и1, и2], не может быть меньше значения (T) = (и1, и2).

Теорема 1. Для того чтобы T было наименьшим временем выполнения данного алгоритма однородной вычислительной системой, состоящей из n процессоров, либо чтобы n процессоров было достаточно для выполнения данного алгоритма за время T, необходимо, чтобы для данного отрезка времени [и1, и2] [0, T] выполнялось соотношение

(7.1)

Доказательство. Нетрудно видеть, что если при данном наборе ф1 , ... , фm — сроках окончания выполнения работ, в том числе и при таком наборе, при котором обеспечивается минимальное или заданное T = max {ф1 , ... , фm}, для реализации алгоритма достаточно n процессоров, то

Отсюда, для любого отрезка времени [и1, и2] [0, T]

что и требовалось доказать.

Необходимость, но не достаточность условия (7.1) покажем на примере. Пусть алгоритму соответствует граф G на рис. 7.16а. Пусть T=3, и одна из возможных диаграмм выполнения алгоритма — на рис. 7.16б.

Рис. 7.16. Пример: минимальная плотность загрузки не соответствует действительной: а — информационный граф, б — временная диаграмма загрузки

Оценим на основе (7.1) число n процессоров, достаточное для выполнения алгоритма в указанное время. Из (7.1) имеем общее соотношение

(7.2)

Для получения полной оценки надо перебрать все отрезки [и1, и2] [0, T] т. е.

(7.3)

Проанализируем все возможные отрезки [и1, и2] [0, 3] : (3)(0, 1) = (3)(1, 2) (3)(2, 3) = 0, (3)(0, 2) = (3)(1, 3) = 3, (3)(0, 3) = 6. Находим минимальное n = 2, удовлетворяющие (7.3). Однако из рисунка видно, что не существует плана выполнения работ на двух процессорах за время T=3. Минимально достаточное число процессоров здесь n = 3.

Функция (T)(и1, и2) минимальной загрузки отрезка времени является одним из основных средств оценки предпринимаемых действий при решении задач распараллеливания. Поэтому ниже будет дан алгоритм нахождения её значения.

Предварительно определим функцию

Тогда значение о(ф1j - и1) характеризует условный объём части работы j на отрезке времени [и1, и2] при условии ф1j - tj и1 и при максимальном смещении времени выполнения работы j влево (рис. 7.17а).

Значение о (и2 - ф2j(T) + tj) характеризует аналогичный объём работы j при максимальном смещении времени выполнения работы j вправо. Это соответствует, например, ситуации, изображённой на рис. 7.17б.

Рис. 7.17. Нахождение минимальной плотности загрузки отрезка: все различные случаи соотношения времени выполнения работ и сроков

Если для работы j оба указанных выше значения функции о отличны от нуля, но не превышают значение tj и и2 - и1, то максимально разгрузить отрезок [и1, и2] от работы j можно смещением времени его выполнения в сторону, обеспечивающую меньшее из двух указанных выше значений о (рис. 7.17в).

Существуют два случая, когда работа j не может быть хотя бы частично смещена с отрезка [и1, и2] :

а) и1 ф1j - tj < ф2j (T) и2, в этом случае очевидно, что tj и2 - и1 (рис. 7.17г), и объём работы j, выполняемой на отрезке, совпадает с объёмом tj всей этой работы;

б) ф1j и2 Л ф2j(T) - tj и1, в этом случае очевидно, что tj и2 - и1 (рис. 7.17д), и объём части работы j, выполняемой на отрезке [и1, и2] совпадает со значением и2 - и1.

Приведённый ниже алгоритм объединяет все возможные указанные выше случаи.

Алгоритм 4 нахождения значения функции (T)(и1, и2).

1. Предполагаем, что для каждой работы j = 1, ... , m, известны значения tj, ф1j, ф2j(T). Полагаем равным нулю значение переменной .

2. Организуем последовательный анализ работ j = 1, ... , m.

3. Для каждой работы j полагаем

:= + min {о (ф1j - и1), о(и2 - ф2j(T) + tj), tj, и2 - и1}.

После перебора всех работ = (T)(и1, и2).

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

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

Приведём аналогичное соотношение для нижней оценки минимального времени Т.

Теорема 2. Пусть заданный алгоритм выполняется на ВС, состоящей из n процессоров, и T* — текущее значение оценки снизу времени выполнения алгоритма. Пусть на отрезке времени [и1, и2] [0, T*] выполняется соотношение

(T*)(и1,и2) - n(и2 - и1) = d > 0.

Тогда минимальное время T выполнения алгоритма удовлетворяет соотношению

(7.4)

Теоремы 1 и 2 на основе анализа такой локальной характеристики параллельного алгоритма, как значение функции минимальной загрузки отрезка, предлагают способы оценки снизу ресурсов, необходимых для реализации каждого заданного алгоритма: