Временные оценки на информационных графах

Информационный граф отображает порядок следования работ. Тогда очевидно, что момент окончания выполнения любой работы (если началом отсчёта времени является момент начала выполнения работ — начало выполнения алгоритма) не может быть меньше максимальной из длин всех путей, которые заканчиваются вершиной, соответствующей этой работе.

Таким образом, для каждой i = 1 , ... , m работы алгоритма, представленного информационным графом, можно найти ранний срок ?1i окончания её выполнения. Если же выполнение алгоритма ограничено временем T < Tкр, то для каждой работы можно найти и поздний срок ?2i(T) окончания её выполнения. Окончание выполнения i-й работы позже этого срока приводит к тому, что выполнение других работ, следующих за данной, не может быть закончено до истечения времени T. Иначе говоря, поздний срок окончания выполнения данной работы не может превышать разности между значением T и максимальной из длин путей, в первую вершину которых входит дуга, что исходит из вершины, соответствующей данной работе. Без задания значения T (ограничения на длительность вычислительного процесса) определение позднего срока окончания выполнения работы не имеет смысла.

При T = Tкр ранние сроки окончания выполнения работ, составляющих критические пути, совпадают с поздними сроками окончания их выполнения.

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

Алгоритм 2 нахождения ранних сроков окончания выполнения работ.

1. Полагаем первоначально ?11 = ?12 = ... = ?1m

   = 0.

2. Производя циклический обзор строк матрицы S, находим очередную из необработанных строк.
   Если все строки обработаны, выполнение алгоритма заканчивается.
3. Пусть j — номер найденной необработанной строки. Если j-я строка не содержит единичных элементов, полагаем ?1j = tj. Переходим к выполнению шага 6.
4. Если j-я строка содержит единичные элементы, выбираем элементы множества {?11 , ... , ?1m}, соответствующие номерам единичных элементов j-й строки.
5. 
   
   Если все выбранные таким образом элементы, образующие множество {?1j(?)}, ? = 1, ... , kj, отличны от нуля, полагаем ?1j = max ?1 j? + tj.
   
   Если хотя бы один из выбранных элементов нулевой (соответствующий ранний срок ещё не найден), выполняем шаг 2.
   
   
6. 
   
   Обработанную j-ю строку метим, чтобы исключить её повторную обработку. Переходим к выполнению шага 2.
   
   Примечание. Если граф G не содержит контуров, зацикливание при этом невозможно.
   
   

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

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

Очевидно, что Tкр = max {?11 , ... , ?1m}.

По матрице S* ( S — треугольная) на рис. 7.5 (граф G — на рис. 7.1) находим

?11 = t1 = 2, ?12 = t2 = 3, ?13 = ?11 + t3

=3, ?14

= ?11 + t4 = 4, ?15 = max {?11, ?12 + t5= 7, ?16 = max {?11, ?14} + t6 = 8, ?17 = max {?12,?14 } + t7 = 6, ?18 = max {?13, ?15, ?16, ?17} + t8 = 9; Tкр = 9.

Чтобы рассмотреть пример с нетреугольной матрицей следования, выберем граф G без контуров с "неправильно" пронумерованными вершинами (рис. 7.10).


Рис. 7.10.  Информационный граф с не треугольной матрицей следования

После обработки первой строки ?11 = 1. Попытка обработать вторую строку неудачна, т.к. ?13 и ?14 ещё не найдены. После обработки третьей строки ?13 = ?11 + t3 = 3. Обработка четвёртой строки даёт ?14 = 2. После обработки пятой строки ?15 = ?13 + t5 = 4. Попытка обработки шестой строки неудачна, т.к. не найдено значение ?12. Приступаем к следующему циклу обзора необработанных строк S. Обрабатываем вторую строку: ?12 = max {?13, ?14} + t2 = 6.


После обработки шестой строки ?16 = ?12 + t6 = 7. Tкр = 7.

Для удобства представления наряду с другими способами будем пользоваться наглядными диаграммами выполнения работ при заданных значениях времени начала или окончания их выполнения. Работы обозначаются прямоугольниками с постоянной высотой и длиной, равной времени выполнения. Стрелки, связывающие прямоугольники-работы, соответствуют дугам в графе G. На рис. 7.11 представлена диаграмма выполнения работ, отраженных графом G на рис. 7.1 и расширенной матрицей следования на рис. 7.5 — при ранних сроках выполнения работ.


Рис. 7.11.  Временная диаграмма выполнения работ при ранних сроках окончания

Алгоритм 3 нахождения поздних сроков окончания выполнения работ при заданном значенииТ.

1. Полагаем первоначально ?21(T) = ... = ?2m(T) = 0.
2. Производя циклический обзор справа налево столбцов матрицы S, находим очередной из не обработанных ещё столбцов. Если все столбцы обработаны, выполнение алгоритма заканчивается.
3. Пусть j — номер найденного необработанного столбца. Если j-й столбец не содержит единичных элементов, полагаем ?2j(T) = T. Переходим к выполнению шага 6.
4. Если j-й столбец содержит единичные элементы, выбираем элементы множества { ?21(T) , ... ,?2m(T) }, соответствующие номерам единичных элементов j-го столбца.
5. 
   
   Если все выбранные таким образом элементы {?2j?}(T)}
   
   {?21(T), ... , ?2m(T)}, ? = 1 , ... , kj, отличны от нуля, полагаем
   
   ?2j (T) = min {?2j? (T) - tj? }.
   
   В противном случае выполняем шаг 2.
   
   
6. Обработанный j-й столбец метим с целью исключения его повторной обработки. Переходим к выполнению шага 2.

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

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

Для матрицы S* (матрица S — треугольная) на рис. 7.5 и для T = 10 за один просмотр находим

?28(10) = 10, ?27(10) = ?28(10) - t8 = 9, ?26(10) = ?28(10)- t8 = 9, ?25(10) = ?28(10) - t8 = 9 , ?24 = min {?26(10), - t6, ?27(10) - t7} = 5, ?23(10) = ?28(10) - t8 = 9, ?22(10) = min {?25(10) - t5, ?27(10) - t7 } = 5, ?21(10) = min {?23(10) - t3, ?24(10) - t4, ?25(10) - t5, ?26(10) - t6} = 3.



Для нетреугольной матрицы S на рис. 7.10 при T = 10 находим ?26(10) = ?25(10) = 10. Обработка четвёртого столбца откладывается, т.к. не найдено значение ?22(10). По этой же причине не обрабатывается третий столбец. После обработки второго столбца находим ?22(10) = ?26(10) - t6 = 9.

Обработка первого столбца невозможна, т.к. ещё не найдено значение ?23(10). Продолжаем циклический обзор столбцов. После обработки четвёертого столбца получаем ?24(10) = ?22(10) - t2 = 6. Обработка третьего столбца даёт ?23(10) = min {?22(10) - t2, ?25(10) - t5} = 6. После обработки первого столбца находим ?21(10) = ?23(10) - t3 = 4.

Диаграммы выполнения работ при поздних сроках окончания, по графам на рис. 7.1 и 7.10, при T = 10 представлены на рис. 7.12 — (а) и (б), соответственно. (Стрелки, соответствующие дугам в графах, опущены в связи с их избыточностью.)


Рис. 7.12.  Диаграммы выполнения работ при поздних сроках окончания: а — для графа на рис. 7.1,б — для графа на рис. 7.10

Пусть ?j — произвольное значение момента окончания выполнения j-й работы, j =1 , ... , m,

?1j ?j ?2j(T) (?j [?1j, ?2j(T)]).

Меняя значения {?j}, j = 1 , ... ,m, но соблюдая при этом порядок следования работ, мы получим множество допустимых расписаний выполнения работ.

Нашей конечной целью является выбор таких расписаний, которые позволяют решить задачи 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-е полное множество и найдём

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 на основе анализа такой локальной характеристики параллельного алгоритма, как значение функции минимальной загрузки отрезка, предлагают способы оценки снизу ресурсов, необходимых для реализации каждого заданного алгоритма:

• числа n процессоров при заданном ограничении на длительность T процесса;
• минимального времени T, необходимого для реализации данного алгоритма при заданном числе n процессоров.

Рис. 7.18.  К примеру нахождения нижней оценки числа исполнителей



Содержание раздела

---

---

Главная сайта

---