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

Рис. 7.13. Графики функции: а — для ранних сроков окончания работ,,б — для некоторого допустимого расписания

Для графического представления функции F удобно пользоваться временной диаграммой, которая для второго случая, например, имеет вид, представленный на рисунке 7.14..

Рис. 7.14. Временная диаграмма функции F

Пусть данный граф G, в котором учтены транзитивные связи, образует l полных множеств взаимно независимых работ (ПМВНР). (Каждая пара таких множеств может иметь непустое пересечение.) Обозначим ri, i = 1 , ... , l, число работ, образующих i-е полное множество и найдём

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. Максимальное значение плотности загрузки

….

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

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

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

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

…

Теорема 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).

Нашей конечной целью является выбор таких расписаний, которые позволяют решить задачи 1 и 2

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

назовём плотностью загрузки, найденной для значений ф1 , ... , фm.

Для заданных ф1 , ... , фm значение функции F в каждый момент времени t совпадает с числом одновременно (параллельно) выполняющихся в этот момент работ.

Например, по диаграмме на 7.11, т. е. для ф1 = ф11, ф2 = ф12, ... , ф8 = ф18, функция F(2, 3, 3, 4, 7, 8, 6, 9, t) имеет вид, представленный на рис. 7.13а. Для допустимого расписания, определяемого набором значений ф1 = 2, ф2 = 4, ф3 = 3, ф4 = 4, ф5 = 8, ф6 = 9, ф7 = 7, ф8 = 10, функция F(2, 4, 3, 4, 8, 9, 7, 10, t) имеет вид, представленный на рис. 7.13б.

Рис. 7.13. Графики функции: а — для ранних сроков окончания работ,,б — для некоторого допустимого расписания

Для графического представления функции F удобно пользоваться временной диаграммой, которая для второго случая, например, имеет вид, представленный на рисунке 7.14..

Рис. 7.14. Временная диаграмма функции F

Пусть данный граф G, в котором учтены транзитивные связи, образует l полных множеств взаимно независимых работ (ПМВНР). (Каждая пара таких множеств может иметь непустое пересечение.) Обозначим ri, i = 1 , ... , l, число работ, образующих i-е полное множество и найдём