4.1 Условия приводимости к ппф

Для того, чтобы линейная программа была приводимой к ППФ, необходимо и достаточно, чтобы для каждой пары ее взаимно независимых операторов S_i и S_j и для каждого S_k N₂ (S_i, S_j), где i< k< j (т.е. S_k лежит между S_i и S_j) имело место условие

N₁ (S_i, S_j)3*( S_k), (5)

Где N₁ (S_i, S_j)=3*( S_i)3*( S_j), N₂ (S_i, S_j)=3*( S_i)3*( S_j)- N₁ (S_i, S_j),

_*

3*( S_k)=S S_kS

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

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

В том случае, если для линейной программы условие (5) выполняется, для не существует ППФ и при том единственная.

Упрощенная интерпретация условия

1. S_i и S_j - независимы_;

2. Между S_i и S_j имеется оператор S_k ;

3. Для S_k выполняется:

S_k N₂ (S_i, S_j), где i< k< j при N₁ (S_i, S_j)3*( S_k).

Пояснение к условию

Множество 3*( S_i) – это множество всех операторов, зависящих от S_i слабо.

N₁ (S_i, S_j) - это множество операторов, зависящих как от S_i , так и от S_j. Если S_i и S_j - независимы, то могут выполняться параллельно, то есть находиться в параллельных ветвях. Следовательно, N₁ – это те элементы, которые являются точками слияния параллельных ветвей.

N₂ (S_i, S_j) – это операторы, зависящие либо от S_i либо от S_j, тогда S_{к ,} входящее в N_{2 –} это оператор_, принадлежащий одной из параллельных ветвей (если S_k принадлежит ветви, то оператор в N₁ автоматически зависит от S_k).

Для того, чтобы программа Р по отношению к операторам S_i и S_j была приводима к ППФ необходимо:

• Чтобы операторы S_i и S_j были независимыми;

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

П ример:

S₁ → S₅

S₂ → S₅

S₃ → S₆

S₄ → S₆

S₅ → S₇

S₆→S₇

Выполним проверку условий для операторов S₁ и S_3:

1. S_1, S₃ - независимы;

2. S₂ между S₁ и S₃;

3. N₂ (S₁, S₃)={ S_5, S_6, S₇}\ { S₇} ={ S_5, S₆}

N₁(S₁, S₃) = { S₇}

3*( S₂)=S_5, S₇ 

N₁ (S₁, S₃)3*( S₂) (6)

Так как не выполняется условие, S₂ входит в N₂ хотя выполняется условие (6), то данная форма не может быть приведена к ППФ.

Правило:

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

Правило изменения порядка:

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

S₁→S₃

S₂→S₃

S₄→S₆

S₅→S₆

S₃→S₇

S₆→S₇

1. S₁ и S₄

2. S₂ и S₃ между S₁ и S₄

3. N₁ (S₁, S₄ )= {S₇}

N₂ (S₁, S₄ )= {S₇, S₆}

3*( S₃)= S₇  =>

S₃ N₂ (S₁, S₄ ) и N₁ (S₁, S₄ )3*( S₃)

Таким образом, для операторов S₁ и S₄ программа является приводимой к ППФ.