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

5. Если все выбранные таким образом элементы {t2jg (T)}c{t21(T, ... t2m(T)=min{t2jg(T)- tjg}. В противном случае выполняем шаг 7.

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

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

Пример.

Для Т=10 находим

Т28(10)=10 t26(10)=t28(10)-t8=9

t27(10)=t28(10)-t8=9 t25(10)=t28(10)-t8=9

t29(10)=min{t26(10)-t6, t27(10)-t7)}=5

t23(10)=t28(10)-t8=9

t22(10)=min{t25(10)-t5, t27(10)-t7}=5

t21(10)=min{t23(10)-t3, t24(10)-t4, t25(10)-t5}=3

Пусть tj - произвольное значение момента окончания j-го оператора, j=1...m, А - множество минорант (т. е. вершин, в которые не входит ни одна дуга) графа G.

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

tj-tj³0, если jÎA

tj³tj³ti, если существует связь ш®jiÎX\В, jÎX\A

T³tj, если jÎB

Соотношения задают многоугольник Dr в т-мерном пространстве ti,...tm. Выберем произвольную точку (t1...tm)ÎDr. Функцию F(t1... tm, t)=Sf(tj, t), где

f(tj, t)={1, при tÎ[tj-tj, tj]

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

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

Если зафиксировать моменты окончания выполнения операторов, т. е. выбрать точку в Dr, то значение функций F в каждый момент времени t совпадает с числом одновременно выполняемых в этот момент операторов.

Пусть данный граф G, в котором учтены транзитивные связи, образует l полных множеств ВНО (каждая пара таких множеств может иметь непустое пересечение. Обозначим ri, i=1...l, число операторов, образующих i=e полное множество, и найдем R=max{r1...re}.

Тогда, R=max(F-(t1... tm, t), Т. к. возможно и такое распределение выполняемых операторов во времени, когда на каком-то отрезке времени выполняются все операторы, входящие в полное множество ВНО с числом операторов R.

Минимальное число и процессоров одинаковой специализации и производительности, способных выполнить данный алгоритм за время Т³Ткр, не превышает R=max {r, re}, где ri, i...11 - число операторов входящих в i-е полное множество ВНО, составленное по соответствующему этому алгоритму графу G-го скалярными весами вершин.

Функцию Ф(t, ... tm, Q1, Q2)= F(t, ... tm, t)dt назовем загрузкой отрезка [Q1, Q2]c[O, T] для [t1... tm]ÎDr. Функция Ф определяет объем работ (суммарное время их выполнения) на фиксированном отрезке времени.

Функцию (Т) (Q1, Q2)=minФ(t,...tm, Q1, Q2) назовем минимальной загрузкой отрезка.

Функция определяет минимально возможный объем работ, который при данном Т и при различных допустимых значениях t,...tm должен быть выполнен на отрезке времени [Q1, Q2]. Это означает, что как бы мы не планировали вычислительный процесс, который должен быть закончен к моменту времени Т, т. е. какой бы набор значений t1... tm мы не выбирали, объем работ, выполненных на отрезке времени [Q1, Q2], не может быть меньше значения (Т) (Q1, Q2).

Для того чтобы Т было наименьшим временем выполнения данного алгоритма вычислительной системой, состоящей из процессоров, либо чтобы и процессоров было достаточно для выполнения данного алгоритма за время Т, необходимо, чтобы для данного отрезка времени [Q1, Q2]Î [Q2-Q1].

Алгоритм нахождения функции (Т) (Q1, Q2) имеет вид:

1. Предполагаем, что для каждого оператора j известны значения tj, t1j, t2j [T]. Полагаем равным нулю значение переменной.

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

3. Полагаем

Ч:=Ч+min{(t1j-Q1), (Q2-t2j (T)+tj), Q2-Q1}

где l(x)={х при х³0

0 при х<0}

После перебора всех операторов Ч=Ч(Т) [Q1, Q2].

Пусть заданный алгоритм, которому соответствует информационный граф G со скалярными весами вершин, реализуется на ВС, состоящей из и процессоров, и Т1 - оценка снизу времени выполнения алгоритма. Пусть на отрезке времени [Q1, Q2]с[О, Т] выполняется соотношение:

Ч(Т1) (Q1, Q2)-n[Q2-Q1)=d>0. Тогда наименьшее время Т реализации алгоритма удовлетворяет соотношению: Т³Т1+d/n.

Оценка минимального числа n процессоров, необходимо для выполнения заданного алгоритма за время Т, производится по следующему алгоритму:

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

2. Организуем перебор всех отрезков [Q1, Q2]с[О, Т] в порядке

[0,1]

[0,2]; [1, 2]

[0,3]; [1, 3]; [2,3]

[О, Т] [1, Т]...[Т-1, Т]

Всего таких отрезков Т (Т+1)/2-1.

3. Для очередного анализируемого отрезка времени [Q1, Q2] находим значение n1=Ч(Т) (Q1, Q2)/([Q2-Q1).

4. Если n>n выполняем операцию n:=n. После перебора всех отрезков окажется найденным значениe n.

Оценка минимального времени Т выполнения заданного алгоритма на ВС, содержащей и процессоров, может производиться по следующему алгоритму.

1. Первоначально полагаем

Т=max{]1/n Sti[, Tкр}

2. Организуем перебор всех отрезков [Q1, Q2]с[О, Т] в той же последовательности, что и в предыдущем алгоритме. В процессе выполнения данного алгоритма значение Т можно увеличивать, что при данном порядке перебора не приведет к усложнению алгоритма.

3.Для очередного анализируемого отрезка [Q1, Q2] находим значение d=Ч(Т) (Q1, Q2)-n(Q2-Q1).

4. Если d>0, выполняем операцию

Т:=Т+]d/n[

]X[ - ближайшее целое, не меньшее Х.

5. Полагаем

t2j(T):=t2j(T)+[d/n], j=1...m

После перебора всех отрезков [Q1, Q2] окажется найденным окончательное значение Т - оценка минимального времени выполнения данного алгоритма на данной ВС.

Информационные ГСА с векторными весами вершин

Пусть ВС состоит из процессов k-типов, различных по производительности, специализации и стоимости. Пусть ni i=1...k - число процессов i-го типа. Веса в информационном графе G, отображающем заданный алгоритм, являются векторами, где компонента tji - время выполнения j-го оператора на процессоре i-типа.

Если 1) оператор b входит в одно и только одно полное множество ВНО с числом операторов М; 2) компоненты веса вершины ab в информационном графе G упорядочены по не убыванию так, что tb1£tb2£...£tbS=tbS+1=...tbk= при S<k и 3) существует положительное l<S такое, что Sni<M<Sni, то при исследовании и выборе планов параллельного выполнения алгоритма можно положить tpl+1=...tps= , что приведет к исключению процессоров соответствующих типов из рассмотрения при поиске варианта назначения оператора b.

Оператор входит в одно и только одно полное множество ВНО в том случае, если все операторы, соответствующие нулевым элементам его строки, в матрице следования S, дополненной транзитивными связями, попарно взаимно независимы. Расположим в порядке неубывания компоненты весов каждой вершины jю Индекс каждой компоненты веса, указывающий на принадлежности типу процессора, запомним. Компоненты, равные, отбросим. Таким образом, каждая из вершин j графа G будет обладать вектором-весом размерности pj£k, равной числу отличный от бесконечности компонент исходного вектора-веса этой вершины.

Будем считать, что tji£tji+1 i=1...pj-1.

Построим граф G* на основе графа G, заметив каждую вершину j множеством вершин {(j..l)}, обладающих скалярными весами tje¹ , j=1...m, l=1...pj. Каждая вершина в G* связана дугами в соответствии со связями породившей ее вершины в графе G.

Выбрав по одной вершине из каждого множества вершин, получим граф G, где каждой вершине соответствует скалярный вес, равный времени выполнения обозначенного этой вершиной оператора процессором определенного типа. Назовем такой граф G - выборной графа G*. Все планы реализации данного частично упорядоченного множества работ, представленного графам G*, можно получить на основе перебора R"Пpj G-выбором. Каждая из них предусматривает, что каждый оператор заранее закреплен за процессорами одного и только одного типа по производительности и стоимости.

Минимальную из компонент вектора-веса вершины a в графе G назовем младшим скалярным весом этой вершины.

G - выборы графа G*, составленную из вершин с младшими скалярными весами этих вершин в G, назовем младшей G-выборкой графа G*.

Так как G-выборка представляет собой информационный граф со скалярными весами вершин, отличающийся тем, что он отражает выполнение работ в неоднородной ВС, то на него распространяются все рассмотренные ранее определения и алгоритмы для информационного графа со скалярными весами вершин, отражающие выполнение работ в однородной ВС.

Распараллеливание в однородной ВС по информационному графу

Рассмотрим две взаимно обратные задачи:

Задача 1. Для данного алгоритма, которому соответствует информационный граф G со скалярными весами вершин, и для времени Т, отведенного для его выполнения, найти наименьшее необходимое число и процессоров, входящих в состав однородной ВС, и план выполнения операторов на них.

Задача 2. Для данного алгоритма, которому соответствует информационный граф G со скалярными весами вершин, найти минимальное время Т и план реализации этого алгоритма на данной однородной ВС, в состав которой входит и процессор.

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

Для того, чтобы значение и являлось наименьшим числом процессоров в однородной ВС, которая выполняет алгоритм, представленный информационным графом G со скалярными весами вершин, за время, не превышающее заданное значение Т, необходимо и достаточно, чтобы и было наименьшим числом, для которого можно построить граф G, объединив вершины, соответствующие операторам каждого полного множества ВНО, содержащего r>n операторов, r-n ориентированным дугами в n путей, не содержащих общих вершин. При этом длина критического пути в графе G не должна превышать значение T.

Так как каждый оператор может входить не в одно полное множество ВНО, то общее число связей, которое необходимо ввести для построения графа G, лишь не превышает значения: S(rg-n), где s - число полных множеств ВНО, в каждом из которых rg-n операторов.