Лекции по дисциплине «Теория вычислительных процессов» (стр. 11 )

Информационные граф-схемы алгоритмов

со скалярными весами вершин

При решении задач распараллеливания, в особенности при статическом их решении, распространенным важным ограничением является предположение отсутствия в схеме алгоритма логических операторов. Это означает, что граф-схема алгоритма отражает только информационные связи между операторами, т. е. при одной реализации алгоритма выполняются все операторы. Это справедливо по следующим причинам.

1. Статический режим решения задач распараллеливания обусловлен необходимостью планирования выполнения в ограниченное время множества работ значительного объема. Чаще всего это крупные взаимосвязанные задачи, состав которых остается неизменным в течение длительного периода работы ВС. Тогда схема алгоритма, где эти задачи фигурируют как отдельные операторы, может отражать малое число логических ветвей или иметь единственную ветвь. Малый объем работ, заключенных в одном операторе, с учетом трудоемкости методов решения задач распараллеливания и необходимости работы средств синхронизации при выполнении операторов снизил бы эффективность распараллеливания. Рассуждения о целесообразном объеме распараллеливаемых работ справедлив и в случае, когда мы оцениваем необходимый вычислительный ресурс для реализации данного алгоритма. Такая задача решается для обоснования состава вычислительных средств при их специализированном длительном использовании.

2. Даже учитывая логические операторы, при поиске точных планов параллельной реализации операторов и оценке этих планов необходимо установить все действительные варианты совместного выполнения операторов, т. е. предусмотреть все значения логических переменных. Это говорит о важности обязательного элемента решения задач распараллеливания - необходимости их решения в том случае, когда состав выполняемых при одной реализации алгоритма операторов уже известен и известна их информационная зависимость, т. е. задана их частичная упорядоченность.

Скалярные весы вершин в информационном графе задают при рассмотрении однородных ВС, в которых каждый процессор выполняет оператор i за одинаковое время ti. Временем обмена информацией между процессорами можно пренебречь, если ВС располагает общей оперативной памятью. Если мы не рассматриваем связи по управлению, то матрица независимости М совпадает с матрицей следования S, дополненной транзитивными связями. Считаем что граф G не содержит контуров.

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

Без задания значения Т определение позднего срока окончания выполнения Оператора не имеет смысла. При Т=Ткр ранние сроки выполнения операторов, составляющий критические пути, совпадают с поздними сроками окончания их выполнения.

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

Алгоритм

1. Полагаем первоначально t11=t12=...t1m=0.

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

3. Пусть j - номер найденной необработанной строки. Если j-е строка не содержит единичных элементов, полагаем t1j=tj. Переходим к выполнению шага 6.

4. Если j-я строка содержит единичные элементы, выбираем элементы множества {t11...tim}, соответствующие номерам единичных элементов j-й строки.

5. Если все выбранные таким образом элементы, образующие множество {t1jg} n=1...k, отличны от нуля, полагаем

t1j=max t1jn+tj

g=1...Kj

В противном случае - шаг 7.

6. Обработанную j-ю строку помечаем с целью исключения ее повторной обработки. Переходим к шагу 2.

7. Если среди элементов множества {tvg} есть хотя бы один нулевой (т. е. данное значение раннего срока окончания выполнения оператора еще не определено), производим поиск следующей из необработанных строк, после чего алгоритм выполняем с шага 3.

Если матрица следования S треугольная, то никогда не складываются условия для выполнения шага 7. Ранние сроки окончания выполнения операторов находятся за один последовательный просмотр строк матрицы S. Очевидно, что Ткр=max (t11...tim).

Пример:

2 3

1 2

3 1 4 2 5 4

6 4 7 2

8 1

1 2

2 3

3 1 1

4 1 2

5 1 1 4

6 1 4

7 1 1 2

8 1 1 1 1 1

1 2 3 4 5 6 7 8

t11=t1=2 t15=max(t11, t12)+t5=7

t12=t2=3 t16=t14+t6=8

t13=t11+t3=3 t17=max{t12, t14}+t7=6

t14=t11+t4=4 t18=max(t13, t15, t16, t17}+t8=9

Выберем для каждого i=1...k подмножество (tjg}c{tj}g=1...ki, j=1...m, ki - число операторов алгоритма, выполняющихся на процессоре типа i, {ij}cDт.

Функцию Fi(tji...tiki, t) = Sf(tjg, t),

где f(tjg, t) ={ 1 при tÎ[tjg-tjg, tjg]

0 в противном случае.

назовем плотностью загрузки для i-го типа процессоров, найденной для значений (ti...tm)ÎDт.

Функцию Фi(tj1...tjkj, Q1, Q2)= Fi(tj1...tjki, t) dt назовем загрузкой отрезка [Q1, Q2]c[O, T] для i-го типа процессоров и (t1...tm)ÎDт.

Функцию i(T) (Q1, Q2)=min Фi (tj1...tjki, Q1, Q2) назовем минимальной загрузкой отрезка [Q1, Q2]c[O, T] для i-го типа процессоров. Для нахождение значений функции i(T) (Q1, Q2) необходимо анализировать только операторы, закрепленные за процессорами i-го типа.

Пусть каждый оператор данного алгоритма может быть выполнен процессором одного и только одного типа из множества типов i=1...k. Тогда для того, чтобы Т было наименьшим временем реализации данного алгоритма ВС, состоящей из множества {ni} процессоров, либо для того, чтобы набор {ni} процессоров был достаточен для выполнения данного алгоритма за время Т, необходимо, чтобы для любого отрезка времени [Q1, Q2]c[O, T] выполнялось соотношение i(T) (Q1, Q2)£ni(Q2-Q1)

Пусть алгоритм задан информационным графом со скалярными весами вершин, а каждый оператор может быть выполнен процессором одного и только одного типа из множества типов i=1...k. Пусть ВС представляет набор {ni} процессоров. Пусть далее Т1 - оценка времени реализации данного алгоритма на ВС, для которой на некотором отрезке {Q1, Q2]c[O, T1] для некоторого iÎ{1, k} выполняется соотношение i(T1) (Q1, Q2) - ni(Q2-Q1)=d, тогда наименьшее время Т реализации данного алгоритма удовлетворяет соотношению

Т³Т1+d

ni

Аналогично строятся алгоритм оценки минимального количества ni, i=1...k, процессоров, необходимых для выполнения данного алгоритма за время Т, и алгоритм оценки минимального времени Т выполнения заданного алгоритма набором {ni} процессоров k-типов. Разница заключается в том, что вместо одного значения (Т) (Q1, Q2), при анализе каждого отрезка (Q1, Q2) используется к значений (Е) (Q1, Q2) i=1...k Каждое из этих значений влияет на формирование значений ni или Т.

Поздние сроки окончания выполнения операторов при заданном значении Т можно найти по следующему алгоритму.

1. Полагаем первоначально t21(Т)=...t2m(Т)=0.

2. Находим первый справа столбец из необработанных еще столбов матрицы S. Если все столбцы обработаны, выполнение алгоритма заканчивается.

3. Пусть j-номер найденного необработанного столбца. Если j-й столбец не содержит единичных элементов, полагаем t21(Т)=Т. Переходим к шагу 6.

4. Если j-й столбец содержит единичные элементы, выбираем элементы множества {t21(Т)...t2m(Т)}, соответствующие номерам единичных элементов j-го столбца.