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


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

Нижняя оценка минимального числа процессоров, необходимого для выполнения алгоритма за заданное время

Алгоритм 5.

Первоначально полагаем n = 0. Организуем перебор всех отрезков [и1, и2] [0, T] в порядке

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

Для очередного анализируемого отрезка времени [и1, и2] находим значение

Если n' > n, выполняем операцию n := n'. После перебора всех отрезков окажется найденным значение n, которое равно максимальному из значений, удовлетворяющих (7.2).

Пример. Нахождение оценки n.

Нахождение (4)(и1,и2) будем иллюстрировать графически, возможными временными диаграммами (рис. 7.19).


увеличить изображение
Рис. 7.19. Нахождение нижней оценки числа исполнителей


Рис. 7.19. Окончание

В результате анализа всех отрезков находим n = max n' = 2.

Нижняя оценка минимального времени выполнения данного алгоритма на ВС

Алгоритм 6.

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

Организуем перебор всех отрезков [и1, и2] [0, T] в той же последовательности, что и в предыдущем алгоритме. (В процессе выполнения данного алгоритма значение T может увеличиваться, что при данном порядке перебора не приведёт к усложнению алгоритма.) Для очередного анализируемого отрезка времени [и1, и2] находим значение

d = (T)(и1,и2) - n(и2 - и1)

Если d > 0, выполняем операцию T := T + ] d/n [. Полагаем ф2j(T) := ф2j(T) + ] d/n [ , j = 1 , ... , m.

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

НЕ нашли? Не то? Что вы ищете?

Пример. Произведём оценку T для графа G, рассмотренного в предыдущем примере, и ВС, состоящей из двух процессоров, n = 2 (рис. 7.20).


увеличить изображение
Рис. 7.20. Оценка снизу минимального времени выполнения работ


Рис. 7.20. Окончание

Первоначально находим

После перебора всех отрезков, с учётом уточнения оценки времени в процессе этого перебора, окончательно находим T = 4.

<a href="http://mb. osp. ru/cgi-bin/href/intuit-240x90?67633" target="_top"><img src="http://mb. osp. ru/cgi-bin/banner/intuit-240x90?67633&options=T" alt="MadBanner" width="240" height="90" border="0" ismap="ismap"></a>

<a href="http://mb. osp. ru/cgi-bin/href/intuit-240x400?19832" target="_top"><img src="http://mb. osp. ru/cgi-bin/banner/intuit-240x400?19832&options=T" alt="MadBanner" width="240" height="400" border="0" ismap="ismap"></a>

Решение задачи 1 распараллеливания для однородных ВС

Формулировка задачи: Для данного алгоритма, которому соответствует информационный граф G, и для времени T, отведённого для его выполнения, найти наименьшее число n процессоров, составляющих однородную ВС, и план выполнения работ на них.

Метод точного решения задачи (метод "ветвей и границ") основан на следующей основной теореме.

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

Алгоритм 7 решения задачи 1 — нахождения графа-решения G'

Для графа G и времени T находим значения ранних {ф1j} и поздних {фj(T)}, j = 1 , ... , m, сроков окончания выполнения работ. (Если задача поставлена корректно, то

Находим оценку минимального числа n процессоров, которое необходимо для выполнения заданного алгоритма за время, не превышающее T. Пусть н — номер шага решения задачи. Полагаем н = 1. Находим наименьшее значение tн такое, что

F(ф11, ф12 , ... , ф1m, tн ) = rн > n.

Если такого tн нет, то n — решение задачи.

Выделяем множество работ Aн = {jм}, м =1 , ... , rн, для которых

ф1jм - tjм tн < ф1м,

т. е. тех работ, которые "порождают" данное значение F. Множество A является подмножеством некоторого ПМВНР.

Предположим, что мы можем упорядочивать комбинации дополнительных связей внутри множества Aн. Введём очередную комбинацию r - n связей, как указано в теореме — так, чтобы длина критического пути в изменившемся при этом графе G не превысила T. Если такая комбинация найдена, выполняем операцию н := н + 1, уточняем значения {ф1j} и {ф2j(T)} с учётом введённых связей, переходим к выполнению 4. Если такой комбинации связей не существует, либо все они уже испытаны, выполняем операцию н := н - 1. Если н = 0, т. е. на первом же шаге сглаживание загрузки процессоров не приводит к подтверждению того, что n — решение, выполняем операцию n := n + 1 и переходим к выполнению 3. Если н 0, восстанавливаем значения {ф1j} и {ф2j(T)} , найденные на данном шаге, и переходим к выполнению 6.

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

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

Примечания

Как упорядочить вводимые комбинации связей?

Пусть Aн — множество взаимно независимых работ, между которыми нужно ввести r - n связей по условию теоремы, т. е. построить некоторый граф, связывающий вершины Aн. Построим матрицу следования Lн, соответствующую этому графу. Первоначально эта матрица — нулевая. Вводим rн - n единиц так, чтобы:

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

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

Можно рекомендовать следующий способ сокращения перебора: введение дополнительных связей в пункте 6 алгоритма производить не только по критерию допустимого увеличения длины критического пути, но и по значениям функции минимальной загрузки отрезка. А именно, вводя очередную комбинацию связей на н-м шаге сглаживания функции плотности загрузки, не приводящую к увеличению длины критического пути сверх заданного T, необходимо вновь пересчитать значение функции с учётом новых связей на всех отрезках [и1, и2] [tн, T] . Если для испытываемого значения n на этих отрезках выполняется соотношение (7.2), данная комбинация связей может быть признана удачной. Таким образом, выполнение соотношения (7.2) в совокупности с допустимым увеличением длины критического пути определяет "границы" при ветвлении.

(Напомним, что метод "ветвей и границ", как метод перебора, обладает экспоненциальной сложностью, является NP-трудным. Поэтому сокращение перебора — очень важная задача.)

Пример. Найдём минимальное число n процессоров, необходимое для выполнения алгоритма, который представлен графом G на рисунке 7.21а, за время T = 7.


Рис. 7.21. Последовательные действия при точном решении задачи 1

Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6