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

В основу алгоритма точного решения задачи 1 положим метод направленного перебора, называемые методом ветвей и границ. В данном случае ветвление определяется различными возможными способами введения дополнительных связей в каждое полное множество ВНО, число операторов в котором превышает n, или его подмножество.

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

1. Если связь a®b привела к формированию графа, длина критического пути в котором превышает Т, т. е. t1a>t2tb(Т)-tb, то следующее введение связей не может привести к уменьшению длины критического пути вновь.

2. Если оператор a, входящий в некоторое полное множество ВНО, которое содержит r>n операторов, удалось назначить для выполнения, так что данные ранние и поздние сроки окончания выполнения оставшихся операторов этого множества не изменились, то это назначение не ограничивает числа вариантов распределения этих операторов.

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

Алгоритм нахождения графа-решения G имеет вид:

1. Для заданного информационного графа G со скалярными весами вершин и данного времени Т находим значения ранних t1i и поздних t2ш (Т) сроков окончания выполнения операторов. Для корректности постановки задачи должно выполняться соотношение max{t1i}=Ткр£Т. Найденные значения {t1i} фиксируют исходное расписание выполнения операторов за время, не превышающее Т.

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

3. Полагаем g=1, G(g)=G, t(g)1i=t1i, t(g)2i(T)=t2i(T)/

4. Находим наименьшее значение
tg=t(g)(1j)-tj, такое, что F(t11(g),...t1m(g), tg)=rg>n.

Если такого значения Tg нет, то и - решение задачи.

5. Выделяем множество операторов

Аg={ajm} M=1...rg, для которых t(g)1оь-еоь£t(g)1оь.

Множество Аg является подмножеством некоторого полного множества ВНО.

6. Предположим, что мы располагаем возможностью упорядочения комбинации дополнительных связей внутри множества АgВНО. Введем очередную комбинацию rg-n связей, так, чтобы длина критического пути в изменившемся при этом графе G(g) не превысила Т.

7. Если такая комбинация найдена, выполняем операцию, g:=g+1, запоминаем новые значения t(g)1i и t(g)2i (Т), найденные с учетом введенных связей, и переходим к выполнению шага 4.

8. Если такой комбинации связей не существует, либо все они уже испытаны, выполняем операцию g:=g-1.

9. Если g=0, т. е. на первом же шаге сглаживание загрузки процессоров не приводит к подтверждению того, что и - решение, выполняем операцию n:=n+1 и переходим к шагу 3. Если g¹0, переходим к выполнению шага 6.

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

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

Как способ сокращения перебора можно рекомендовать введние дополнительных связей на шаге 6 алгоритма не только по критерию допустимого увеличения длины критического пути, но и по значениям функции минимальной загрузки отрезка, т. е., вводя очередную комбинацию связей на g-том шаге сглаживания функции плотности загрузки, не приводящую к увеличению длины критического пути сверх значения Т, необходимо вновь пересчитать значения функций и с учетом новых связей на всех отрезках [Q1, Q2]с[tg, Т]. Если для испытываемого значения и на этих отрезках выполняется соотношение Ч(Т) (Q1, Q2)£n(Q2-Q1), то данная комбинация связей может быть признана удачной.

При Т=Ткр и указанной выше процедуре введения дополнительных связей очевидно, что если в анализируемом множестве взаимно независимых операторов оператор b принадлежит критическому пути, то любая связь a®b, где a принадлежит этому же множеству, ведет к увеличению его длины, т. е. не должна испытываться.

После нахождения графа-решения G само распределение множества операторов между и процессорами не представляет трудностей, т. к. известны моменты начала выполнения каждого оператора, которые равны раннем срокам начала их выполнения, найденным по графу G. При этих сроках одновременно могут выполняться не более и операторов. Остается лишь закрепить операторы за процессорами. Для этого достаточно, имитируя загрузки каждого процессора во времени, просматривать значения ранних сроков начала выполнения операторов (значения t1i-ti) в порядке неубывания и закреплять соответствующие за процессорами, которые в эти моменты времени не загружены счетом.

Рассмотрим возможный алгоритм выбора допустимой комбинации rg - n связей внутри множества ВНО, содержащего rg операторов.

Пусть Аg ={jm}, М=1...rg - множество ВНО. Сформируем квадратную матрицу Lg размера rg. Все элементы этой матрицы первоначально положим равными нулю. Задача заключается в последовательном формировании различных допустимых вариантов единичной матрицы следования Lg в соответствии с введением дополнительных связей между операторами множества Аg.

Нетрудно установить, что для удовлетворения заданных требований в матрицу Lg необходимо записывать rg - n единиц, так, чтобы выполнялись условия:

а) граф, соответствующий получаемой при этом матрице, не должен содержать контуров (т. е. диагональные элементы всегда должны быть нулевыми);

б) в каждой строке и каждом столбце матрицы не должно содержаться больше одной единицы. Если Т=Ткр, закрепим l³1 строк за операторами из Аg, принадлежащими критическим путем, тогда появляется дополнительное условие, которое в этом случае необходимо выполнять: первые l строк матрицы Lg должны быть нулевыми.

Вводимые связи упорядочим так, что единица, соответствующая р-й связи, р=1...rg - n, окажется записанной в строке, выше которой обязательно есть и только есть р-1 ненулевых строк матрицы Lg. Таким образом, р-я связь при проверке всех комбинаций пробегает строки от р до rg -[(rg - n)-p]=n+р или при Т=Ткр от l+р до n+р.

Алгоритм

1. Ставим в соответствие каждому оператору jmÎAg значения t(g -1)1jm и t(g -1)2jm(T) m=1...rg-n.

2. Вводим начальную, первую из возможных комбинаций связей, удовлетворяющих условиям 1 и 2. Легко видеть, что единичные элементы в этом случае располагаются в матрице Lg параллельно главной диагонали, начиная с позиции (1,2) при Т¹Ткр и с позиции (l+1,1) при Т=Ткр.

3. Организуем последовательный просмотр строк матрицы Lg.

4. Пусть очередная м-я анализируемая строка матрицы не содержит единичных элементов. Полагаем t*1jm=t(g -1)1jm, переходим к выполнению шага 7.

5. Пусть очередная м-я анализируемая строка содержит единичный элемент в l-м столбце. Тогда, если уже найдено значение t*1jm, полагаем t*1jm=t*2jm+tjm. В противном случае переходим на шаг 3.

6. Если t*1jl>t2j(g-1) (Т), данная комбинация связей не является допустимой, переходим к формированию следующей комбинации связей - выполнению шага 8. В противном случае выполняем следующий шаг.

7. Если закончен однократный просмотр строк матрицы Lg, но найдены не все значения t*1jm М=1...rg, организуем повторный просмотр строк матрицы Lg, переходим к выполнению шага 3. Если все указанные значения найдены, найдена и необходимая комбинация связей. Она может быть использована при выполнении шага 6 предыдущего алгоритма. В дальнейшем она должна быть введена в информационный граф, полученный на (g-1)-м шаге сглаживания функции плотности загрузки и по нему должны быть определены новые значения ранних и поздних сроков окончания выполнения операторов. Даже эта комбинация может подвергнуться новому испытанию с помощью функции Ч и быть отвергнутой. Тогда выполнение данного алгоритма поиска необходимой комбинации связей внутри данного множества взаимного независимых операторов должно быть продолжено со следующего шага.

8. Пусть в соответствии с упорядочением вводимых связей в общем случае единичные элементы матрицы Lg, соответствующие связям р+1, ... rg-n, занимают крайнее правое положение, удовлетворяющее условиям 1 и 3, в строках матрицы с номерами n+р+1...rg соответственно. Легко видеть, что эти элементы находятся под главной диагональю. Если р=0, то комбинация единичных элементов - последняя из возможных по условиям 1 и 2. При решении задачи 1 завершение перебора всех возможных комбинаций связей, удовлетворяющих условиям 1 и 2, означает, что необходимой комбинации связей не существует. При выполнении предыдущего алгоритма это соответствует необходимости выполнения шага 8.

Если р>0, полагаем равным нулю эти элементы и смещаем единицу, соответствующую р-й связи по строке, в которой она расположена, на одну позицию вправо или в крайнее левое положение на следующую строку (которая в этом случае обязательно является нулевой). Данное смещение производится так, чтобы по отношению к связям 1... р-1 выполнялось условие 2, т. е. в результате проверки условия 2 данное смещение может быть произведено неоднократно.