Вычисление матриц следования, расширенных матриц следования и матриц следования с транзитивными связями.

Определение 1.Если в параллельном алгоритме существует связь между операторами α, β и α – исполнительный блок, то в графе G существует дуга d_i Î D₁, исходящая из вершины α и входящая в вершину β. Эту связь будем обозначать α → β.

Определение 2.Если в параллельном алгоритме существует связь между операторами α, β и α – логический блок, то в графе G существует дуга d_i Î D₂, исходящая из вершины α и входящая в вершину β. Эту связь будем обозначать или соответственно и называть связь по управлению.

Связь определяет связь между операторами, если оператор α принимает значение “ TRUE ”, связь - в противном случае.

Связи α → β, , назовём задающими связями.

Определение 3.Путями в графе G назовём последовательности вершин α₁,…, α_n , такие, что для любой пары вершин α_i, α_i+1 существует дуга uÎD1 U D2, исходящая из вершины α_i и входящая в вершину α_i+1.

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

Определение 4.Характеристикой пути в графе G назовем количество вершин, входящих в этот путь.

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

Определение 6.Путь максимальной длины Т_кр в графе G со скалярными весами вершин назовем критическим. В одном графе может быть несколько критических путей.

В качестве примера алгоритмов в виде схемы последовательного и параллельного алгоритмов с некоторыми трехмерными весами вершин представлен рис. 3.

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

Более точное определение матрицы следования заключается в следующем: i –ой вершине графа G ставятся в соответствие i – ые столбец и строка матрицы, если существует связь по управлению , то элемент матрицы равен (i,j) = jT, порождает значение (i,j) = jF, при j → i образуется (i,j) = 1. Остальные элементы матрицы равны 0.

Если мы хотим сказать, что между элементом i и j существует некоторая связь, то будем писать i → j. Для отражения весов вершин вводится понятие расширенной матрицы следования SR: прибавляется дополнительно k столбцов с номерами m+1,…,m+k, где k – размерность вектора весов вершин граф – схемы.

3T

3T

3F

∞

3T

∞

3F

3F