Свойства отношений зависимости и независимости между операциями

1. Отношения сильной зависимости (S_i  S_j):

• Нерефлексивность

из S_{i →} S_j S_j→ S_i

• Несимметричность

S_{i →} S_i - без смысла

• Транзитивность

Из S_i → S_j и S_j→ S_k ≠ S_i → S_k

2. Отношения слабой зависимости (S_i S_j):

• Из S_i S_j ≠ S_j S_i

• Из S_i S_i - без смысла

• Из S_i S_j и S_j S_k ≠ S_i S_k

3. Отношения слабой независимости (S_i S_j):

• Из S_i S_j S_j S_i

• S_i S_j

• Из S_i S_j и S_j S_k ≠ S_i S_k

4. Отношения сильной независимости (S_i S_j):

• Из S_i S_j ≠ S_j S_i

• S_i S_j

• Из S_i S_j и S_j S_k ≠ S_i S_k

4. Алгоритм распараллеливания последовательных программ путем приведения их к полной параллельной форме (ппф)

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

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

Последовательность операторов в виде (3) или (4) называется линейной цепочкой, если выполняется (3).

= S₁ , S_{2 ,} S₃, … , S_l (3)

= S_i , S_{i+1 ,} … , S_i+p (4)

S₀ → S_{i+1 ,} S_i+1 → S_i+2 … S_i+(p-1)→ S_i+p => S_i , S_i+1 , S_i+p

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

Алгоритм приведения программы к ППФ предполагает выделение максимально-последовательных цепочек. Для двух или более максимально-последовательных цепочек выполняется условие:

α₁ α₂ = 0

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

Пример (рис. 2):

S ₁ → S₂ α₁ = { S₁ , S_{2 ,} S₃ }

S₂ → S₃ α₂ = { S₄ , S_{5 ,} S_6, S₇ }

S₄ → S₅ α₁ α₂ = 0

S₅ → S₆

S₆ → S₇

S₃ → S₈

S₇ → S₈

Рисунок 2 – Пример приведения программы к ППФ

Программа Р’, полученная из последовательной программы Р путем выделения в ней всех максимальных последовательных цепочек, называется ППФ(полной параллельной формой) линейной программы Р.

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

Программа P’ - это параллельная форма программы Р, если в программе Р могут быть выделены последовательные, параллельные, взаимно параллельные участки и в результате получена ППФ.

Условие:

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