glava2 (1033925), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

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

Кратчайший путь из одного источника (алгоритм Дейкстры) [2].

Вход: Ориентированный граф G = (A, R), источник a₀  A и функция l, отображающая множество A  A в множество неотрицательных вещественных чисел. Полагаем l(a_i, a_j) = +, если ребро (a_i, a_j), a_i  a_j не принадлежит графу, и l(a, a) = 0.

Выход: Для каждого a  A наименьшая сумма меток на ребрах из G, взятая по всем путям, идущим из a₀ в a.

Метод: Строим такое множество K  A, что кратчайший путь из источника в каждый узел a  K целиком лежит в K. Массив D[a] содержит стоимость текущего кратчайшего пути из a₀ в a, который проходит только через узлы из K. Описание алгоритма приведено на рис.2.8.

Алгоритм Дейкстры

begin

1. K  {a₀};

2. D[a₀]  0;

3. for a  A - {a₀} do D[a]  l(a₀, a);

4. while K  A do

begin

1. выбрать узел b  A - K, для которого D[b] принимает наименьшее значение;

2. добавить b к K;

3. for a  A - K do

4. D[a]  min(D[a], D[b] + l(b, a));

end

end

Рис.2.8

Рассмотрим граф, изображенный на рис.2.9. Вначале K = {a₀}, D[a₀] = 0, а D[a_i] = 2, +, +, 10 для i = 1, 2, 3, 4 соответственно. При первой итерации цикла в строках 4-8 берем b = a₁, поскольку D[a₁] = 2 – наименьшее значение для D. Затем вычисляем D[a₂] = min(+, 2 + 3) = 5 и D[a₄] = min(10, 2 + 7) = 9. Последовательность значений для D и другие вычисления алгоритма приведены на рис.2.10.

Матрица минимальных путей для рис.2.9

Вычисления алгоритма на графе с рис.2.9

Рис.2.10

Алгоритм позволяет также найти остовную конструкцию, по которой определяются составляющие дуги кратчайшего пути от a₀ к a. На рис.2.9 данная основная конструкция (дерево) выделена жирным.

2.2. Представление алгоритмов обработки

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

Введем отношение :

для каждой компоненты, выполняемой параллельно. Это отношение определяет какое количество затрат (издержек), связанных с организацией обмена данными, приходится на (полезные) вычисления.

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

Отсюда и возникает потребность в нахождении некоторого компромисса между двумя видами затрат и выбора определенной величины отношения (1).

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

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

Теперь вполне реально для алгоритма или некоторой его части обоснованно определить характер отношения (1), как отношение сложности c к объему обмениваемой информации e

.

П
усть p_пр - производительность процессора [кол.опер./сек], а v_кан - скорость передачи данных по каналу [бит/сек].Тогда отношение

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

Естественно предположить, что введенная характеристика-отношение компоненты не должна быть меньше подобной характеристики-отношения процессора с каналом.

Отсюда и вытекает уже введенное выше отношение (1), но уже в конкретном представлении

, (2)

где wl [сек] – вычислительная загрузка, а cl [сек] – коммуникационная загрузка алгоритма (компоненты), применительно к конкретному процессору.

Допустимо заменить неравенство (2) и равенством

, (3)

где  – некоторый скаляр, выбираемый разработчиком.

Тем самым, для алгоритма обработки имеем

G_A = <C, E >,

где С – множество вершин (компонент), представляемых либо в виде вектора, элементы которого вычислительные сложности компонент, оцениваемые количеством операций , либо в виде диагональной матрицы сложности , n – число компонент; c_i – вычислительная сложность компоненты, E - отношение на

множестве С, задаваемое в виде взвешенной квадратной матрицы смежности , элементы e_ii = 0, а остальные элементы определяют вес – объем передаваемой информации от i-ой к j-ой вершинам.

На рис.2.11а и 2.11б приведен некоторый граф алгоритма обработки, представленный в параллельно-ярусной форме.

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

большего числа процессоров не улучшит результирующие временные свойства.

Окончательно, граф алгоритма обработки задается взвешенным графом G_A , представленным в параллельно-ярусной форме (рис.2.11в),

G_A = <C, E, H >.

2.2.1. Представление численных процедур интегрирования

Анализ описания динамических процессов и систем управления с сосредоточенными параметрами показывает, что чаще всего оно задается совокупностью обыкновенных алгебраических и дифференциальных уравнений (ОАДУ) вида

, (4)

где x = [x₁, x₂, ..., x_n] ^T - вектор состояния, v = [v₁, v₂, ..., v_m] ^T - вектор промежуточных переменных, u = [u₁, u₂, ..., u_r]^T - вектор управления.

Введением дополнительного скалярного уравнения

явный фактор времени t = x_{n+ 1} вводится в число переменных состояния.

Тем самым, имеем такую общую форму записи ОАДУ

(4)

Характеристики

Список файлов книги