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

Рис. 7.8. Первый шаг обнаружения контура

После второго шага преобразования S принимает вид, показанный на рис. 7.9.

Рис. 7.9. Обнаружение контура

Т. к. на главной диагонали матрицы появились единицы, то граф G содержит циклы (контуры). Из рисунка графа виден цикл 2 6 3 5 . "Участники" цикла отмечены единицами на главной диагонали.

Определение 6. Работы a и b будем называть взаимно независимыми, если в матрице следования S выполняется условие (a, b) = (b, a) = 0.

Определение 7. Работы {ai}, i = 1, ... , s, образуют полное множество взаимно независимых работ (ПМВНР), если для любой работы j {ai} существует задающая или транзитивная связь (aм, j) = 1 или {(j, aн) =1} (м, н {1 , ... , s}).

Например, для графа G, представленного на рис. 7.1, после введения транзитивных связей, что учтено в матрице следования на рис. 7.6, можно установить следующие ПМВНР: {1,2}, {2,3,4}, {3,4,5}, {2,3,6}, {3,5,6,7}, {8}.

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

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

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

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

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

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

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

Если хотя бы один из выбранных элементов нулевой (соответствующий ранний срок ещё не найден), выполняем шаг 2.

Обработанную 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 нахождения поздних сроков окончания выполнения работ при заданном значении.

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

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

ф2j (T) = min {ф2jн (T) - tjн }.

В противном случае выполняем шаг 2.

Обработанный 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, но соблюдая при этом порядок следования работ, мы получим множество допустимых расписаний выполнения работ.

Определение 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б.