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



              

Граф-схемы параллельных алгоритмов - часть 3


Матрица следования с задающими связями

Рис. 7.5.  Матрица следования с задающими связями

Определение 1. Назовём все связи по информации, обусловленные исходным видом графа G, задающими связями.

Определение 2.

Путями в графе G будем называть последовательности вершин вида a1, a2 , ... , as такие, что для любой пары соседних вершин ai и ai+1 существует дуга, исходящая из вершины ai и входящая в вершину ai+1.

Будем считать все пути в графе G допустимыми, т.е. реально существующими ветвями отображаемой программы.

Определение 3. Длиной пути в информационном графе G назовём сумму весов вершин, составляющих этот путь.

Определение 4. Путь максимальной длины Tкр в информационном графе G назовём критическим.

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

Если в графе G есть дуга, исходящая из вершины a и входящая в вершину b, т.е. существует задающая связь a

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

Определение 5. Множество связей, которые введены направленно внутри всех пар работ, принадлежащих одному пути в графе G и не связанных задающими связями, назовём множеством транзитивных связей.

Транзитивные связи полностью определяются задающими связями.

Алгоритм 1 дополнения треугольной матрицы S транзитивными связями.

  1. Организуем просмотр сверху вниз строк матрицы следования S.
  2. В очередной i-й строке организуем просмотр элементов в порядке увеличения j номеров столбцов.
  3. Если (i, j)=1, складываем строки i и j по операции дизъюнкции.
  4. Если исходная матрица следования S нетреугольная, последовательный просмотр её строк производится неоднократно до установления факта неизменности окончательно полученной матрицы.)

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




Содержание  Назад  Вперед